Двойная очередь в OCaml - какая идея?

Question

я наткнулся на эту реализацию дека:

type 'a elem = { mutable l1 : 'a elem; mutable l2 : 'a elem; v : 'a option } 
type 'a queue = { mutable front : 'a elem; mutable back : 'a elem } 

let init() = 
    let rec g1 = { l1 = g1; l2 = g2; v = None} 
    and  g2 = { l1 = g2; l2 = g1; v = None} 
    in 
     { front = g1; back = g2 } 

let is_empty q = 
    let f = q.front 
    and b = q.back 
    in 
     f.l2 == b 

let put_between p q x = 
    let r = { l1 = p; l2 = q; v = Some x } 
    in begin 
     if p.l1 == q then p.l1 <- r else p.l2 <- r; 
     if q.l1 == p then q.l1 <- r else q.l2 <- r 
    end 

Я не очень понимаю, что главная идея этой реализации, основной концепции? Не могли бы вы объяснить мне это? Почему мы используем эти рекурсивные записи друг к другу?

Answer 1

Во-первых, обратите внимание, что это недопустимый код OCaml! Это может быть код с более ранней фазы языка. Чтобы сделать его действительным, замените альфа-символы на 'a и замените Val на Some.

Чтобы немного расширить то, что говорит @Lee.

Это простая перепрограммируемая реализация двухсторонней очереди (или deque), например, то, что вы бы кодировали на языке с обычными указателями (например, C).

Есть только несколько конкретных идей, которые я могу видеть, кроме того, что ссылки остаются прямыми.

1. На каждом конце дека есть заголовок (то, что @Lee называет часовым). Таким образом, пустой объект имеет два узла. Из-за двухсторонней связи каждый узел указывает на другой. (Это, вероятно, рекурсия, о которой вы говорите.)

2. Поскольку OCaml строго типизирован, все узлы должны быть одного типа, даже заголовки в конце. Поскольку заголовки не имеют в них значения, вам нужно использовать значение 'a option. Другими словами, вам нужно разрешить узлы без значения в них.

3. Абонент put_between должен поставлять два соседних узла, но они могут поставляться в любом порядке.

4. Код использует «физическое равенство» (==) для проверки идентичности узлов. Это опасно для OCaml, но здесь это правильно. Переменные значения можно сравнить с == с более или менее результатом, который вы ожидаете от сравнения указателей на императивном языке.

Одной из причин изучения OCaml является изучение функционального программирования. Этот код не подходит для этого, поскольку (как я уже сказал) это изменчивый. Вы можете увидеть некоторые фактические функциональные реализации deque в главе 5 Chris Okasaki's PhD thesis. (Вы также можете купить свою книгу, которая является многолетним фаворитом.)