Ocaml List: Implémente les fonctions append et map
-
08-07-2019 - |
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!
La solution
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).
Autres conseils
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 .
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.