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

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.

Возможно ли это на любом языке? А как насчет Хаскелла?

Редактировать: Чтобы прояснить ситуацию: вопрос не в том, как определить, является ли ленивый список короче заданного числа. Речь идет об использовании обычных встроенных функций таким образом, что числовые вычисления выполняются лениво.

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

Проверка Взлом .

Редактировать: Добавлен экземпляр 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, но работает.

На любом другом строгом языке с замыканиями вы можете имитировать лень, используя type () -> a вместо a. Используя это, можно перевести первое решение с Haskell на другие языки. Однако это быстро станет нечитаемым.

См. Также хорошая статья об однострочниках Python .

Answer 2

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

Это показывает, почему люди пишут этот материал только на Хаскеле.

Answer 3

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

Answer 4

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