6

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

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

这可以用任何语言实现吗？哈斯克尔呢？

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

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

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

4

4 回答 4

8

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

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 * infinity + 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

检查黑客攻击。

编辑：添加实例编号。

编辑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 中那么漂亮，但它确实有效。

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

另请参阅Python one-liners 的一篇不错的文章。

于 2009-09-20T16:32:43.540 回答
3

如果不是因为懒惰，我认为这适用于 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 中编写这些东西。

于 2009-09-20T18:47:14.357 回答
2

您可能可以通过尝试从偶数中获取超过 42 个元素来实现您想要的。

于 2009-09-20T16:01:58.247 回答
1

不确定我是否理解您的问题，但让我们试一试。也许您正在寻找流。我只会说 FP 语言家族之外的 Erlang，所以...

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>}
于 2009-09-20T16:08:34.787 回答