Какова структура данных для наборов Clojure?

Недавно я слушал интервью Rich Hickey на Радио Software Engineering. Во время интервью Рич упомянул, что коллекции Clojure реализованы как деревья. Я надеюсь реализовать постоянные структуры данных на другом языке и хотел бы понять, как реализуются наборы и Clojure другие постоянные структуры данных.

Что будет выглядеть дерево в каждой точке в следующем сценарии?

  • Создайте набор {1 2 3}

  • Создайте объединение {1 2 3} и {4}

  • Создайте разницу между {1 2 3 4} и {1}

Я хотел бы понять, как сгенерированы три сета ({1 2 3}, {1 2 3 4} и {2 3 4}), и как обрабатываются "удаления".

Я также хотел бы узнать максимальное количество ветвей, которое может иметь node. Рич упомянул в интервью, что деревья мелкие, поэтому предположительно коэффициент ветвления больше двух.

Ответы

Ответ 1

Вам, вероятно, нужно прочитать работу Фила Багвелла. Его исследования в структурах данных являются основой постоянных структур данных Clojure, Haskell и Scala.

Есть этот разговор Фила в Clojure/Conj: http://www.youtube.com/watch?v=K2NYwP90bNs

Существуют также некоторые документы:

Вы также можете прочитать чисто функциональные структуры данных Криса Окасаки. Этот пост в блоге рассказывает о книге: http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

Ответ 2

Вы действительно должны читать Clojure Программирование, он подробно описывает это, включая фотографии. Вкратце, однако, коллекции - это глубины первых поисков через деревья. Мы можем показать ваши примеры следующим образом:

(def x #{1 2 3})

x
|
| \
|\ 3
1 \
   2

(def y (conj x 4))

 x  y
 | / \
 | \   4
 |\ 3
 1 \
    2

 (def z (difference y #{1}))

 x  y
 | / \
 | \  4
 |\ 3
 1/\
z-  2

Обратите внимание, что это просто индикативно, я не говорю, что это именно макет Clojure используется внутри. Это суть, хотя.

Ответ 3

Мне нравятся рисунки и объяснения SCdF, но если вы ищете больше глубины, вы должны прочитать отличную серию статей о структурах данных Clojure на Higher-Order. Он подробно объясняет, как работают карты Clojure, а Clojure - просто тонкий слой поверх своих карт: #{:a :b} реализуется как обтекание {:a :a, :b :b}.