Journal InTime


2011-11-12 (Sat) [長年日記]

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

湿潤治療の本を買うために今井書店に行ったら 関数プログラミングの楽しみ(Jeremy Gibbons and Oege de Moor/山下 伸夫)が置いてあったので、つい購入してしまった。 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(Chris Okasaki)が欲しいと思いつつ、洋書高いしなあと躊躇していたのだが、意外と『関数プログラミングの楽しみ』の方が高かった。 でもその価値はあると思う。

Tags: Haskell