Jugar con el infinito: aritméticos vagos

Question

Muchos lenguajes de programación modernos nos permiten manejar listas potencialmente infinitas y realizar ciertas operaciones en ellas.

Ejemplo [Python]:

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

Tales listas pueden existir porque sólo los elementos que son realmente necesarios están computarizada. (Evaluación diferida)

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

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

length evens 

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

Pero en realidad podría determinar que

length evens > 42 

sin tener que evaluar toda la length plazo.

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

Editar: Para aclarar el punto: La pregunta no es sobre cómo determinar si una lista perezosa es más corta que un número dado. Se trata de usar funciones integradas convencionales de forma que el cálculo numérico se realice de forma perezosa.

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 

También es posible esto 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 

entonces A es verdadera , gracias a la evaluación perezosa. Es crucial que len use foldr, foldl no funciona en 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 perezosos.

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

Comprobar Hackage.

Editar: Instancia añadida 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, utilice itertools.chain, multiplicar, utilice itertools.product. Esto no es tan bonito como en Haskell, pero funciona.

En cualquier otro lenguaje estricto con cierres, puede simular la pereza usando el tipo() -> a en lugar de a. Usando eso, es posible traducir la primera solución de Haskell a otros idiomas. Sin embargo, esto se volverá ilegible rápidamente.

Véase también a nice article on Python one-liners.

Answer 2

Probablemente pueda lograr lo que quiere al tratar de obtener más de 42 elementos fuera de los pares.

Answer 3

No estoy seguro si entiendo su pregunta, pero vamos a intentar esto. Quizás estás buscando transmisiones. 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}. 

Llamando la corriente siempre devuelve el siguiente elemento, y una diversión que debería llamar a recuperar el siguiente elemento. De esta forma logras una 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). 

Resultado:

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

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 esto:

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 solo escribe esto en Haskell.