Как реализовать дерево B + в Haskell?

Дерево B + имеет связанные узлы листа. Просмотр структуры указателя дерева B + в качестве ориентированного графика не является циклическим. Но игнорируя направления указателей и рассматривая их как неориентированные связанные узлы листа, создает циклы на графике.

В Haskell, как можно было бы построить лист как дочерний элемент родительского внутреннего node и одновременно следующую ссылку из соседнего листа node. Как можно сделать это с помощью алгебраических типов данных Haskell? Похоже, что Haskell ADT вообще создает циклические структуры, которые трудно выразить.

Ответ 1

Вот идея для (неизменной/ "изменчивой" -и-реконструкции/zipperable) Представление ADT (с участием immutable векторы):

module Data.BTree.Internal where

import Data.Vector

type Values v = Vector v

type Keys k = Vector k

data Leaf k v
  = Leaf
    { _leafKeys   :: !(Keys k)
    , _leafValues :: !(Values v)
    , _leafNext   :: !(Maybe (Leaf k v)) -- @[email protected] is lazy in @[email protected], so this strict mark
                                         -- is ok for tying-the-knot stuff.
    -- , _leafPrev   :: !(Maybe (Leaf k v))
    -- ^ for doubly-linked lists of leaves
    }

type Childs k v = Vector (BTree k v)

data Node k v
  = Node
    { _nodeKeys   :: !(Keys k)
    , _nodeChilds :: !(Childs k v)
    }

data BTree k v
  = BTreeNode !(Node k v)
  | BTreeLeaf !(Leaf k v)

newtype BTreeRoot k v
  = BTreeRoot (BTree k v)

Это должно быть внутренним, так что неправильное использование необработанных конструкторов, аксессуаров или сопоставления шаблонов не разрушит дерево.
Keys, Values, Childs может быть добавлено управление длиной (с проверкой времени выполнения или, возможно, с GADT и т.д.).

И для интерфейса:

module Data.BTree ( {- appropriate exports -} ) where

import Data.Vector
import Data.BTree.Internal

-- * Building trees: "good" constructors.

keys :: [k] -> Keys k
keys = fromList

values :: [v] -> Values v
values = fromList

leaves :: [Leaf k v] -> Childs k v
leaves = fromList . fmap BTreeLeaf

leaf :: Keys k -> Values v -> Maybe (Leaf k v) -> Leaf k v
-- or
-- leaf :: Keys k -> Values v -> Maybe (Leaf k v) -> Maybe (Leaf k v) -> Leaf k v
-- for doubly-linked lists of leaves
leaf = Leaf

node :: Keys k -> Childs k v -> BTree k v
node ks = BTreeNode . Node ks

-- ...

-- * "Good" accessors.

-- ...

-- * Basic functions: insert, lookup, etc.

-- ...

Затем этот вид дерева:

можно построить как

test :: BTree Int ByteString
test = let
  root  = node (keys [3, 5]) (leaves [leaf1, leaf2, leaf3])
  leaf1 = leaf (keys [1, 2]) (values ["d1", "d2"]) (Just leaf2)
  leaf2 = leaf (keys [3, 4]) (values ["d3", "d4"]) (Just leaf3)
  leaf3 = leaf (keys [5, 6, 7]) (values ["d5", "d6", "d7"]) Nothing
  in root

Этот метод, известный как "привязка узла" . Листья могут циклироваться:

  leaf1 = leaf (keys [1, 2]) (values ["d1", "d2"]) (Just leaf2)
  leaf2 = leaf (keys [3, 4]) (values ["d3", "d4"]) (Just leaf3)
  leaf3 = leaf (keys [5, 6, 7]) (values ["d5", "d6", "d7"]) (Just leaf1)

или дважды связан (предполагая _leafPrev и соответствующую функцию leaf):

  leaf1 = leaf (keys [1, 2]) (values ["d1", "d2"]) (Just leaf2) (Just leaf3)
  leaf2 = leaf (keys [3, 4]) (values ["d3", "d4"]) (Just leaf3) (Just leaf1)
  leaf3 = leaf (keys [5, 6, 7]) (values ["d5", "d6", "d7"]) (Just leaf1) (Just leaf2)

Полностью изменяемое представление также возможно с изменяемыми векторами и изменчивым ссылки:

type Values v = IOVector v

type Keys k = IOVector k

type Childs k v = IOVector (BTree k v)

    , _leafNext   :: !(IORef (Maybe (Leaf k v)))

и т.д., в основном то же самое, но используя IORef и IOVector, работающие в IO monad.

Ответ 2

Возможно, это похоже на то, что вы ищете?

data Node key value
    = Empty
    | Internal key [Node key value] -- key and children
    | Leaf value (Node key value) -- value and next-leaf
    deriving Show

let a = Leaf 0 b
    b = Leaf 1 c
    c = Leaf 2 d
    d = Leaf 3 Empty
in  Internal [Internal 0 [a,b], Internal 2 [c,d]]

Проблема с этим определением состоит в том, что он не препятствует тому, чтобы следующий лист в Leaf node был Internal node.

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

let a = 0:a

Вы даже можете сделать взаимную рекурсию, которая еще более циклична:

let a = 0:b
    b = 1:a
in  a