Манипулируем деревьями в фокусе

Теперь, когда мы можем перемещаться вверх и вниз, давайте созда- дим функцию, изменяющую элемент в корне поддерева, на кото- ром фокусируется застёжка.

modify:: (a –> a) –> Zipper a –> Zipper a modify f (Node x l r, bs) = (Node (f x) l r, bs) modify f (Empty, bs) = (Empty, bs)

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

ghci> let newFocus = modify (\_ –> 'P') (goRight (goLeft (freeTree, [])))

Мы идём влево, затем вправо, а потом изменяем корневой эле- мент, заменяя его на 'P'. Если мы используем оператор –:, это будет читаться ещё лучше:

ghci> let newFocus = (freeTree, []) –: goLeft –: goRight –: modify (\_ –> 'P')

 

Затем мы можем перейти вверх, если захотим, и заменить име- ющийся там элемент таинственным символом 'X':

ghci> let newFocus2 = modify (\_ –> 'X') (goUp newFocus)

Либо можем записать это, используя оператор –: следующим образом:

ghci> let newFocus2 = newFocus –: goUp –: modify (\_ –> 'X')

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

Каждый узел имеет два поддерева, даже если эти поддеревья пусты. Поэтому, фокусируясь на пустом поддереве, мы по крайней мере можем сделать одну вещь: заменить его непустым поддеревом, таким образом прикрепляя дерево к листу. Код весьма прост:

attach:: Tree a –> Zipper a –> Zipper a attach t (_, bs) = (t, bs)

Мы берём дерево и застёжку и возвращаем новую застёжку, фо- кус которой заменён переданным деревом. Можно не только рас- ширять деревья, заменяя пустые поддеревья новыми, но и заменять существующие поддеревья. Давайте прикрепим дерево к дальнему левому краю нашего дерева freeTree:

ghci> let farLeft = (freeTree, []) –: goLeft –: goLeft –: goLeft –: goLeft ghci> let newFocus = farLeft –: attach (Node 'Z' Empty Empty)

Значение newFocus теперь сфокусировано на дереве, которое мы только что прикрепили, а остальная часть дерева находится в «хлебных крошках» в вывернутом наизнанку виде. Если бы мы использовали функцию goUp для прохода всего пути к вершине де- рева, оно было бы таким же деревом, как и 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, а «хвост» является пустым списком [].

ФОКУСИРУЕМСЯ НА СПИСКАХ 479

Давайте создадим застёжку для списков. Чтобы изменить фокус на подсписках списка, мы перемещаемся или вперёд, или назад (тогда как при использова- нии деревьев мы перемещались вверх, влево или вправо). По- мещённой в фокус частью будет подсписок, а кроме того, мы бу- дем оставлять «хлебные крош- ки» по мере нашего движения вперёд.

А из чего состояла бы от- дельная «хлебная крошка» для

списка? Когда мы имели дело с бинарными деревьями, нужно было, чтобы «хлебная крошка» хранила элемент, содержащийся в корне родительского узла, вместе со всеми поддеревьями, которые мы не выбрали. Она также должна была запоминать, куда мы пошли, – влево или вправо. Поэтому требовалось, чтобы в ней содержалась вся имеющаяся в узле информация, за исключением поддерева, на которое мы решили навести фокус.

Списки проще, чем деревья. Нам не нужно запоминать, пошли ли мы влево или вправо, потому что вглубь списка можно пойти лишь одним способом. Поскольку для каждого узла существует только одно поддерево, нам также не нужно запоминать пути, по которым мы не пошли. Кажется, всё, что мы должны запоминать, – это предыдущий элемент. Если у нас есть список вроде [3,4,5] и мы знаем, что предыдущим элементом было значение 2, мы можем пойти назад, просто поместив этот элемент в «голову» нашего спис- ка, получая [2,3,4,5].

Поскольку отдельная «хлебная крошка» здесь – просто элемент, нам на самом деле не нужно помещать её в тип данных, как мы де- лали это, когда создавали тип данных Crumb, использовавшийся за- стёжками для деревьев.

type ListZipper a = ([a], [a])

Первый список представляет список, на котором мы фокусиру- емся, а второй – это список «хлебных крошек». Давайте создадим функции, которые перемещаются вперёд и назад по спискам:

 

goForward:: ListZipper a –> ListZipper a goForward (x:xs, bs) = (xs, x:bs)

 

goBack:: ListZipper a –> ListZipper a goBack (xs, b:bs) = (b:xs, bs)

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

ghci> let xs = [1,2,3,4] ghci> goForward (xs, []) ([2,3,4], [1])

ghci> goForward ([2,3,4], [1])

([3,4], [2,1])

ghci> goForward ([3,4], [2,1])

([4], [3,2,1])

ghci> goBack ([4], [3,2,1])

([3,4], [2,1])

Вы можете видеть, что «хлебные крошки» в случае со списка- ми – просто перевёрнутая часть вашего списка. Элемент, от которо- го мы удаляемся, всегда помещается в «голову» «хлебных крошек». Потом легко переместиться назад, просто вынимая этот элемент из их «головы» и делая его «головой» нашего фокуса. На данном при- мере опять-таки легко понять, почему мы называем это застёжкой: действительно очень напоминает перемещающийся вверх-вниз за- мок застёжки-молнии!

Если бы вы создавали текстовый редактор, можно было бы ис- пользовать список строк для представления строк текста, которые в текущий момент открыты, а затем использовать застёжку, чтобы знать, на какой строке в данный момент установлен курсор. Ис- пользование застёжки также облегчило бы вставку новых строк в любом месте текста или удаление имеющихся строк.