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

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), которое имеет контекст возможной неудачи) и передаёт его в функцию, обеспечивая при этом обработку контекста. Так что, как и наш канатоходец, мы отдадим все наши старые операторы –: в счёт приобретения операторов >>=. Затем мы вновь сможем сцеплять наши функции! Смотрите, как это работает: