Ocaml List: Implémente les fonctions append et map

Question

J'essaie actuellement d'étendre le programme OCaml d'un ami. C’est une énorme collection de fonctions nécessaires à l’analyse de certaines données. Comme je ne suis pas vraiment un crack OCaml, je suis actuellement bloqué sur une implémentation de liste étrange (pour moi):

type 'a cell = Nil
    | Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;

J'ai compris que cela implémentait une sorte de "paresseux". liste, mais je ne sais absolument pas comment cela fonctionne vraiment. Je dois implémenter une fonction Append et une fonction Map basée sur le type ci-dessus. Quelqu'un a-t-il une idée de comment faire cela?

Toute aide serait vraiment appréciée!

Answer 1

let rec append l1 l2 = 
    match l1 () with
        Nil -> l2 | 
        (Cons (a, l)) -> fun () -> (Cons (a, append l l2));;

let rec map f l =
    fun () -> 
        match l () with
            Nil -> Nil | 
            (Cons (a, r)) -> fun () -> (Cons (f a, map f r));;

L’idée de base de cette implémentation des listes paresseuses est que chaque calcul est encapsulé dans une fonction (le terme technique est une fermeture) via fun () - > X. L’expression x n’est alors évaluée que lorsque la fonction est appliquée à () (la valeur unitaire qui ne contient aucune information).

Answer 2

Il peut être utile de noter que les fermetures de fonctions sont essentiellement équivalentes aux valeurs paresseuses:

lazy n : 'a Lazy.t    <=>    (fun () -> n) : unit -> 'a
force x : 'a          <=>    x () : 'a

Le type 'a llist est donc équivalent à

type 'a llist = 'a cell Lazy.t

c'est-à-dire une valeur de cellule paresseuse.

Une implémentation de carte pourrait être plus logique en termes de définition ci-dessus

let rec map f lst =
  match force lst with
    | Nil -> lazy Nil
    | Cons (hd,tl) -> lazy (Cons (f hd, map f tl))

Traduire cela en fermetures:

let rec map f lst =
  match lst () with
    | Nil -> (fun () -> Nil)
    | Cons (hd,tl) -> (fun () -> Cons (f hd, map f tl))

De même avec append

let rec append a b =
  match force a with
    | Nil -> b
    | Cons (hd,tl) -> lazy (Cons (hd, append tl b))

devient

let rec append a b =
  match a () with
    | Nil -> b
    | Cons (hd,tl) -> (fun () -> Cons (hd, append tl b))

Je préfère généralement utiliser la syntaxe lazy , car elle précise ce qui se passe.

Notez également qu'une suspension paresseuse et une fermeture ne sont pas exactement équivalentes. Par exemple,

let x = lazy (print_endline "foo") in
  force x;
  force x

imprime

foo

alors que

let x = fun () -> print_endline "foo" in
  x ();
  x ()

imprime

foo
foo

La différence est que force calcule la valeur de l'expression exactement une fois .

Answer 3

Oui, les listes peuvent être infinies. Le code donné dans les autres réponses sera ajouté à la fin d'une liste infinie, mais vous ne pouvez écrire aucun programme pouvant observer ce qui est ajouté à la suite d'une liste infinie.