Хотя чистота языка Haskell даёт море преимуществ, вместе с тем он заставляет нас решать некоторые проблемы не так, как мы решали бы их в нечистых языках.
Из-за прозрачности ссылок одно значение в языке Haskell всё равно что другое, если оно представляет то же самое. Поэтому если у нас есть дерево, заполненное пятёрками (или, может, пятернями?), и мы хотим изменить одну из них на шестёрку, мы должны каким-то образом понимать, какую именно пятёрку в нашем дереве мы хотим изменить. Нам нужно знать, где в нашем дереве она находится. В нечистых языках можно было бы просто указать, где в памяти находится пятёрка, и изменить её. Но в языке Haskell одна пятёрка – всё равно что другая, поэтому нельзя проводить различие исходя из их расположения в памяти.
К тому же на самом деле мы не можем что-либо изменять. Когда мы говорим, что «изменяем дерево», то на самом деле имеем в виду, что мы берём дерево и возвращаем новое, аналогичное первоначальному, но немного отличающееся.
Одна вещь, которую мы можем сделать, – запомнить путь от корня дерева до элемента, который следует изменить. Мы могли бы сказать: «Возьми это дерево, пойди влево, пойди вправо, а затем опять влево и измени находящийся там элемент». Хотя это и работает, но может быть неэффективно. Если позднее мы захотим изменить элемент, находящийся рядом с элементом, изменённым нами ранее, нам снова нужно будет пройти весь путь от корня дерева до нашего элемента!
В этой главе вы увидите, как взять некую структуру данных и снабдить её тем, что называется застёжкой, чтобы фокусироваться на части структуры данных таким образом, который делает изменение её элементов простым, а прохождение по ней – эффективным. Славно!
Прогулка
Как вы узнали на уроках биологии, есть множество различных деревьев, поэтому давайте выберем зёрнышко, которое мы используем, чтобы посадить наше. Вот оно:
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
Наше дерево или пусто, или является узлом, содержащим элемент и два поддерева. Вот хороший пример такого дерева, которое я отдаю вам, читатель, просто задаром!
freeTree :: Tree Char
freeTree =
Node 'P'
(Node 'O'
(Node 'L'
(Node 'N' Empty Empty)
(Node 'T' Empty Empty)
)
(Node 'Y'
(Node 'S' Empty Empty)
(Node 'A' Empty Empty)
)
)
(Node 'L'
(Node 'W'
(Node 'C' Empty Empty)
(Node 'R' Empty Empty)
)
(Node 'A'
(Node 'A' Empty Empty)
(Node 'C' Empty Empty)
)
)
А вот это дерево, представленное графически:
Заметили символ W в дереве? Предположим, мы хотим заменить его символом P. Как нам это сделать? Ну, один из подходящих способов – сопоставление нашего дерева с образцом до тех пор, пока мы не найдём элемент, сначала двигаясь вправо, а затем влево. Вот соответствующий код:
changeToP :: Tree Char –> Tree Char
changeToP (Node x l (Node y (Node _ m n) r)) = Node x l (Node y (Node 'P' m n) r)
Тьфу, какая гадость! Это не только некрасиво, но к тому же несколько сбивает с толку. Что здесь на самом деле происходит? Мы сопоставляем наше дерево с образцом и даём его корневому элементу идентификатор x (который превращается в символ 'P' из корня), а левому поддереву – идентификатор l. Вместо того чтобы дать имя правому поддереву, мы опять же сопоставляем его с образцом. Мы продолжаем это сопоставление с образцом до тех пор, пока не достигнем поддерева, корнем которого является наш искомый символ 'W'. Как только мы произвели сопоставление, мы перестраиваем дерево; только поддерево, которое содержало символ 'W', теперь содержит символ 'P'.
Есть ли лучший способ? Как насчёт того, чтобы наша функция принимала дерево вместе со списком направлений? Направления будут кодироваться символами L или R, представляя левую и правую стороны соответственно, и мы изменим элемент, которого достигнем, следуя переданным направлениям. Посмотрите:
data Direction = L | R deriving (Show)
type Directions = [Direction]
changeToP :: Directions –> Tree Char –> Tree Char
changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r
changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r)
changeToP [] (Node _ l r) = Node 'P' l r
Если первый элемент в списке направлений – L, мы строим новое дерево, похожее на прежнее, только элемент в его левом под дереве заменён символом 'P'. Когда мы рекурсивно вызываем функцию changeToP, то передаём ей только «хвост» списка направлений, потому что мы уже переместились влево. То же самое происходит в случае с направлением R. Если список направлений пуст, это значит, что мы дошли до нашего места назначения, так что мы возвращаем дерево, аналогичное переданному, за исключением того, что в качестве корневого элемента оно содержит символ 'P'.
Чтобы не распечатывать дерево целиком, давайте создадим функцию, которая принимает список направлений и сообщает нам об элементе в месте назначения:
elemAt :: Directions –> Tree a –> a
elemAt (L:ds) (Node _ l _) = elemAt ds l
elemAt (R:ds) (Node _ _ r) = elemAt ds r
elemAt [] (Node x _ _) = x
Эта функция на самом деле очень похожа на функцию changeToP. С одной только разницей: вместо запоминания того, что встречается на пути, и воссоздания дерева она игнорирует всё, кроме своего места назначения. Здесь мы заменяем символ 'W' символом 'P' и проверяем, сохраняется ли изменение в нашем новом дереве:
ghci> let newTree = changeToP [R,L] freeTree
ghci> elemAt [R,L] newTree
'P'
Кажется, работает! В этих функциях список направлений служит чем-то вроде фокуса, потому как в точности указывает на одно поддерево нашего дерева. Например, список направлений [R] фокусируется на поддереве, находящемся справа от корня. Пустой список направлений фокусируется на самом главном дереве.
Хотя эта техника с виду весьма хороша, она может быть довольно неэффективной, особенно если мы хотим часто изменять элементы. Скажем, у нас есть огромное дерево и длинный список направлений, который указывает весь путь до некоего элемента в самом низу дерева. Мы используем список направлений, чтобы пройтись по дереву и изменить элемент внизу. Если мы хотим изменить другой элемент, который близок к только что изменённому нами элементу, нужно начать с корня дерева и снова пройти весь путь вниз. Какая тоска!..
В следующем разделе мы найдём более удачный способ фокусироваться на поддереве – способ, который позволяет нам эффективно переводить фокус на близлежащие поддеревья.
Тропинка из хлебных крошек
Чтобы фокусироваться на поддереве, нам нужно что-то лучшее, нежели просто список направлений, по которому мы следуем из корня нашего дерева. А могло бы помочь, если бы мы начали с корня дерева и двигались на один шаг влево или вправо за раз, оставляя по пути «хлебные крошки»? Используя этот подход, когда мы идём влево, мы запоминаем, что пошли влево; а когда идём вправо, мы запоминаем, что пошли вправо. Давайте попробуем.
Чтобы представить «хлебные крошки», мы также будем использовать список со значениями направлений (значения L и R), называя их, однако, не Directions, а Breadcrumbs, потому что наши направления теперь будут переворачиваться по мере того, как мы оставляем их, проходя вниз по нашему дереву.
type Breadcrumbs = [Direction]
Вот функция, которая принимает дерево и какие-то «хлебные крошки» и перемещается в левое поддерево, добавляя код L в «голову» списка, который представляет наши хлебные крошки:
goLeft :: (Tree a, Breadcrumbs) –> (Tree a, Breadcrumbs)
goLeft (Node _ l _, bs) = (l, L:bs)
Мы игнорируем элемент в корне и правое поддерево и просто возвращаем левое поддерево вместе с прежними «хлебными крошками», где код L присутствует в качестве «головы».
Вот функция для перемещения вправо:
goRight :: (Tree a, Breadcrumbs) –> (Tree a, Breadcrumbs)
goRight (Node _ _ r, bs) = (r, R:bs)
Она работает так же, как и функция для перемещения влево.
Давайте используем эти функции, чтобы взять наше дерево freeTree и переместиться вправо, а затем влево.
ghci> goLeft (goRight (freeTree, []))
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])
Теперь у нас есть дерево с символом 'W', находящимся в его корне, символом 'C' – в корне его левого поддерева и символом 'R' – в корне правого поддерева. «Хлебными крошками» являются коды [L,R], потому что сначала мы пошли вправо, а затем влево.
Чтобы сделать обход нашего дерева более ясным, мы можем использовать оператор –: из главы 13, который мы определили следующим образом:
x –: f = f x
Это позволяет нам применять функции к значениям, сначала записывая значение, потом –:, а затем функцию. Поэтому вместо выражения goRight (freeTree, []) мы можем написать (freeTree, []) –: goRight. Используя эту форму, перепишем предыдущий пример так, чтобы было более очевидно, что мы идём вправо, а затем влево:
ghci> (freeTree, []) -: goRight -: goLeft
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])
Движемся обратно вверх
Что, если мы хотим пойти обратно вверх по нашему дереву? Благодаря «хлебным крошкам» нам известно, что текущее дерево является левым поддеревом своего родителя, а последнее является правым поддеревом своего родителя – собственно, это всё, что нам известно. «Хлебные крошки» не сообщают нам достаточно сведений о родителе текущего поддерева, чтобы была возможность пойти вверх по дереву. Похоже, что помимо направления, по которому мы пошли, отдельная «хлебная крошка» должна также содержать все остальные сведения, которые необходимы для обратного движения вверх. В таком случае необходимыми сведениями являются элемент в родительском дереве вместе с его правым поддеревом.
Вообще у отдельной «хлебной крошки» должны быть все сведения, необходимые для восстановления родительского узла. Так что она должна иметь информацию из всех путей, которыми мы не пошли, а также знать направление, по которому мы пошли. Однако она не должна содержать поддерево, на котором мы фокусируемся в текущий момент, – потому что у нас уже есть это поддерево в первом компоненте кортежа. Если бы оно присутствовало у нас и в «хлебной крошке», мы бы имели копию уже имеющейся информации.
А нам такая копия не нужна, поскольку если бы мы изменили несколько элементов в поддереве, на котором фокусируемся, то имеющаяся в «хлебных крошках» информация не согласовывалась бы с произведёнными нами изменениями. Копия имеющейся информации устаревает, как только мы изменяем что-либо в нашем фокусе. Если наше дерево содержит много элементов, это также может забрать много памяти.
Давайте изменим наши «хлебные крошки», чтобы они содержали информацию обо всём, что мы проигнорировали ранее, когда двигались влево и вправо. Вместо типа Direction создадим новый тип данных:
data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)
Теперь вместо кода L у нас есть значение LeftCrumb, содержащее также элемент узла, из которого мы переместились, и не посещённое нами правое поддерево. Вместо кода R есть значение RightCrumb, содержащее элемент узла, из которого мы переместились, и не посещённое нами левое поддерево.
Эти «хлебные крошки» уже содержат все сведения, необходимые для воссоздания дерева, по которому мы прошли. Теперь это не обычные «хлебные крошки» – они больше похожи на дискеты, которые мы оставляем при перемещении, потому что они содержат гораздо больше информации, чем просто направление, по которому мы шли!
В сущности, каждая такая «хлебная крошка» – как узел дерева, имеющий отверстие. Когда мы двигаемся вглубь дерева, в «хлебной крошке» содержится вся информация, которая имелась в покинутом нами узле, за исключением поддерева, на котором мы решили сфокусироваться. Нужно также указать, где находится отверстие. В случае со значением LeftCrumb нам известно, что мы переместились влево, так что отсутствующее поддерево – правое.
Давайте также изменим наш синоним типа Breadcrumbs, чтобы отразить это:
type Breadcrumbs a = [Crumb a]
Затем нам нужно изменить функции goLeft и goRight, чтобы они сохраняли информацию о путях, по которым мы не пошли, в наших «хлебных крошках», а не игнорировали эту информацию, как они делали это раньше. Вот новое определение функции goLeft:
goLeft :: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a)
goLeft (Node x l r, bs) = (l, (LeftCrumb x r):bs)
Как вы можете видеть, она очень похожа на нашу предыдущую функцию goLeft, но вместо того чтобы просто добавлять код L в «голову» нашего списка «хлебных крошек», мы добавляем туда значение LeftCrumb, чтобы показать, что мы пошли влево. Мы также снабжаем наше значение LeftCrumb элементом узла, из которого мы переместились (то есть значением x), и правым поддеревом, которое мы решили не посещать.
Обратите внимание: эта функция предполагает, что текущее дерево, находящееся в фокусе, – не Empty. Пустое дерево не содержит никаких поддеревьев, поэтому если мы попытаемся пойти влево из пустого дерева, возникнет ошибка. Причина в том, что сравнение значения типа Node с образцом будет неуспешным, и нет образца, который заботится о конструкторе Empty.
Функция goRight аналогична:
goRight :: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a)
goRight (Node x l r, bs) = (r, (RightCrumb x l):bs)
Ранее мы могли двигаться влево или вправо. То, чем мы располагаем сейчас, – это возможность действительно возвращаться вверх, запоминая информацию о родительских узлах и путях, которые мы не посетили. Вот определение функции goUp:
goUp :: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a)
goUp (t, LeftCrumbx r:bs) = (Node x t r, bs)
goUp (t, RightCrumb x l:bs) = (Node x l t, bs)
Мы фокусируемся на дереве t и проверяем последнее значение типа Crumb. Если это значение равно LeftCrumb, мы строим новое дерево, используя наше дерево t в качестве левого поддерева и информацию о правом поддереве и элементе, которые мы не посетили, чтобы заполнить остальные части Node. Поскольку мы «переместились обратно» и подняли последнюю «хлебную крошку», а затем использовали её, чтобы воссоздать родительское дерево, в новом списке эта «хлебная крошка» не содержится.
Обратите внимание, что данная функция вызывает ошибку, если мы уже находимся на вершине дерева и хотим переместиться выше. Позже мы используем монаду Maybe, чтобы представить возможную неудачу при перемещении фокуса.
С парой, состоящей из значений типов Tree a и Breadcrumbs a, у нас есть вся необходимая информация для восстановления дерева; кроме того, у нас есть фокус на поддереве. Эта схема позволяет нам легко двигаться вверх, влево и вправо.
Пару, содержащую часть структуры данных в фокусе и её окружение, называют застёжкой, потому что перемещение нашего фокуса вверх и вниз по структуре данных напоминает работу застёжки-молнии на брюках. Поэтому круто будет создать такой синоним типа:
type Zipper a = (Tree a, Breadcrumbs a)
Я бы предпочёл назвать этот синоним типа Focus, поскольку это наглядно показывает, что мы фокусируемся на части структуры данных. Но так как для описания такой структуры чаще всего используется имя Zipper, будем придерживаться его.
Манипулируем деревьями в фокусе
Теперь, когда мы можем перемещаться вверх и вниз, давайте создадим функцию, изменяющую элемент в корне поддерева, на котором фокусируется застёжка.
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, а «хвост» является пустым списком [].
Давайте создадим застёжку для списков. Чтобы изменить фокус на подсписках списка, мы перемещаемся или вперёд, или назад (тогда как при использовании деревьев мы перемещались вверх, влево или вправо). Помещённой в фокус частью будет подсписок, а кроме того, мы будем оставлять «хлебные крошки» по мере нашего движения вперёд.
А из чего состояла бы отдельная «хлебная крошка» для списка? Когда мы имели дело с бинарными деревьями, нужно было, чтобы «хлебная крошка» хранила элемент, содержащийся в корне родительского узла, вместе со всеми поддеревьями, которые мы не выбрали. Она также должна была запоминать, куда мы пошли, – влево или вправо. Поэтому требовалось, чтобы в ней содержалась вся имеющаяся в узле информация, за исключением поддерева, на которое мы решили навести фокус.
Списки проще, чем деревья. Нам не нужно запоминать, по шли ли мы влево или вправо, потому что вглубь списка можно пойти лишь одним способом. Поскольку для каждого узла существует только одно поддерево, нам также не нужно запоминать пути, по которым мы не пошли. Кажется, всё, что мы должны запоминать, – это предыдущий элемент. Если у нас есть список вроде [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])
Вы можете видеть, что «хлебные крошки» в случае со списками – просто перевёрнутая часть вашего списка. Элемент, от которого мы удаляемся, всегда помещается в «голову» «хлебных крошек». Потом легко переместиться назад, просто вынимая этот элемент из их «головы» и делая его «головой» нашего фокуса. На данном примере опять-таки легко понять, почему мы называем это застёжкой: действительно очень напоминает перемещающийся вверх-вниз замок застёжки-молнии!
Если бы вы создавали текстовый редактор, можно было бы использовать список строк для представления строк текста, которые в текущий момент открыты, а затем использовать застёжку, чтобы знать, на какой строке в данный момент установлен курсор. Использование застёжки также облегчило бы вставку новых строк в любом месте текста или удаление имеющихся строк.
Очень простая файловая система
Для демонстрации работы застёжек давайте используем деревья, чтобы представить очень простую файловую систему. Затем мы можем создать застёжку для этой файловой системы, которая позволит нам перемещаться между каталогами, как мы это делаем при переходах по реальной файловой системе.
Обычная иерархическая файловая система состоит преимущественно из файлов и каталогов. Файлы – это элементы данных, снабжённые именами. Каталоги используются для организации этих файлов и могут содержать файлы или другие каталоги. Для нашего простого примера достаточно сказать, что элементами файловой системы являются:
• файл под некоторым именем, содержащий некие данные;
• каталог под некоторым именем, содержащий другие элементы, которые сами являются или файлами, или каталогами.
Вот соответствующий тип данных и некоторые синонимы типов, чтобы было понятно, что к чему:
type Name = String
type Data = String
data FSItem = File Name Data | Folder Name [FSItem] deriving (Show)
К файлу прилагаются две строки, представляющие его имя и содержимое. К каталогу прилагаются строка, являющаяся его именем, и список элементов. Если этот список пуст, значит, мы имеем пустой каталог.
Вот каталог с некоторыми файлами и подкаталогами (на самом деле это то, что в настоящую минуту содержится на моём диске):
myDisk :: FSItem
myDisk =
Folder "root"
[ File "goat_yelling_like_man.wmv" "бааааааа"
, File "pope_time.avi" "Боже, благослови"
, Folder "pics"
[ File "ape_throwing_up.jpg" "блин..."
, File "watermelon_smash.gif" "шмяк!!"
, File "skull_man(scary).bmp" "Ой!"
]
, File "dijon_poupon.doc" "лучшая горчица"
, Folder "programs"
[ File "sleepwizard.exe" "10 пойти поспать"
, File "owl_bandit.dmg" "move ax, 42h"
, File "not_a_virus.exe" "точно не вирус"
, Folder "source code"
[ File "best_hs_prog.hs" "main = print (fix error)"
, File "random.hs" "main = print 4"
]
]
]
Создаём застёжку для нашей файловой системы
Теперь, когда у нас есть файловая система, всё, что нам нужно, – это застёжка, чтобы мы могли застёгивать файловую систему и брать её крупным планом, а также добавлять, изменять и удалять файлы и каталоги. Как и в случае с использованием бинарных деревьев и списков, наши «хлебные крошки» будут содержать информацию обо всём, что мы решили не посещать. Отдельная «хлебная крошка» должна хранить всё, кроме поддерева, на котором мы фокусируемся в данный момент. Она также должна указывать, где находится отверстие, чтобы при перемещении обратно вверх мы смогли вставить в отверстие наш предыдущий фокус.
В этом случае «хлебная крошка» должна быть похожа на каталог – только выбранный нами в данный момент каталог должен в нём отсутствовать. Вы спросите: «А почему не на файл?» Ну, потому что, когда мы фокусируемся на файле, мы не можем углубляться в файловую систему, а значит, не имеет смысла оставлять «хлебную крошку», которая говорит, что мы пришли из файла. Файл – это что-то вроде пустого дерева.
Если мы фокусируемся на каталоге "root", а затем на файле "dijon_poupon.doc", как должна выглядеть «хлебная крошка», которую мы оставляем? Она должна содержать имя своего родительского каталога вместе с элементами, идущими перед файлом, на котором мы фокусируемся, и следом за ним. Поэтому всё, что нам требуется, – значение Name и два списка элементов. Храня два отдельных списка для элементов, идущих перед элементом, на котором мы фокусируемся, и для элементов, идущих за ним, мы будем точно знать, где мы его поместили, при перемещении обратно вверх. Таким образом, нам известно местоположение отверстия.
Вот наш тип «хлебной крошки» для файловой системы:
data FSCrumb = FSCrumb Name [FSItem] [FSItem]
deriving (Show)
А вот синоним типа для нашей застёжки:
type FSZipper = (FSItem, [FSCrumb])
Идти обратно вверх по иерархии очень просто. Мы берём самую последнюю «хлебную крошку» и собираем новый фокус из текущего фокуса и «хлебной крошки» следующим образом:
fsUp :: FSZipper –> FSZipper
fsUp (item, FSCrumb name ls rs:bs) = (Folder name (ls ++ [item] ++ rs), bs)
Поскольку нашей «хлебной крошке» были известны имя родительского каталога, а также элементы, которые шли перед находящимся в фокусе элементом каталога (то есть ls), и элементы, которые шли за ним (то есть rs), перемещаться вверх было легко.
Как насчёт продвижения вглубь файловой системы? Если мы находимся в "root" и хотим сфокусироваться на файле "dijon_poupon. doc", оставляемая нами «хлебная крошка» будет включать имя "root" вместе с элементами, предшествующими файлу "dijon_poupon.doc", и элементами, идущими за ним. Вот функция, которая, получив имя, фокусируется на файле или каталоге, расположенном в текущем каталоге, куда в текущий момент наведён фокус:
import Data.List (break)
fsTo :: Name –> FSZipper –> FSZipper
fsTo name (Folder folderName items, bs) =
let (ls, item:rs) = break (nameIs name) items
in (item, FSCrumb folderName ls rs:bs)
nameIs :: Name –> FSItem –> Bool
nameIs name (Folder folderName _) = name == folderName
nameIs name (File fileName _) = name == fileName
Функция fsTo принимает значения Name и FSZipper и возвращает новое значение FSZipper, которое фокусируется на файле с заданным именем. Этот файл должен присутствовать в текущем каталоге, находящемся в фокусе. Данная функция не производит поиск везде – она просто смотрит в текущем каталоге.
Сначала мы используем функцию break, чтобы разбить список элементов в каталоге на те, что предшествуют искомому нами файлу, и те, что идут за ним. Функция break принимает предикат и список и возвращает пару списков. Первый список в паре содержит элементы, для которых предикат возвращает значение False. Затем, когда предикат возвращает значение True для элемента, функция помещает этот элемент и остальную часть списка во второй элемент пары. Мы создали вспомогательную функцию nameIs, которая принимает имя и элемент файловой системы и, если имена совпадают, возвращает значение True.
Теперь ls – список, содержащий элементы, предшествующие искомому нами элементу; item является этим самым элементом, а rs – это список элементов, идущих за ним в его каталоге. И вот сейчас, когда они у нас есть, мы просто представляем элемент, полученный нами из функции break, как фокус и строим «хлебную крошку», которая содержит все необходимые ей данные.
Обратите внимание, что если имя, которое мы ищем, не присутствует в каталоге, образец item:rs попытается произвести сопоставление с пустым списком, и мы получим ошибку. А если наш текущий фокус – файл, а не каталог, мы тоже получим ошибку, и программа завершится аварийно.
Итак, мы можем двигаться вверх и вниз по нашей файловой системе. Давайте начнём движение с корня и перейдём к файлу "skull_man(scary).bmp":
ghci> let newFocus = (myDisk, []) -: fsTo "pics" -: fsTo "skull_man(scary).bmp"
Значение newFocus теперь – застёжка, сфокусированная на файле skull_man(scary).bmp. Давайте получим первый компонент застёжки (сам фокус) и посмотрим, так ли это на самом деле.
ghci> fst newFocus
File "skull_man(scary).bmp" "Ой!"
Переместимся выше и сфокусируемся на соседнем с ним файле "watermelon_smash.gif":
ghci> let newFocus2 = newFocus –: fsUp –: fsTo "watermelon_smash.gif"
ghci> fst newFocus2
File "watermelon_smash.gif" "шмяк!!"
Манипулируем файловой системой
Теперь, когда мы можем передвигаться по нашей файловой системе, ею легко манипулировать. Вот функция, которая переименовывает находящийся в данный момент в фокусе файл или каталог:
fsRename :: Name –> FSZipper –> FSZipper
fsRename newName (Folder name items, bs) = (Folder newName items, bs)
fsRename newName (File name dat, bs) = (File newName dat, bs)
Давайте переименуем наш каталог "pics" в "cspi":
ghci> let newFocus = (myDisk, []) –: fsTo "pics" –: fsRename "cspi" –: fsUp
Мы спустились к каталогу "pics", переименовали его, а затем поднялись обратно вверх.
Как насчёт функции, которая создаёт новый элемент в текущем каталоге? Встречайте:
fsNewFile :: FSItem –> FSZipper –> FSZipper
fsNewFile item (Folder folderName items, bs) =
(Folder folderName (item:items), bs)
Проще пареной репы! Обратите внимание, что если бы мы попытались добавить элемент, но фокусировались бы на файле, а не на каталоге, это привело бы к аварийному завершению программы.
Давайте добавим в наш каталог "pics" файл, а затем поднимемся обратно к корню:
ghci> let newFocus =
(myDisk, []) –: fsTo "pics" –: fsNewFile (File "heh.jpg" "лол") –: fsUp
Что действительно во всём этом здорово, так это то, что когда мы изменяем нашу файловую систему, наши изменения на самом деле не производятся на месте – напротив, функция возвращает совершенно новую файловую систему. Таким образом, мы имеем доступ к нашей прежней файловой системе (в данном случае myDisk), а также к новой (первый компонент newFocus).
Используя застёжки, мы бесплатно получаем контроль версий. Мы всегда можем обратиться к старым версиям структур данных даже после того, как изменили их. Это не уникальное свойство застёжек; оно характерно для языка Haskell в целом, потому что его структуры данных неизменяемы. При использовании застёжек, однако, мы получаем возможность легко и эффективно обходить наши структуры данных, так что неизменность структур данных языка Haskell действительно начинает сиять во всей красе!
Осторожнее – смотрите под ноги!
До сих пор при обходе наших структур данных – будь они бинарными деревьями, списками, или файловыми системами – нам не было дела до того, что мы прошагаем слишком далеко и упадём. Например, наша функция goLeft принимает застёжку бинарного дерева и передвигает фокус на его левое поддерево:
goLeft :: Zipper a –> Zipper a
goLeft (Node x l r, bs) = (l, LeftCrumb x r:bs)
Но что если дерево, с которого мы сходим, является пустым? Что если это не значение Node, а Empty? В этом случае мы получили бы ошибку времени исполнения, потому что сопоставление с образцом завершилось бы неуспешно, а образец для обработки пустого дерева, у которого нет поддеревьев, мы не создавали.
До сих пор мы просто предполагали, что никогда не пытались бы навести фокус на левое поддерево пустого дерева, так как его левого поддерева просто не существует. Но переход к левому поддереву пустого дерева не имеет какого-либо смысла, и мы до сих пор это удачно игнорировали.
Ну или вдруг мы уже находимся в корне какого-либо дерева, и у нас нет «хлебных крошек», но мы всё же пытаемся переместиться вверх? Произошло бы то же самое! Кажется, при использовании застёжек каждый наш шаг может стать последним (не хватает только зловещей музыки). Другими словами, любое перемещение может привести к успеху, но также может привести и к неудаче. Вам это что-нибудь напоминает? Ну конечно же: монады! А конкретнее, монаду Maybe, которая добавляет к обычным значениям контекст возможной неудачи.
Давайте используем монаду Maybe, чтобы добавить к нашим перемещениям контекст возможной неудачи. Мы возьмём функции, которые работают с нашей застёжкой для двоичных деревьев, и превратим в монадические функции.
Сначала давайте позаботимся о возможной неудаче в функциях goLeft и goRight. До сих пор неуспешное окончание выполнения функций, которые могли окончиться неуспешно, всегда отражалось в их результате, и этот пример – не исключение.
Вот определения функций goLeft и goRight с добавленной возможностью неудачи:
goLeft :: Zipper a –> Maybe (Zipper a)
goLeft (Node x l r, bs) = Just (l, LeftCrumb x r:bs)
goLeft (Empty, _) = Nothing
goRight :: Zipper a –> Maybe (Zipper a)
goRight (Node x l r, bs) = Just (r, RightCrumb x l:bs)
goRight (Empty, _) = Nothing
Теперь, если мы попытаемся сделать шаг влево относительно пустого дерева, мы получим значение Nothing!
ghci> goLeft (Empty, [])
Nothing
ghci> goLeft (Node 'A' Empty Empty, [])
Just (Empty, [LeftCrumb 'A' Empty])
Выглядит неплохо! Как насчёт движения вверх? Раньше возникала проблема, если мы пытались пойти вверх, но у нас больше не было «хлебных крошек», что значило, что мы уже находимся в корне дерева. Это функция goUp, которая выдаст ошибку, если мы выйдем за пределы нашего дерева:
goUp :: Zipper a –> Zipper a
goUp (t, LeftCrumbx r:bs) = (Node x t r, bs)
goUp (t, RightCrumb x l:bs) = (Node x l t, bs)
Давайте изменим её, чтобы она завершалась неудачей мягко:
goUp :: Zipper a –> Maybe (Zipper a)
goUp (t, LeftCrumbx r:bs) = Just (Node x t r,bs)
goUp (t, RightCrumb x l:bs) = Just (Node x l t, bs)
goUp (_, []) = Nothing
Если у нас есть хлебные крошки, всё в порядке, и мы возвращаем успешный новый фокус. Если у нас нет хлебных крошек, мы возвращаем неудачу.
Раньше эти функции принимали застёжки и возвращали застёжки, что означало, что мы можем сцеплять их следующим образом для осуществления обхода:
gchi> let newFocus = (freeTree, []) –: goLeft –: goRight
Но теперь вместо того, чтобы возвращать значение типа Zipper a, они возвращают значение типа Maybe (Zipper a), и сцепление функций подобным образом работать не будет. У нас была похожая проблема, когда в главе 13 мы имели дело с нашим канатоходцем. Он тоже проходил один шаг за раз, и каждый из его шагов мог привести к неудаче, потому что несколько птиц могли приземлиться на одну сторону его балансировочного шеста, что приводило к падению.
Теперь шутить будут над нами, потому что мы – те, кто производит обход, и обходим мы лабиринт нашей собственной разработки. К счастью, мы можем поучиться у канатоходца и сделать то, что сделал он: заменить обычное применение функций оператором >>=. Он берёт значение с контекстом (в нашем случае это значение типа Maybe (Zipper a), которое имеет контекст возможной неудачи) и передаёт его в функцию, обеспечивая при этом обработку контекста. Так что, как и наш канатоходец, мы отдадим все наши старые операторы –: в счёт приобретения операторов >>=. Затем мы вновь сможем сцеплять наши функции! Смотрите, как это работает:
ghci> let coolTree = Node 1 Empty (Node 3 Empty Empty)
ghci> return (coolTree, []) >>= goRight
Just (Node 3 Empty Empty,[RightCrumb 1 Empty])
ghci> return (coolTree, []) >>= goRight >>= goRight
Just (Empty,[RightCrumb 3 Empty,RightCrumb 1 Empty])
ghci> return (coolTree, []) >>= goRight >>= goRight >>= goRight
Nothing
Мы использовали функцию return, чтобы поместить застёжку в конструктор Just, а затем прибегли к оператору >>=, чтобы передать это дело нашей функции goRight. Сначала мы создали дерево, которое в своей левой части имеет пустое поддерево, а в правой – узел, имеющий два пустых поддерева. Когда мы пытаемся пойти вправо один раз, результатом становится успех, потому что операция имеет смысл. Пойти вправо во второй раз – тоже нормально. В итоге мы получаем фокус на пустом поддереве. Но идти вправо третий раз не имеет смысла: мы не можем пойти вправо от пустого поддерева! Поэтому результат – Nothing.
Теперь мы снабдили наши деревья «сеткой безопасности», которая поймает нас, если мы свалимся. (Ух ты, хорошую метафору я подобрал.)
ПРИМЕЧАНИЕ. В нашей файловой системе также имеется много случаев, когда операция может завершиться неуспешно, как, например, попытка сфокусироваться на несуществующем файле или каталоге. В качестве упражнения вы можете снабдить нашу файловую систему функциями, которые завершаются неудачей мягко, используя монаду Maybe .
Благодарю за то, что прочитали!
…Или, по крайней мере, пролистали до последней страницы! Я надеюсь, вы нашли эту книгу полезной и весёлой. Я постарался дать вам хорошее понимание языка Haskell и его идиом. Хотя при изучении этого языка всегда открывается что-то новое, вы теперь сможете писать классный код, а также читать и понимать код других людей. Так что скорее приступайте к делу! Увидимся в мире программирования!
