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 は次の2つの本を読んで勉強した。

ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門

ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門

  • 作者: 青木 峰郎
  • 出版社/メーカー: ソフトバンククリエイティブ
  • 発売日: 2006-06-01
  • メディア: 単行本
  • Amazon のレビューを見る

「ふつうのHaskell」はとても丁寧で分かりやすかった。全体の構成が練りに練られていて、初心者でもすいすい理解できる!

入門Haskell―はじめて学ぶ関数型言語

入門Haskell―はじめて学ぶ関数型言語

  • 作者: 向井 淳
  • 出版社/メーカー: 毎日コミュニケーションズ
  • 発売日: 2006-03
  • メディア: 単行本
  • Amazon のレビューを見る

「入門 Haskell」は文章が多少こなれていない感じなんだけど、「ふつうのHaskell」のあとに読むと復習になってよかった。「ふつうのHaskell」では扱っていない内容にも踏み込んでいて理解が深まった。