Ocaml Liste: Implementieren append und Kartenfunktionen
-
08-07-2019 - |
Frage
Ich versuche zur Zeit eines Freundes OCaml Programm zu erweitern. Es ist eine riesige Sammlung von Funktionen für einige Datenanalyse benötigt werden .. Da ich nicht wirklich ein OCaml Riss bin ich zur Zeit auf einem bin stecken (für mich) seltsame Liste Umsetzung:
type 'a cell = Nil
| Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;
Ich habe herausgefunden, dass dies eine Art von „lazy“ Liste implementiert, aber ich habe absolut keine Ahnung, wie es wirklich funktioniert. Ich brauche einen anhängen und eine Map-Funktion zur Implementierung auf der oben genannten Art basieren. Hat jemand hätte eine Idee, wie das zu tun?
Jede Hilfe wäre wirklich dankbar!
Lösung
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));;
Die Grundidee dieser Implementierung von faulen Listen ist, dass jede Berechnung in einer Funktion gekapselt ist (der Fachbegriff ist ein Verschluss) über Spaß () -> x. Der Ausdruck x wird dann nur dann ausgewertet, wenn die Funktion () (der Einheitswert, der keine Information enthält) angelegt wird.
Andere Tipps
Es könnte helfen, dass Funktions Verschlüsse sind im wesentlichen äquivalent zu faulen Werte zu beachten:
lazy n : 'a Lazy.t <=> (fun () -> n) : unit -> 'a
force x : 'a <=> x () : 'a
So der Typ 'a llist
entspricht
type 'a llist = 'a cell Lazy.t
d., Ein fauler Zellenwert.
Eine Karte Implementierung könnte mehr Sinn im Hinblick auf die obigen Definition machen
let rec map f lst =
match force lst with
| Nil -> lazy Nil
| Cons (hd,tl) -> lazy (Cons (f hd, map f tl))
Die Übertragung dieser zurück in Schließungen:
let rec map f lst =
match lst () with
| Nil -> (fun () -> Nil)
| Cons (hd,tl) -> (fun () -> Cons (f hd, map f tl))
Ähnlich ist es mit append
let rec append a b =
match force a with
| Nil -> b
| Cons (hd,tl) -> lazy (Cons (hd, append tl b))
wird
let rec append a b =
match a () with
| Nil -> b
| Cons (hd,tl) -> (fun () -> Cons (hd, append tl b))
Ich ziehe es im Allgemeinen die lazy
Syntax zu verwenden, da sie es deutlich macht, was los ist.
Beachten Sie auch, dass eine faule Aufhängung und ein Verschluss ist nicht genau gleichwertig. Zum Beispiel:
let x = lazy (print_endline "foo") in
force x;
force x
druckt
foo
während
let x = fun () -> print_endline "foo" in
x ();
x ()
druckt
foo
foo
Der Unterschied besteht darin, dass force
den Wert des Ausdrucks berechnet genau einmal .
Ja, Sie können die Listen unendlich sein. Der Code in den anderen Antworten gegeben wird bis zum Ende einer unendlichen Liste anzuhängen, aber es gibt kein Programm, das Sie als schreiben können, kann beobachten, was im Anschluss an einer unendlichen Liste angefügt wird.