Lista Ocaml: Implementar funciones de agregar y mapear

Question

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!

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

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

Answer 2

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 .

Answer 3

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.