玩无限 - 懒惰算术

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。

编辑：添加了实例编号。

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那么漂亮，但它起作用。

在任何其他使用闭包的严格语言中，您可以使用type（） - > a而不是a来模拟懒惰。使用它可以将第一个解决方案从Haskell翻译成其他语言。但是，这将很快变得不可读。请参阅a nice article on Python one-liners。

Answer 2

你可以通过试图从超过42个元素获得你想要的东西。

Answer 3

不知道我理解你的问题，但让我们试试这个。也许你正在寻找溪流。我只说二郎神，出了FP语系，所以...

esn_stream() -> 
    fun() -> esn_stream(1) end. 

esn_stream(N) -> 
    {N*N, fun() -> esn_stream(N+2) end}. 

调用流总是返回下一个元素和乐趣，你应该调用来检索下一个元素。这样你就可以实现懒惰的评估。

然后你就可以定义一个is_stream_longer_than功能：

is_stream_longer_than(end_of_stream, 0) -> 
    false; 
is_stream_longer_than(_, 0) -> 
    true; 
is_stream_longer_than(Stream, N) -> 
    {_, NextStream} = Stream(), 
    is_stream_longer_than(NextStream, N-1). 

结果：

1> e:is_stream_longer_than(e:esn_stream(), 42). 
true 

2> S0 = e:esn_stream(). 
#Fun<e.0.6417874> 

3> {E1, S1} = S0(). 
{1,#Fun<e.1.62636971>} 
4> {E2, S2} = S1(). 
{9,#Fun<e.1.62636971>} 
5> {E3, S3} = S2(). 
{25,#Fun<e.1.62636971>} 

Answer 4

如果不是因为懒惰，我认为这将在F＃工作：

type Nat = Zero | Succ of Nat 

let rec toLazy x = 
    if x = 0 then Zero 
    else Succ(toLazy(x-1)) 

type Nat with 
    static member (+)(x:Nat, y:Nat) = 
     match x with 
     | Succ(a) -> Succ(a+y) 
     | Zero -> y 
    static member (*)(x:Nat, y:Nat) = 
     match x,y with 
     | _, Zero -> Zero 
     | Zero, _ -> Zero 
     | Succ(a), b -> b + a*b 

module NumericLiteralQ = 
    let FromZero()   = toLazy 0 
    let FromOne()   = toLazy 1 
    let FromInt32(x:int) = toLazy x 

let rec len = function 
    | [] -> 0Q 
    | _::t -> 1Q + len t 

printfn "%A" (len [1..42] < 100Q) 
printfn "%A" (len [while true do yield 1] < 100Q) 

但是因为我们需要偷懒，它扩展到这一点：

let eqLazy<'T> (x:Lazy<'T>) (y:Lazy<'T>) : bool = //' 
    let a = x.Force() 
    let b = y.Force() 
    a = b 

type Nat = Zero | Succ of LazyNat 
and [<StructuralComparison(false); StructuralEqualityAttribute(false)>] 
    LazyNat = LN of Lazy<Nat> with 
     override this.GetHashCode() = 0 
     override this.Equals(o) = 
      match o with 
      | :? LazyNat as other -> 
       let (LN(a)) = this 
       let (LN(b)) = other 
       eqLazy a b 
      | _ -> false 
     interface System.IComparable with 
      member this.CompareTo(o) = 
       match o with 
       | :? LazyNat as other -> 
        let (LN(a)) = this 
        let (LN(b)) = other 
        match a.Force(),b.Force() with 
        | Zero, Zero -> 0 
        | Succ _, Zero -> 1 
        | Zero, Succ _ -> -1 
        | Succ(a), Succ(b) -> compare a b 
       | _ -> failwith "bad" 

let (|Force|) (ln : LazyNat) = 
    match ln with LN(x) -> x.Force() 

let rec toLazyNat x = 
    if x = 0 then LN(lazy Zero) 
    else LN(lazy Succ(toLazyNat(x-1))) 

type LazyNat with 
    static member (+)(((Force x) as lx), ((Force y) as ly)) = 
     match x with 
     | Succ(a) -> LN(lazy Succ(a+ly)) 
     | Zero -> lx 

module NumericLiteralQ = 
    let FromZero()   = toLazyNat 0 
    let FromOne()   = toLazyNat 1 
    let FromInt32(x:int) = toLazyNat x 

let rec len = function 
    | LazyList.Nil -> 0Q 
    | LazyList.Cons(_,t) -> LN(lazy Succ(len t)) 

let shortList = LazyList.of_list [1..42] 
let infiniteList = LazyList.of_seq (seq {while true do yield 1}) 
printfn "%A" (len shortList < 100Q)  // true 
printfn "%A" (len infiniteList < 100Q) // false 

这说明人们为什么只在Haskell中写这些东西。