Ocaml Liste: Implementieren append und Kartenfunktionen

Question

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!

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

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.

Answer 2

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 .

Answer 3

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.