Lista Ocaml: Implementar acrescentar e mapear funções

Question

Atualmente estou tentando estender programa de OCaml de um amigo. É uma enorme coleção de funções necessárias para uma análise de dados .. Desde que eu não sou realmente um Ocaml rachar Atualmente estou preso em um (para mim) implementação Lista estranho:

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

Eu descobri que isso implementa algum tipo de lista de "preguiçoso", mas eu não tenho absolutamente nenhuma idéia de como ele realmente funciona. Eu preciso implementar um Append e uma função de mapa com base no tipo acima. Alguém tem uma idéia de como fazer isso?

Qualquer ajuda seria muito apreciada!

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

The basic idea of this implementation of lazy lists is that each computation is encapsulated in a function (the technical term is a closure) via fun () -> x. The expression x is then only evaluated when the function is applied to () (the unit value, which contains no information).

Answer 2

It might help to note that function closures are essentially equivalent to lazy values:

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

So the type 'a llist is equivalent to

type 'a llist = 'a cell Lazy.t

i.e., a lazy cell value.

A map implementation might make more sense in terms of the above definition

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

Translating that back into closures:

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

Similarly with append

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

becomes

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

I generally prefer to use the lazy syntax, since it makes it more clear what's going on.

Note, also, that a lazy suspension and a closure are not exactly equivalent. For example,

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

prints

foo

whereas

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

prints

foo
foo

The difference is that force computes the value of the expression exactly once.

Answer 3

Yes, the lists can be infinite. The code given in the other answers will append to the end of an infinite list, but there's no program you can write than can observe what is appended following an infinite list.