Ocaml List: реализовать функции добавления и отображения - PullRequest
Новая
       31

Ocaml List: реализовать функции добавления и отображения

11 голосов
/ 10 января 2009

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

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

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

Любая помощь будет принята с благодарностью!

Ответы [ 3 ]

7 голосов
/ 10 января 2009

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

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

Аналогично с добавлением 

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
* +1032 * тогда 
let x = fun () -> print_endline "foo" in
  x ();
  x ()

печать 

foo
foo

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

7 голосов
/ 10 января 2009 
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 вычисляется только тогда, когда функция применяется к () (значение единицы, которое не содержит информации).

1 голос
/ 10 января 2009

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

...