Создание двусвязного списка из списка в OCaml - PullRequest
Новая
       24

Создание двусвязного списка из списка в OCaml

15 голосов
/ 28 апреля 2011

Мне часто говорят, что с помощью модуля Lazy в OCaml можно делать все, что можно, на ленивом языке, таком как Haskell. Чтобы проверить это утверждение, я пытаюсь написать функцию, которая преобразует обычный список в статический двусвязный список в ocaml. 

type 'a dlist = Dnil | Dnode of 'a dlist * 'a * 'a dlist

Учитывая этот тип, я могу вручную создать несколько статических двусвязных списков: 

let rec l1 = Dnode (Dnil,1,l2)
    and l2 = Dnode   (l1,2,l3)
    and l3 = Dnode   (l2,3,Dnil)

но я бы хотел написать функцию типа 'a list -> 'a dlist, которая при любом списке создает статический двусвязный список в OCaml. Например, для [1;2;3] он должен вывести что-то эквивалентное l1 выше.

Алгоритм довольно прост в написании на Haskell: 

data DList a = Dnil | Dnode (DList a) a (DList a)

toDList :: [a] -> DList a
toDList l = go Dnil l
 where
  go _ [] = Dnil
  go h (x:xs) = let r = Dnode h x (go r xs) in r

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

Ответы [ 3 ]

12 голосов
/ 28 апреля 2011

Если вы строите свой связанный список в порядке справа налево (как для обычных списков), то левый элемент каждого узла будет построен только после того, как этот узел будет построен. Вы должны представить это, сделав левый элемент ленивым, что означает «это значение будет построено позже»: 

type 'a dlist = 
  | Dnil
  | Dnode of 'a dlist Lazy.t * 'a * 'a dlist

Получив это, создайте каждый узел как ленивое значение, используя рекурсивное определение, которое передает ленивый (все еще неструктурированный) узел в вызов функции, который создает следующий узел (чтобы он имел доступ к предыдущему узлу). На самом деле все проще, чем кажется: 

let dlist_of_list list = 
  let rec aux prev = function
    | [] -> Dnil
    | h :: t -> let rec node = lazy (Dnode (prev, h, aux node t)) in 
                Lazy.force node
  in
  aux (Lazy.lazy_from_val Dnil) list
7 голосов
/ 28 апреля 2011

Вы можете построить только циклическую неизменяемую строгую структуру данных формы, которая определяется во время компиляции. Я не собираюсь определять или доказывать это формально, но, интуитивно говоря, после создания структуры данных ее форма не изменится (поскольку она неизменна). Таким образом, вы не можете добавить в цикл. И если вы создаете какой-либо элемент цикла, вам нужно создать все другие элементы цикла одновременно, потому что у вас не может быть никакого висящего указателя.

Ocaml может делать то же, что и Haskell, но вам нужно задействовать модуль Lazy! В отличие от Haskell, структуры данных ML являются строгими, если не указано иное. Ленивая структура данных имеет фрагменты типа 'a Lazy.t. (ML в этом конкретном вопросе более точен, чем в Haskell.) Ленивые структуры данных позволяют строить циклы, используя предварительно висячие указатели (чьи связанные значения автоматически создаются при первом разыменовании указателя). 

type 'a lazy_dlist_value =
  | Dnil
  | Dnode of 'a lazy_dlist_value * 'a * 'a lazy_dlist_value
 and 'a lazy_dlist = 'a lazy_dlist_value Lazy.t

Другой распространенный способ иметь циклические структуры данных - это использовать изменяемые узлы. (На самом деле, сторонники строгого программирования могут рассматривать ленивые структуры данных как особый случай изменчивых структур данных, которые не слишком сильно нарушают ссылочную прозрачность.) 

type 'a mutable_dlist_value =
  | Dnil
  | Dnode of 'a mutable_dlist_value * 'a * 'a mutable_dlist_value
 and 'a mutable_dlist = 'a mutable_dlist_value ref

Циклические структуры данных в основном полезны, когда в них участвует хотя бы один изменяемый компонент, одна функция (замыкание) или иногда модули. Но у компилятора не было бы никаких причин применять это - циклические строгие неизменяемые структуры данных первого порядка - это просто особый случай, который иногда может быть полезен.

2 голосов
/ 28 апреля 2011 
type 'a dlist = Dnil | Dnode of 'a dlist Lazy.t * 'a * 'a dlist Lazy.t
let rec of_list list = match list with
    [] -> Dnil
    | x :: [] ->
        let rec single () = Dnode (lazy (single ()), x, lazy (single ()))
        in single ()
    | x :: y -> Dnode (
        lazy (
            of_list (match List.rev list with
                [] | _ :: [] -> assert false
                | x :: y -> x :: List.rev y
            )
        ),
        x,
        lazy (
            of_list (match list with
                [] | _ :: [] -> assert false
                | x :: y -> y @ x :: []
            )
        )
    )
let middle dlist = match dlist with
    Dnil -> raise (Failure "middle")
    | Dnode (_, x, _) -> x
let left dlist = match dlist with
    Dnil -> raise (Failure "left")
    | Dnode (x, _, _) -> Lazy.force x
let right dlist = match dlist with
    Dnil -> raise (Failure "right")
    | Dnode (_, _, x) -> Lazy.force x
...