Ответ 1
Это просто незначительная корректировка типа дерева, чтобы сделать определенные операции более эффективными.
Бумага фокусируется (ха-ха) на розовых деревьях - деревьях, узлы которых имеют произвольное количество детей. Код из статьи находится в OCaml, но очень просто перевести на Haskell:
data Rose a = Leaf a | Rose [Rose a]
Вкратце, идея молнии заключается в том, чтобы представлять позицию в структуре данных по ее контексту. Контекст node в розовом дереве состоит из пути, по которому вы взяли дерево, чтобы добраться до родителя node, и путь, который вы взяли по списку братьев и сестер, чтобы достичь самого node.
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 - в настоящее время сосредоточенный node и его братья и сестры - и разбивает их вместе в один список детей. Он забывает о том, с какими node вы смотрели. Соответственно, down фокусирует вас на самом левом ребре текущего фокуса. Если вам нужно пойти up, а затем вернуться к ранее сфокусированному node, вам нужно пройти 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)