最大回避ヒープ。この章ではjoinの仕方を色々工夫する。他にラウンドロビンヒープとかねじれヒープなどがある。

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

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

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 Null = 0
size (Fork n x a b) = n

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

オーム社 / ￥ 4,410 ()
在庫あり。

いきなり最初の章から面白い。

*Main> insert 5 $ insert 4 $ insert 3 $ insert 2 $ insert 1 Null Fork 5 1 (Fork 2 3 (Fork 1 4 Null Null) Null) (Fork 2 2 (Fork 1 5 Null Null) Null)

プログラミングHaskell 9章の練習問題やってないとかいいつつなぜか関数プログラミングの楽しみが手元にあるのであった。

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

オーム社 / ￥ 4,410 ()
在庫あり。

明後日のHaskell読書会は9章なんだけど、練習問題やってない。

堕落だ。

プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
在庫あり。

あと、浜松の遠さに驚いた。というか浜松なめてた。八百徳いけるか？

先週末はHaskell読書会に参加してきた。みなさんお疲れ様でした。今回8章

プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
在庫あり。

do記法使わないで書いてあったので当日は、 筆者のページのサンプル見ながらdo記法で書いてた。

この日からガンダムの公開で、ヒトも多かった。

メロンパン

懇親会の赤から。焼肉した後に鍋が出てきた。

来月は浜松。浜松は行ったことないので楽しみ。

パーサーから直接書き出すようにしたいが、とりあえず。

import Data.Graph.Inductive
import Data.Graph.Inductive.Graphviz

labUEdges :: [Edge] -> [UEdge]
labUEdges = map (\(i,j) -> (i,j,()))

exprt :: Gr String ()
exprt = mkGraph (zip [1..5] ["2","*","3","+","4"]) 
(labUEdges [(2,1),(2,3),(4,2),(4,5)])

main = do putStrLn $ graphviz exprt "test" (0,0) (0,0) Portrait

コンパイルするには--makeオプションをつけて

$ ghc gvtest.hs --make
[1 of 1] Compiling Main             ( gvtest.hs, gvtest.o )
Linking gvtest ...
$ ./gvtest | dot -Tpng > gvtest.png; open gvtest.png

関数型パーサー。復習を兼ねてもう一度

プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
在庫あり。

import Data.Char
type Parser a = String -> [(a,String)]


myreturn :: a -> Parser a
myreturn v = \inp ->[(v,inp)]

myfailure :: Parser a
myfailure = \inp -> []

item :: Parser Char
item = \inp -> case inp of
                 [] -> []
                 (x:xs) -> [(x,xs)] 

parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp

(>>==) :: Parser a -> (a -> Parser b) -> Parser b
p >>== f = \inp -> case parse p inp of
                     [] -> []
                     [(v,out)] -> parse (f v) out

--p :: Parser (Char, Char)
--p = item >>== \v -> (item >>== \w -> (item >>== \z -> myreturn (v,z)))

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case parse p inp of
                    [] -> parse q inp
                    [(v, out)] -> [(v, out)]

sat :: (Char -> Bool) -> Parser Char
sat p = item >>== \x -> if p x then myreturn x else myfailure

digit :: Parser Char
digit = sat isDigit

lower :: Parser Char
lower = sat isLower

upper :: Parser Char
upper = sat isUpper

letter :: Parser Char
letter = sat isAlpha

alphanum :: Parser Char
alphanum = sat isAlphaNum

char :: Char -> Parser Char
char x = sat (==x)

string :: String -> Parser String
string [] = myreturn []
string (x:xs) = char x >>== \x -> string xs >>== \xs -> myreturn (x:xs)

many :: Parser a -> Parser [a]
many p = many1 p +++ myreturn []
many1 :: Parser a -> Parser [a]
many1 p = p >>== \v -> many p >>== \vs -> myreturn (v:vs)

ident :: Parser String
ident = lower >>== \x -> (many alphanum >>== \xs -> myreturn (x:xs))

nat :: Parser Int
nat = many1 digit >>== \xs -> myreturn (read xs)

space :: Parser ()
space = many (sat isSpace) >>== \_ -> myreturn ()

token :: Parser a -> Parser a
token p = space >>== \_ -> p >>== \v -> space >>== \_ -> myreturn v

identifier :: Parser String
identifier = token ident

natural :: Parser Int
natural = token nat

symbol :: String -> Parser String
symbol xs = token (string xs)

--p :: Parser [Int]
--p = symbol "[" >>== \_ -> natural >>== \n -> many (symbol "," >>== \_ ->
--    natural) >>== \ns -> symbol "]" >>== \_ -> myreturn (n:ns)


expr :: Parser Int
expr = term >>== \t -> ((symbol "+" >>== \_ -> expr >>== \e -> myreturn (t + e)) +++ myreturn t)

term :: Parser Int
term = factor >>== \f -> ((symbol "*" >>== \_ -> term >>== \t -> myreturn (f * t)) +++ myreturn f)

factor :: Parser Int
factor = (symbol "(" >>== \_ -> expr >>== \e -> symbol ")" >>== \_ -> myreturn e) +++ natural

eval :: String -> Int
eval xs = case parse expr xs of
            [(n,[])]  -> n
            [(_,out)] -> error ("unused input " ++ out)
            []        -> error "invalid input"

昨日のHaskell読書会の行き帰りの電車の中で読もうかと思ったけど、そんな軽い本じゃなかった。

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

オーム社 / 4410円 ( 2010-06-23 )

かなり濃いめな感じの本だ。

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

昨日は第六回Haskell読書会に行ってきた。参加された皆様お疲れ様でした。

演習問題7.5

sumsqreven compose [sum,map (^2),filter even]が間違っている理由を述べよ

という問題で

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

composeはa -> aという型の関数のリストを引数として取る。

ここで

Prelude> :t (map (^2))
(map (^2)) :: (Num a) => [a] -> [a]
Prelude> :t (filter even)
(filter even) :: (Integral a) => [a] -> [a]
Prelude> :t sum
sum :: (Num a) => [a] -> a

となりsumだけ [a] -> aという型なのでダメ。

sumがなければOKで、これは

:t compose [(map (^2)),(filter even)]
compose [(map (^2)),(filter even)] :: (Integral a) => [a] -> [a]

という型になる。

プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
在庫あり。

7章で感じたのはfoldr,foldlがさくっと出てきて戸惑うのと、関数合成がさらっと流しすぎなとこ。foldl,foldrは知っているのが前提なのかな？と思った。

SICPの1,2章でも読んでおけば違うかも。

計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン,ジュリー サスマン,ハロルド エイブルソン
ピアソンエデュケーション / ￥ 4,830 ()
在庫あり。

関数合成は他の本を読みましょう。

8章はちょっと難しいので、次回は予習して臨む。

来週の土曜日に第二回Haskell読書会が静岡であります。

プログラミングHaskellの3章を読みます。

プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
在庫あり。

次の日は朝から簿記試験なので、懇親会にはまたもやでられない。残念。

なんか慣れない。

scala> Array(1,2,3) zip Array(4,5,6)
res1: Array[(Int, Int)] = Array((1,4), (2,5), (3,6))

Haskellだとこんな感じでしょ。

Prelude> [1,2,3] `zip` [4,5,6]
[(1,4),(2,5),(3,6)]

Pythonだと

[1,2,3].zip([4,5,6])

とはできない。

>>> zip([1,2,3],[4,5,6])
[(1, 4), (2, 5), (3, 6)]