玩无限 - 懒惰的算术

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是真的,多亏了懒惰的评价.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.

编辑:添加了实例Num.

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 one-liners的好文章.