関数プログラミングの楽しみ

レビューに参加した「関数プログラミングの楽しみ」が届きました。これは、関数プログラミングの入門書をいくつか読んだ人が、もっと高みを目指すための本です。

関数プログラミングの楽しみ

目次

この本は、関数プログラミングの父 Richard Bird が還暦を迎えることを記念して、著名人が各章を寄稿し、編集した構成となっています。コードはすべて Haskell で書かれています。目次は以下の通りです。

1. 二分ヒープ木の楽しみ
2. 仕様に基づくテスト -- QuickCheck を使って
3. おりがみプログラミング
4. Haskellで音楽を記述し解釈する
5. 融合変換を自動化する
6. 金融取引契約の書き方
7. 関数画像
8. Lava:関数によるハードウェア記述
9. 論理プログラミングのためのコンビネータ
10. アローと計算
11. もっと整ったプリティプリンタ
12. ファントム型を楽しむ

時間の制約により、僕がレビューできたのは 1章、2章、3章、6章、10章のみです。半分以下しか読んでいませんが、刺激的な内容でした。その一部をお伝えします。

ヒープソート

1章は、"Purely Functional Data Structure" の著者 Chris Okasaki 氏によるヒープの話です。ヒープは木であり、平衡を保つことが重要です。その方法をいくつか示すのですが、最後の最後でどんでん返しが待っています。

Purely Functional Data Structures

3章は、Origami プログラミングの話です。こういう分野があることは耳にはしていたのですが、今回 fold と unfold のことだと初めて分かりました。また、unfold という考え方も初めて知りました。この 2 つの概念を軸に、いろいろなソートを実装してみせます。

新しいプログラミング言語を習得したら、その言語で実装してみたくなるアルゴリズムの一つにヒープソートを挙げる人もいるでしょう。ヒープソートに関しては、たとえば「珠玉のプログラミング」などに詳しく書かれていますが、関数プログラミングと相性の悪い配列を使っています。僕は長い間、Haskell でヒープソートをどう実現したら効率がいいのか分かりませんでした。

本書にははっきりとは書かれていませんが、1章と3章の内容を読めば、効率のよいヒープソートを簡単に実装できます。この記事の最後に、僕が書いたヒープソートのコードを付けます。あまりにも簡単で、拍子抜けするほどです。

まとめ

この本には、関数プログラミングに関する豊かな知見がちりばめられています。一歩先行く関数プログラマーになりたい人は、ぜひ読んでみて下さい。

import Data.List (unfoldr)

data Tree a = Null | Fork a (Tree a) (Tree a) deriving Show

isEmpty :: Tree a -> Bool
isEmpty Null = True
isEmpty _    = False

minElem :: Tree a -> a
minElem (Fork x _ _) = x
minElem _            = error "minElem"

deleteMin :: Ord a => Tree a -> Tree a
deleteMin (Fork _ a b) = merge a b
deleteMin _            = error "deleteMin"

insert :: Ord a => a -> Tree a -> Tree a
insert x = merge (Fork x Null Null)

merge :: Ord a => Tree a -> Tree a -> Tree a
merge a Null = a
merge Null b = b
merge a b
  | minElem a <= minElem b = join a b
  | otherwise              = join b a

join :: Ord a => Tree a -> Tree a -> Tree a
join (Fork x a b) c = Fork x b (merge a c)
join _ _ = error "join"

heapSortTree :: Ord a => [a] -> [a]
heapSortTree xs = unfoldr takeToList (foldr insert Null xs)
  where
    takeToList heap
      | isEmpty heap = Nothing
      | otherwise    = Just (minElem heap, deleteMin heap)