Проигрывание с бесконечностью - Ленивая арифметика

Если бы не лень, я думаю, это сработало бы в 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.

Вы, вероятно, сможете добиться желаемого, если попытаетесь получить более 42 элементов из эвенов.

Не уверен, что я понимаю ваш вопрос, но давайте попробуем. Возможно, вы ищете стримы. Я говорю только на Erlang, из семейства языков 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>}