Lista Ocaml: Implementar acrescentar e mapear funções
-
08-07-2019 - |
Pergunta
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!
Solução
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).
Outras dicas
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.
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.