Lista Ocaml: Implementar funciones de agregar y mapear
-
08-07-2019 - |
Pregunta
Actualmente estoy tratando de extender el programa OCaml de un amigo. Es una gran colección de funciones necesarias para algunos análisis de datos. Dado que no soy realmente un crack de OCaml, actualmente estoy atascado en una (para mí) extraña implementación de la Lista:
type 'a cell = Nil
| Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;
He descubierto que esto implementa algún tipo de "perezoso" lista, pero no tengo ni idea de cómo funciona realmente. Necesito implementar un Append y una función de mapa basada en el tipo anterior. ¿Alguien tiene una idea de cómo hacer eso?
¡Cualquier ayuda sería realmente apreciada!
Solución
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));;
La idea básica de esta implementación de listas perezosas es que cada cálculo está encapsulado en una función (el término técnico es un cierre) a través de fun () - > X. La expresión x solo se evalúa cuando la función se aplica a () (el valor unitario, que no contiene información).
Otros consejos
Podría ser útil tener en cuenta que los cierres de funciones son esencialmente equivalentes a valores diferidos:
lazy n : 'a Lazy.t <=> (fun () -> n) : unit -> 'a
force x : 'a <=> x () : 'a
Entonces, el tipo 'a llist
es equivalente a
type 'a llist = 'a cell Lazy.t
es decir, un valor de celda diferida.
Una implementación de mapa podría tener más sentido en términos de la definición anterior
let rec map f lst =
match force lst with
| Nil -> lazy Nil
| Cons (hd,tl) -> lazy (Cons (f hd, map f tl))
Traduciendo eso nuevamente en cierres:
let rec map f lst =
match lst () with
| Nil -> (fun () -> Nil)
| Cons (hd,tl) -> (fun () -> Cons (f hd, map f tl))
Similarmente con append
let rec append a b =
match force a with
| Nil -> b
| Cons (hd,tl) -> lazy (Cons (hd, append tl b))
se convierte
let rec append a b =
match a () with
| Nil -> b
| Cons (hd,tl) -> (fun () -> Cons (hd, append tl b))
Generalmente prefiero usar la sintaxis lazy
, ya que deja más claro lo que está sucediendo.
Tenga en cuenta, además, que una suspensión perezosa y un cierre no son exactamente equivalentes. Por ejemplo,
let x = lazy (print_endline "foo") in
force x;
force x
impresiones
foo
mientras que
let x = fun () -> print_endline "foo" in
x ();
x ()
impresiones
foo
foo
La diferencia es que force
calcula el valor de la expresión exactamente una vez .
Sí, las listas pueden ser infinitas. El código dado en las otras respuestas se agregará al final de una lista infinita, pero no hay ningún programa que pueda escribir que pueda observar lo que se agrega después de una lista infinita.