>freeTree, но с дополнительным символом >'Z' на дальнем левом краю.Идём прямо на вершину, где воздух чист и свеж!
Создать функцию, которая проходит весь путь к вершине дерева, независимо от того, на чём мы фокусируемся, очень просто. Вот она:
>topMost :: Zipper a –> Zipper a
>topMost (t, []) = (t, [])
>topMost z = topMost (goUp z)
Если наша расширенная тропинка из «хлебных крошек» пуста, это значит, что мы уже находимся в корне нашего дерева, поэтому мы просто возвращаем текущий фокус. В противном случае двигаемся вверх, чтобы получить фокус родительского узла, а затем рекурсивно применяем к нему функцию >topMost.
Итак, теперь мы можем гулять по нашему дереву, двигаясь влево, вправо и вверх, применяя функции >modify и >attach во время нашего путешествия. Затем, когда мы покончили с нашими изменениями, используем функцию >topMost, чтобы сфокусироваться на вершине дерева и увидеть произведённые нами изменения в правильной перспективе.
Фокусируемся на списках
Застёжки могут использоваться почти с любой структурой данных, поэтому неудивительно, что они работают с подсписками списков. В конце концов, списки очень похожи на деревья, только узел дерева содержит (или не содержит) элемент и несколько поддеревьев, а узел списка – элемент и лишь один подсписок. Когда мы реализовывали свои собственные списки в главе 7, то определили наш тип данных вот так:
>data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
Сравните это с определением нашего бинарного дерева – и легко увидите, что списки можно воспринимать в качестве деревьев, где каждый узел содержит лишь одно поддерево.
Список вроде >[1,2,3] может быть записан как >1:2:3:[]. Он состоит из «головы» списка равной >1 и «хвоста», который равен >2:3:[]. 2:3:[] также имеет «голову», которая равна >2, и «хвост», который равен >3:[]. Для >3:[] «голова» равна >3, а «хвост» является пустым списком >[].
Давайте создадим застёжку для списков. Чтобы изменить фокус на подсписках списка, мы перемещаемся или вперёд, или назад (тогда как при использовании деревьев мы перемещались вверх, влево или вправо). Помещённой в фокус частью будет подсписок, а кроме того, мы будем оставлять «хлебные крошки» по мере нашего движения вперёд.
А из чего состояла бы отдельная «хлебная крошка» для списка? Когда мы имели дело с бинарными деревьями, нужно было, чтобы «хлебная крошка» хранила элемент, содержащийся в корне родительского узла, вместе со всеми поддеревьями, которые мы не выбрали. Она также должна была запоминать, куда мы пошли, – влево или вправо. Поэтому требовалось, чтобы в ней содержалась вся имеющаяся в узле информация, за исключением поддерева, на которое мы решили навести фокус.
Списки проще, чем деревья. Нам не нужно запоминать, по шли ли мы влево или вправо, потому что вглубь списка можно пойти лишь одним способом. Поскольку для каждого узла существует только одно поддерево, нам также не нужно запоминать пути, по которым мы не пошли. Кажется, всё, что мы должны запоминать, – это предыдущий элемент. Если у нас есть список вроде