Список Ocaml:Реализовать функции добавления и сопоставления
-
08-07-2019 - |
Вопрос
В настоящее время я пытаюсь расширить программу OCaml моего друга.Это огромный набор функций, необходимых для некоторого анализа данных..Поскольку я на самом деле не взломщик OCaml, я в настоящее время застрял на (для меня) странной реализации списка:
type 'a cell = Nil
| Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;
Я выяснил, что это реализует какой-то "ленивый" список, но я абсолютно понятия не имею, как это работает на самом деле.Мне нужно реализовать функцию Append и Map на основе вышеуказанного типа.У кого-нибудь есть идея, как это сделать?
Любая помощь была бы действительно оценена!
Решение
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 вычисляется только тогда, когда функция применяется к () (значение единицы, которое не содержит информации).
Другие советы
Возможно, полезно отметить, что замыкания функций по существу эквивалентны отложенным значениям:
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
вычисляет значение выражения ровно один раз.
Да, списки могут быть бесконечными. Код, приведенный в других ответах, будет добавлен в конец бесконечного списка, но нет программы, которую вы можете написать, которая могла бы наблюдать за тем, что добавляется после бесконечного списка.