Lista de Ocaml: implementar funciones de agregar y asignar

Question

Actualmente estoy tratando de ampliar el programa OCaml de un amigo. Es una gran colección de funciones necesarias para algunos análisis de datos .. Como yo no soy realmente una grieta OCaml Actualmente estoy atascado en un (para mí) extraña aplicación de lista:

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

He descubierto que esto implementa una especie de lista "floja", pero no tengo ni idea de cómo funciona realmente. Necesito implementar una función Agregar y una función de mapa en función del 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 aplicación de listas perezosos es que cada cálculo se encapsula en una función (el término técnico es un cierre) a través de la diversión() -> 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 ayudar señalar que los cierres de función son esencialmente equivalentes a los valores perezosos:

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

lo que el tipo 'a llist es equivalente a

type 'a llist = 'a cell Lazy.t 

es decir, un valor de celda perezoso.

Una implementación 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)) 

Translating que nuevamente dentro de los cierres:

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

Lo mismo ocurre con append

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

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, también, que una suspensión floja y un cierre no son exactamente equivalente. Por ejemplo,

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

grabados

foo 

mientras

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

grabados

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 proporcionado 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 adjunta después de una lista infinita.