玩转无穷大——懒惰算术

许多现代编程语言允许我们处理潜在的无限列表并对它们执行某些操作。

示例[Python]：

EvenSquareNumbers = ( x * x for x in naturals() if x mod 2 == 0 )

这样的列表可以存在，因为只计算实际需要的元素。 （懒惰评价）

我只是出于兴趣想知道是否有可能（甚至在某些语言中实践过）将惰性求值机制扩展到算术。

例子： 给定偶数的无限列表evens = [ x | x <- [1..], even x ]我们无法计算

length evens

因为这里所需的计算永远不会终止。

但我们实际上可以确定

length evens > 42

无需评估整体length term.

这在任何语言中都可能吗？哈斯克尔呢？

编辑：为了使这一点更清楚：问题不在于如何确定惰性列表是否短于给定数字。它是关于以延迟完成数值计算的方式使用传统的内置函数。

sdcvvc 展示了 Haskell 的解决方案：

data Nat = Zero | Succ Nat deriving (Show, Eq, Ord)

toLazy :: Integer -> Nat
toLazy 0 = Zero
toLazy n = Succ (toLazy (n-1))

instance Num Nat where
   (+) (Succ x) y = Succ (x + y)
   (+) Zero y = y
   (*) Zero y = Zero
   (*) x Zero = Zero
   (*) (Succ x) y = y + (x * y)
   fromInteger = toLazy
   abs = id
   negate = error "Natural only"
   signum Zero = Zero
   signum (Succ x) = Succ Zero

len [] = Zero
len (_:x') = Succ $ len x'

-- Test 

len [1..] < 42 

这在其他语言中也可能吗？

您可以创建自己的自然数...

data Nat = Zero | Succ Nat deriving (Show, Eq, Ord)

len :: [a] -> Nat
len = foldr (const Succ) Zero

toLazy :: Int -> Nat
toLazy 0 = Zero
toLazy n = Succ (toLazy (n-1))

a = len [1..] > toLazy 42

那么 a 是 True，这要归功于惰性求值。 len 使用foldr 至关重要，foldl 不适用于无限列表。你也可以做一些算术（未经测试）：

instance Num Nat where
   (+) (Succ x) y = Succ (x + y)
   (+) Zero y = y
   (*) Zero y = Zero
   (*) x Zero = Zero
   (*) (Succ x) y = y + (x * y)
   fromInteger = toLazy
   abs = id
   negate = error "Natural only"
   signum Zero = Zero
   signum (Succ x) = Succ Zero

例如，2 * 无穷大 + 3 是无穷大：

let infinity = Succ infinity

*Main> 2 * infinity + 3
(Succ (Succ (Succ ^cCc (Succ (Succ (SuccInterrupted.

第二种解决方案

另一种解决方案是使用 () 列表作为惰性自然数。

len = map (const ())
toLazy n = replicate n () 
a = len [1..] > toLazy 42

Check Hackage http://hackage.haskell.org/package/peano-inf.

编辑：添加实例编号。

Edit2:

将第二个解决方案翻译成Python：

import itertools

def length(x):
    return itertools.imap(lambda: (), x) 

def to_lazy(n):
    return itertools.chain([()] * n)

要添加数字，请使用 itertools.chain，要乘法，请使用 itertools.product。这不像 Haskell 中那么漂亮，但它确实有效。

在任何其他带有闭包的严格语言中，您可以使用类型 () -> a 而不是 a 来模拟惰性。使用它可以将第一个解决方案从 Haskell 翻译成其他语言。然而，这很快就会变得不可读。

也可以看看一篇关于 Python 俏皮话的好文章 http://blog.sigfpe.com/2008/09/on-writing-python-one-liners.html.