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

Question

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

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

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

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

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

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

Answer 2

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

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

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

type 'a llist = 'a cell Lazy.t

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

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

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 вычисляет значение выражения ровно один раз.

Answer 3

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