Список Ocaml: выполнить функции добавления и отображения

В настоящее время я пытаюсь расширить программу OCaml для друзей. Это огромная коллекция функций, необходимых для некоторого анализа данных. Так как я не сильно похожа на OCaml, я в настоящее время застрял на (для меня) странной реализации List:

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

Я понял, что это реализует какой-то "ленивый" список, но я абсолютно не знаю, как это работает. Мне нужно реализовать функцию Append и Map, основанную на вышеуказанном типе. Кто-нибудь понял, как это сделать?

Любая помощь будет действительно оценена!

Ответы

Ответ 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));;

Основная идея этой реализации ленивых списков состоит в том, что каждое вычисление инкапсулируется в функцию (технический термин - это замыкание) через fun() → x. Выражение x тогда оценивается только тогда, когда функция применяется к() (значение единицы, которое не содержит информации).

Ответ 2

Это может означать, что закрытие функций по существу эквивалентно ленивым значениям:

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

Итак, тип 'a llist эквивалентен

type 'a llist = 'a cell Lazy.t

т.е. значение ленивой ячейки.

Реализация карты может иметь больше смысла в терминах указанного выше определения

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

Перевод обратно в закрытие:

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

Аналогично append

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

становится

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

Обычно я предпочитаю использовать синтаксис lazy, поскольку он делает более понятным, что происходит.

Обратите также внимание, что ленивая подвеска и закрытие не совсем эквивалентны. Например,

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

печатает

foo

тогда

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

печатает

foo
foo

Разница в том, что force вычисляет значение выражения ровно один раз.

Ответ 3

Да, списки могут быть бесконечными. Код, указанный в других ответах, будет добавлен в конец бесконечного списка, но там нет программы, которую вы можете написать, чем можете наблюдать, что добавляется после бесконечного списка.