language-agnostic - 玩无限游戏-惰性算术

Question

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

示例[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术语。

这有什么可能吗？那Haskell呢？

编辑:为了使观点更清楚:问题不是关于如何确定懒惰列表是否短于给定数字。这是关于使用常规的内置函数的一种方式，即懒惰地进行数值计算。

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 

其他语言也可以吗？

Answer 1

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

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

检查 Hackage。

编辑:添加了实例编号。

编辑2:

第二种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翻译成其他语言。但是，这将很快变得不可读。

另请参见 a nice article on Python one-liners。