В статье под названием «Застежка-молния» Хьюэта он также упоминает шрамы как разновидность застежек-молний. По сравнению с застежками-молниями, которые стали широко известны в сообществе Haskell, о шрамах почти ничего не слышно. Информации о них в самой газете и где-либо в Интернете очень мало из того, что я мог найти.
Поэтому я должен спросить, они просто бесполезны или есть что-то, для чего они полезны, но большинство людей просто не знают о них?
Это всего лишь небольшая корректировка типа дерева, чтобы сделать некоторые операции более эффективными.
Статья фокусируется (ха-ха) на розовых деревьях — деревьях, узлы которых имеют произвольное количество дочерних элементов. Код из статьи написан на OCaml, но его перевод на Haskell не требует особых настроек:
data Rose a = Leaf a | Rose [Rose a]
Кратко напомним, что идея застежек-молний состоит в том, чтобы представлять позицию в структуре данных с помощью ее контекста. Контекст узла в розовом дереве состоит из пути, который вы выбрали по дереву, чтобы добраться до родителя узла, и пути, который вы выбрали по списку братьев и сестер, чтобы добраться до самого узла.
data Path a = Top | Node (Path a) [Rose a] [Rose a]
data Pos a = Pos { focus :: Rose a, path :: Path a }
Это позволяет вам увеличить позицию в дереве, не забывая, где вы были, пройдя right и down, а затем перестроить дерево, отступив left и уменьшив масштаб up.
right, down, left, up :: Pos a -> Maybe (Pos a)
right (Pos _ Top) = Nothing
right (Pos _ (Node _ _ [])) = Nothing
right (Pos t (Node p ls (r:rs))) = Just $ Pos r (Node p (t:ls) rs)
down (Pos (Leaf _) _) = Nothing
down (Pos (Rose []) _) = Nothing
down (Pos (Rose (t:ts)) p) = Just $ Pos t (Node p [] ts)
left (Pos _ Top) = Nothing
left (Pos _ (Node _ [] _)) = Nothing
left (Pos t (Node p (l:ls) rs) = Just $ Pos l (Node p ls (t:rs))
up (Pos _ Top) = Nothing
up (Pos t (Node p l r)) = Just $ Pos (Rose (l ++ t:r)) p
Посмотрите на определение up. Он берет t, l и r — узел, сфокусированный в данный момент, и его братьев и сестер — и объединяет их вместе в один список дочерних узлов. Он забывает, на какой узел вы смотрели. Соответственно, down фокусирует вас на крайнем левом дочернем элементе текущего фокуса. Если вам нужно пройти up, а затем вернуться к ранее сфокусированному узлу, вам нужно пройти right по списку обратно туда, где вы были, что составляет операцию O(n).
Идея Юэта оставить «шрамы» на дереве состоит в том, чтобы сделать более удобным возвращение к ранее сфокусированному ребенку. Он снабжает конструктор Rose собственным фокусом, заменяя список дочерних элементов застежкой-молнией списка.
data SRose a = -- for "scarred rose"
SLeaf a
| SEmpty -- replaces (Rose [])
| SRose [SRose a] (SRose a) [SRose a]
Типы Path и Pos остаются без изменений:
data SPath a = STop | SNode (SPath a) [SRose a] [SRose a]
data SPos a = SPos { sfocus :: Rose a, spath :: SPath a }
Теперь, когда вы идете up, а затем обратно down, вы не забываете, на что раньше смотрели.
up' (SPos _ STop) = Nothing
up' (SPos t (SNode p l r)) = Just $ SPos (SRose l t r) p
down' (SPos (SLeaf _) _) = Nothing
down' (SPos SEmpty _) = Nothing
down' (SPos (SRose l t r) p) = Just $ SPos t (SNode p l r)
