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