Journal InTime

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

湿潤治療の本を買うために今井書店に行ったら関数プログラミングの楽しみが置いてあったので、つい購入してしまった。 Richard S. Birdの還暦を記念して、色々な著者が関数プログミングの楽しみについて綴っている。 Introduction to Functional Programming using Haskell (IFPH)の続編という位置付けらしいが、IFPHを持ってなくても一応読める。

以下は、サポートサイトを参考に第1章の最大回避ヒープの練習問題を解いたもの(ほとんど写経)。

import qualified Data.Tree as T

data (Ord a) => Tree a = Null | Fork Int a (Tree a) (Tree a)

drawTree :: (Ord a, Show a) => Tree a -> String
drawTree = T.drawTree . conv
  where
    conv Null = T.Node "Null" []
    conv (Fork n x a b) = T.Node (show x) (map conv [a, b])

instance (Ord a, Show a) => Show (Tree a) where
  show = drawTree

isEmpty :: Ord a => Tree a -> Bool
isEmpty Null = True
isEmpty (Fork n x a b) = False

minElem :: Ord a => Tree a -> a
minElem (Fork n x a b) = x

deleteMin :: Ord a => Tree a -> Tree a
deleteMin (Fork n x a b) = merge a b

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

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 n x a b) c = Fork (n + size c) x aa (merge bb cc)
  where (aa, bb, cc) = orderBySize a b c

orderBySize :: Ord a => Tree a -> Tree a -> Tree a -> (Tree a, Tree a, Tree a)
orderBySize a b c
  | size a == biggest = (a, b, c)
  | size b == biggest = (b, a, c)
  | size c == biggest = (c, a, b)
  where biggest = size a `max` size b `max` size c

size :: Ord a => Tree a -> Int
size Null = 0
size (Fork n x a b) = n

exercise121 = foldr insert Null [1..7]
exercise122 = foldl (flip insert) Null [1, 7, 2, 6, 3, 5, 4]
exercise123 = deleteMin $ foldl (flip insert) Null [1..7]

main = do putStrLn("1.2.1:")
          print exercise121
	  putStrLn("1.2.2:")
          print exercise122
	  putStrLn("1.2.3:")
          print exercise123

本当は頭の中で解くことを意図してる気もするけど…。

Rubyだと何でも配列やハッシュで済ませてしまうので、便利ではあるんだけど、あまりこういう楽しみは味わえない。

同じ著者のPurely Functional Data Structuresが欲しいと思いつつ、洋書高いしなあと躊躇していたのだが、意外と『関数プログラミングの楽しみ』の方が高かった。 でもその価値はあると思う。