Jugando con el infinito - aritmética Lazy

Question

Muchos lenguajes de programación modernos nos permiten manejar listas potencialmente infinitas y para realizar ciertas operaciones sobre ellos.

Ejemplo [Python]:

EvenSquareNumbers = ( x * x for x in naturals() if x mod 2 == 0 )

pueden existir

Tales listas porque sólo los elementos que son realmente necesarios se calculan. (Evaluación Lazy)

Me preguntaba por interés si es posible (o incluso se practica en algunos idiomas) para extender el mecanismo de evaluación perezosa a la aritmética.

Ejemplo: Teniendo en cuenta la lista infinita de números pares evens = [ x | x <- [1..], even x ] No pudimos calcular

length evens

ya que el cálculo necesario aquí no terminaría nunca.

Pero en realidad podría determinar que

length evens > 42

sin tener que evaluar todo el término length.

Es esto posible en cualquier idioma? ¿Qué hay de Haskell?

Editar: Para hacer el punto más claro: La pregunta no es acerca de cómo determinar si una lista perezoso es más corto que un número dado. Se trata de utilizar las funciones incorporadas convencionales de manera que la computación numérica se realiza con pereza.

sdcvvc mostró una solución para 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 

Es esto posible también en otros idiomas?

Answer 1

Usted puede crear sus propios números naturales ...

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 continuación, una es cierto, gracias a la evaluación perezosa. Es crucial que len utiliza foldr, foldl no funciona en las listas infinitas. Y se puede hacer un poco de aritmética demasiado (no probado):

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

Por ejemplo, 2 * infinito + 3 es el infinito:

let infinity = Succ infinity

*Main> 2 * infinity + 3
(Succ (Succ (Succ ^cCc (Succ (Succ (SuccInterrupted.

segunda solución

Otra solución es utilizar listas de () como números naturales perezosas.

len = map (const ())
toLazy n = replicate n () 
a = len [1..] > toLazy 42

Hackage .

Editar:. Añadido instancia Num

Edit2:

Traducción de segunda solución a Python:

import itertools

def length(x):
    return itertools.imap(lambda: (), x) 

def to_lazy(n):
    return itertools.chain([()] * n)

Para añadir números, utilizar itertools.chain, multiplicar, utilice itertools.product. Esto no es tan bonita como en Haskell, pero funciona.

En cualquier otro lenguaje estricto con los cierres, se puede simular la pereza utilizando el tipo () -> a en lugar de una. Usando que es posible traducir la primera solución de Haskell a otros idiomas. Esto hará que rápidamente se hace ilegible, sin embargo.

un buen artículo sobre Python uno revestimientos .

Answer 2

Si no fuera por la pereza, creo que esto funcionaría en Fa #:

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)

Pero ya que tenemos que ser perezoso, se expande a lo siguiente:

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

Esto demuestra por qué la gente sólo escriben estas cosas en Haskell.

Answer 3

Puede probablemente lograr lo que desea, tratando de obtener más de 42 elementos de iguala.

Answer 4

No estoy seguro de entender su pregunta, pero vamos a darle una oportunidad. Tal vez usted está buscando para los flujos. Sólo hablo de Erlang, de la familia de lenguas FP, así que ...

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

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

Llamar a la corriente siempre devuelve el siguiente elemento, y una diversión que debe llamar para recuperar el siguiente elemento. De esta manera se logra la evaluación perezosa.

A continuación, puede definir una función is_stream_longer_than como:

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).

Resultados:

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>}