Jouer avec l'infini - Lazy Arithmétique

Question

De nombreux langages de programmation modernes nous permettent de gérer des listes potentiellement infinies et d'effectuer certaines opérations sur eux.

Exemple [python]:

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

Ces listes peuvent exister parce que seuls les éléments qui sont effectivement nécessaires sont calculés. (Évaluation Lazy)

Je me demandais simplement sur l'intérêt que ce soit possible (ou même pratiqué dans certaines langues) pour étendre le mécanisme d'évaluation paresseux pour Arithmétique.

Exemple: Compte tenu de la liste infinie des nombres pairs evens = [ x | x <- [1..], even x ] Nous ne pouvions pas calculer

length evens

depuis le calcul requis ici ne serait jamais fin.

Mais on pourrait effectivement déterminer que

length evens > 42

sans avoir à évaluer toute la durée de length.

Est-ce possible dans toutes les langues? Qu'en est-il Haskell?

Edit: Pour le point plus clair: La question ne porte pas sur la façon de déterminer si une liste paresseux est plus court qu'un nombre donné. Il est sur l'utilisation de fonctions intégrées classiques d'une manière que le calcul numérique se fait paresseusement.

sdcvvc a montré une solution pour 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 

Est-ce possible dans d'autres langues?

Answer 1

Vous pouvez créer vos propres nombres naturels ...

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

Alors un est vrai, grâce à l'évaluation paresseuse. Il est crucial que len utilise foldr, foldl ne fonctionne pas sur les listes infinies. Et vous pouvez le faire aussi (non testé) un peu d'arithmétique:

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

Par exemple, 2 * infini + 3 est infini:

let infinity = Succ infinity

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

Deuxième solution

Une autre solution consiste à utiliser des listes de () sous forme de nombres naturels paresseux.

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

Vérifier Hackage .

Modifier. Ajouté par exemple Num

Edit2:

Traduction du deuxième solution à python:

import itertools

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

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

Pour ajouter des numéros, utilisez itertools.chain, multiplier, utiliser itertools.product. Ce n'est pas aussi jolie que dans Haskell, mais cela fonctionne.

Dans une autre langue stricte avec des fermetures, vous pouvez simuler la paresse en utilisant le type () -> a au lieu d'un. Utilise qu'il est possible de traduire la première solution de Haskell à d'autres langues. Cela prendra rapidement illisible, cependant.

Voir aussi un bel article sur Python de un doublures .

Answer 2

S'il n'y avait pas la paresse, je pense que cela fonctionnerait en 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)

Mais puisque nous devons être paresseux, il se développe à ceci:

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

Cela montre pourquoi les gens écrivent que ce genre de choses dans Haskell.

Answer 3

Vous pouvez probablement obtenir ce que vous voulez en essayant d'obtenir plus de 42 éléments sur Evens.

Answer 4

Je ne sais pas, je comprends votre question, mais nous allons essayer ce. Peut-être que vous êtes à la recherche pour les flux. Je ne parle que Erlang, de la famille des langues FP, alors ...

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

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

Appeler le flux renvoie toujours l'élément suivant, et un amusement vous devez appeler pour récupérer l'élément suivant. De cette façon, vous obtenez l'évaluation paresseuse.

Ensuite, vous pouvez définir une fonction is_stream_longer_than comme:

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

Résultat:

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