Elenco Ocaml: implementa le funzioni append e map

Question

Attualmente sto cercando di estendere il programma OCaml di un amico. È un'enorme raccolta di funzioni necessarie per l'analisi dei dati. Dato che non sono proprio un crack OCaml, sono attualmente bloccato su una (per me) strana implementazione dell'elenco:

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

Ho capito che questo implementa una sorta di "pigro" elenco, ma non ho assolutamente idea di come funzioni davvero. Ho bisogno di implementare un'appendice e una funzione mappa basata sul tipo sopra. Qualcuno ha idea di come farlo?

Qualsiasi aiuto sarebbe davvero apprezzato!

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'idea di base di questa implementazione di liste pigre è che ogni calcolo è incapsulato in una funzione (il termine tecnico è una chiusura) tramite fun () - > X. L'espressione x viene quindi valutata solo quando la funzione viene applicata a () (il valore dell'unità, che non contiene informazioni).

Answer 2

Potrebbe essere utile notare che le chiusure di funzioni sono sostanzialmente equivalenti a valori pigri:

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

Quindi il tipo 'a llist è equivalente a

type 'a llist = 'a cell Lazy.t

ovvero un valore di cella pigro.

Un'implementazione della mappa potrebbe avere più senso in termini di definizione sopra

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

Traducendolo nuovamente in chiusure:

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

Allo stesso modo con append

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

diventa

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

In genere preferisco usare la sintassi lazy , poiché rende più chiaro cosa sta succedendo.

Nota, inoltre, che una sospensione pigra e una chiusura non sono esattamente equivalenti. Ad esempio,

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

stampe

foo

, mentre

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

stampe

foo
foo

La differenza è che force calcola il valore dell'espressione esattamente una volta .

Answer 3

Sì, le liste possono essere infinite. Il codice fornito nelle altre risposte verrà aggiunto alla fine di un elenco infinito, ma non esiste un programma che puoi scrivere che possa osservare ciò che viene aggiunto dopo un elenco infinito.