Миран Липовача - Изучай Haskell во имя добра!

Застёжки могут использоваться почти с любой структурой данных, поэтому неудивительно, что они работают с подсписками списков. В конце концов, списки очень похожи на деревья, только узел дерева содержит (или не содержит) элемент и несколько поддеревьев, а узел списка – элемент и лишь один подсписок. Когда мы реализовывали свои собственные списки в главе 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, а «хвост» является пустым списком [].

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

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

Списки проще, чем деревья. Нам не нужно запоминать, по шли ли мы влево или вправо, потому что вглубь списка можно пойти лишь одним способом. Поскольку для каждого узла существует только одно поддерево, нам также не нужно запоминать пути, по которым мы не пошли. Кажется, всё, что мы должны запоминать, – это предыдущий элемент. Если у нас есть список вроде [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])

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

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

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