Lista Ocaml: funkcje dołączania i mapowania narzędzia

Question

Obecnie próbuję rozszerzyć program OCaml przyjaciela. Jest to ogromny zbiór funkcji potrzebnych do jakiejś analizy danych .. Ponieważ nie jestem naprawdę pęknięcie OCaml jestem obecnie zatrzymany na (dla mnie) dziwne realizacji listy:

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

Mam zorientowali się, że to implementuje jakąś "leniwą" listę, ale absolutnie nie mam pojęcia, jak to naprawdę działa. Muszę zaimplementować funkcję Append i Map opartą na powyższym typie. Czy ktoś ma pomysł, jak to zrobić?

Każda pomoc będzie naprawdę doceniona!

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

Podstawową ideą tej realizacji leniwych list jest to, że każdy obliczeń jest zawarta w funkcji (termin techniczny jest zamknięcie) poprzez zabawę() -> x. Wyrażenie x jest wówczas oceniane tylko wtedy, gdy funkcja jest zastosowana do() (wartość jednostki, która nie zawiera żadnych informacji).

Answer 2

To może pomóc, aby pamiętać, że zamknięcia funkcyjne są zasadniczo równoważne wartości leniwych:

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

Więc typ 'a llist jest równoważna

type 'a llist = 'a cell Lazy.t 

czyli leniwe wartości komórki.

Implementacja mapa może więcej sensu w odniesieniu do powyższej definicji

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

tłumaczenia, że ​​z powrotem do zamknięć:

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

podobnie z append

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

staje

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

Generalnie wolę używać składni lazy, ponieważ pozwala to lepiej zrozumieć, co się dzieje.

Należy również zauważyć, że leniwy układ zawieszenia i zamknięcie nie są równoważne z dokładnie taką, jaką jest. Na przykład,

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

drukuje

foo 

podczas gdy

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

drukuje

foo 
foo 

Różnica polega na tym, że force oblicza wartość wyrażenia dokładnie raz.

Answer 3

Tak, listy mogą być nieskończone.Kod podany w innych odpowiedziach zostanie dołączony do końca nieskończonej listy, ale nie ma programu, który można napisać, niż można obserwować, co jest dołączane po nieskończonej liście.