はじめに

この記事はHaskell Advent Calendar 2日目の記事です。

この記事では、書籍「すごいHaskellたのしく学ぼう!」(以下すごいHの本)の15章を参考に、Zipperを使ってリストや木構造を"純粋に"操作する方法を紹介します。

初めての挑戦なので自分の中でZipperを整理しようという意図もありますが、その際の知見をお裾分けしてみようと思います。

Zipperって何？

Haskellではリストや木構造は再帰的に定義されていています。こうした構造では先頭の値を変更することは容易ですが、途中の値を変更するには以下の手順を踏む必要があります。

変更したい場所まで構造をたどる
その場所より後ろにある構造($L_{tail}$)と、前にある構造($L_{init}$)を切り離す
$L_{tail}$に新しい値を継ぎ足し、さらに$L_{init}$をつなぐ

もし複数の値を変更したい際には、いちいち先頭からたどっては変更して...を繰り返す必要があり、非常に効率が悪くなってしまいます。

そこでZipperではリストや木構造の「現在位置」を一緒に保存しておくことで、最小限の移動で更新されたリストなどを取得できるようにしています。それではさっそく具体例と一緒に見ていきましょう。

ListでZipper

Zipperの定義

リストでZipperをしてみます。リストの現在位置と、残りのリストを保存しておけば良いので次のようなタプルを作って、ListZipperと命名しておきましょう。タプルの最初の値が今注目しているリスト、二番目の値が残りのリストを表しています。

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

Zipperでリストを行き来しよう

さて、リストを行ったり来たりしてみましょう。注目点を次に進めるgoForwardとgoBackを実装してみます。

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

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

ちょっくら試してみましょう。

Prelude> list = [1,2,3,4,5]
Prelude> goForward (list, [])
([2,3,4,5],[1])
Prelude> goBack ([2,3,4,5],[1])
([1,2,3,4,5],[])

でもリストのパーンマッチって失敗するよね

こんな場合はどうでしょうか？

Prelude> goForward ([], list)
*** Exception: <interactive>:2:1-33: Non-exhaustive patterns in function goForward
Prelude> goBack (list, [])
*** Exception: <interactive>:3:1-30: Non-exhaustive patterns in function goBack

実行時エラーはお行儀が悪いので、Maybeに包んであげましょう。ちょっとghciでやるのはつらいので、適当なスクリプトに書き込んでghci側でロードして実験します。

zipper.hs

goForward :: ListZipper a -> Maybe (ListZipper a)
goForward (x:xs, bs) = Just (xs, x:bs)
goForward ([], _) = Nothing

goBack :: ListZipper a -> Maybe (ListZipper a)
goBack (xs, b:bs) = Just (b:xs, bs)
goBack (_, []) = Nothing

Prelude> :l zipper.hs
[1 of 1] Compiling Main             ( zipper.hs, interpreted )
Ok, modules loaded: Main.
*Main> list = [1,2,3,4,5]
*Main> goForward (list, [])
Just ([2,3,4,5],[1])
*Main> goForward ([], list)
Nothing
*Main> goBack ([], list)
Just ([1],[2,3,4,5])
*Main> goBack (list, [])
Nothing
*Main>

ちゃんと失敗を捕まえていますね。しかもbindを使えば連続して関数を適用することもできちゃいます。

*Main> return (list, []) >>= goForward >>= goForward >>= goBack
Just ([2,3,4,5],[1])
*Main>

値を更新してみよう

今注目している値を更新する関数も書いてみましょう。やっぱり注目している箇所が空リストだった場合はパターンマッチに失敗してしまうので、Maybeを使って処理してあげます。

replace :: a -> ListZipper a -> Maybe (ListZipper a)
replace a (_:xs, bs) = Just (a:xs, bs)
replace _ ([], _) = Nothing

*Main> list = [1,2,3,4,5]
*Main> replace 10 (list, [])
Just ([10,2,3,4,5],[])
*Main> replace 10 ([], list)
Nothing
*Main> return (list, []) >>= goForward >>= goForward >>= replace 50
Just ([50,4,5],[2,1])

きちんと置換できてますね。

Zipperとリストの相互変換

今まで手動でタプルを作って渡していましたが、ちょっと面倒なのでヘルパー関数を書いてしまいましょう。

toListZipper :: [a] -> ListZipper a
toListZipper xs = (xs, [])

fromListZipper :: ListZipper a -> [a]
fromListZipper (xs, []) = xs
fromListZipper (xs, b:bs) = fromListZipper (b:xs, bs)

*Main> fmap fromListZipper $ return (toListZipper list) >>= goForward >>= replace 10
Just [1,10,3,4,5]

無事に一連の計算ができたようです！

おわりに

すごいHの本には木構造のZipperが先に紹介されていますが、個人的には先にリストでイメージをつかんだ方がやりやすかったのでこのような記事を書いてみました。また、Maybeで失敗を表したりする方法も木構造のものしか紹介されていなかったので、自分で考えて作ってみました。型とパターンを合わせて正しく動作する関数を作るのはやっぱり楽しいですね！

そういうわけで皆さんもこういった構造の操作にZipperを使ってみてください！

なお自分で実装しなくても「Data.Generics.Zipper」もすでに存在しているので、こちらを活用してみるのも良いでしょう！それでは皆さんよきHaskellライフを！

Zipperに挑む