Haskell でヒープソートを書いてみた
関数型言語に苦手意識があったので、ここのところ Haskell を勉強していた。せっかくなので、Smalltalk でヒープソートを書いてみた に続き、今度は Haskell でヒープソートを書いてみる。
アルゴリズムイントロダクション 第1巻の疑似コードが手続き型なので、それをどのように関数型に変換していくかが難しかった。アルゴリズムイントロダクションが手元にない人は、Ruby 版 を見ると分かりやすいだろう。
下準備
まずは、配列のインデックスを 1 ベースにする。ライブラリの Array 型は好きな値からインデックスを始められるようだが、Haskell の基本的な使い方を覚えたいのでパス。あえてリストで書いてみる。リストの要素にアクセスする関数は !! なので、これをラップした !!! を作ってみる。
(!!!) :: [a] -> Int -> a (!!!) xs i = xs !! (i - 1)
次は、教科書の PARENT, LEFT, RIGHT。
parent :: Int -> Int parent = (`div` 2) left :: Int -> Int left = (* 2) right :: Int -> Int right = (+ 1) . (* 2)
単純な関数なので、部分適用や関数合成を使って書いてみた。
次、swap。これも頑張って書き下してみる。もっとシンプルな書き方がありそうなんだが、ひとまずは泥臭く。
swap :: Int -> Int -> [a] -> [a]
swap m n list = take (i1 - 1) list
++ [list !!! i2]
++ (drop i1 $ take (i2 - 1) list)
++ [list !!! i1]
++ drop i2 list
where i1 = min m n
i2 = max m n
手続き型脳から脱却できぬ
いよいよ大物へ。MAX-HEAPIFY。if 文が並んでいた THE 手続き型な関数だったので、とても苦労した。
maxHeapify :: Int -> [Int] -> [Int]
maxHeapify i arr = if largest i /= i
then maxHeapify (largest i) $ swap (largest i) i arr
else arr
where
largeLeft i j =
if left i <= length arr && (arr !!! left i) > (arr !!! j)
then left i
else j
largeRight i j =
if right i <= length arr && (arr !!! right i) > (arr !!! j)
then right i
else j
largest i = largeRight i $ largeLeft i i
ひとまずは教科書をそのまま書き下してみた。もっとシンプルに関数型っぽく書き直してみたいんだけど、方針が思いつかない。
ループの書き直し
BUILD-MAX-HEAP には for 文が登場。Haskell に for 文はないので、再帰か畳み込みで書き直す必要がある。ここでは畳み込み(foldr)を使ってみた。
buildMaxHeap :: [Int] -> [Int] buildMaxHeap arr = foldr maxHeapify arr $ [1 .. (length arr) `div` 2]
畳み込みにも苦手意識があったけど、畳み込み関数の比較 (fold / accumulate / inject / reduce) - blanket-log がすごく分かりやすかった。ありがたい。
最後は HEAP-SORT。ここでも for 文が登場するので、今度は再帰を使ってみた。
heapSort :: [Int] -> [Int]
heapSort [] = []
heapSort arr = heapSort (take (length arr - 1) $ swapped arr)
++ [head $ buildMaxHeap arr]
where swapped arr = swap 1 (length arr) $ buildMaxHeap arr
動け！
最後に main。
main = print $ heapSort [4,1,3,2,16,9,10,14,8,7] -- [1,2,3,4,7,8,9,10,14,16]
動いた！
感想
なんとか動いたが、Haskell っぽいソースに見えない。誰かに添削してほしい。ujihisa とか。
Haskell は次の２つの本を読んで勉強した。
ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門
- 作者: 青木 峰郎
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2006-06-01
- メディア: 単行本
- Amazon のレビューを見る
「ふつうのHaskell」はとても丁寧で分かりやすかった。全体の構成が練りに練られていて、初心者でもすいすい理解できる！
- 作者: 向井 淳
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2006-03
- メディア: 単行本
- Amazon のレビューを見る
「入門 Haskell」は文章が多少こなれていない感じなんだけど、「ふつうのHaskell」のあとに読むと復習になってよかった。「ふつうのHaskell」では扱っていない内容にも踏み込んでいて理解が深まった。