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

Мне часто говорят, что, используя модуль 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.


lazy-evaluation ocaml
person Russell O'Connor    schedule 27.04.2011    source источник
comment
Перво-наперво, тип - 'a dlist, а не 'a DList. ;)   -  person Jeff Mercado    schedule 28.04.2011

Ответы (3)


arrow_upward
12
arrow_downward

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

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
person Victor Nicollet    schedule 28.04.2011

arrow_upward
7
arrow_downward

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

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

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

person Gilles 'SO- stop being evil'    schedule 27.04.2011

arrow_upward

arrow_downward

person    schedule
comment
Это не так. Он строит круговой двусвязный список вместо списка с завершающим нулем. Это хорошо, но не совсем то, о чем я просил. Что еще более важно, он не может связать себя узами брака и вместо этого строит ленивое бесконечное дерево, которое с точки зрения наблюдений эквивалентно тому, что я хочу, но оно не использует ограниченную память. В частности, left (right dlist) не будет тем же объектом, что и dlist. - person Russell O'Connor; 28.04.2011