前回は, すごいhaskellたのしく学ぼう!の9章までを紹介しました。引き続き10-15章を紹介します。
第10章 関数型問題解決法
10.1 逆ポーランド記法電卓
10.2 ヒースロー空港からロンドンへ
10章ではこれまでのテクニックを踏まえて、逆ポーランド記法、最短経路問題を解きます。
最短経路問題は遅延評価が生きてくる問題です。
$ runghc optimal_path.hs < paths.txt
([(C,30),(B,10)],[(B,10)])
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]
best path is BCACBBC
Time Taken : 75
第11章 ファンクターからアプリカティブファンクターへ
11.1 帰ってきたファンクター
11.2 ファンクター則
11.3 アプリカティブファンクターを使おう
11.4 アプリカティブの便利な関数
11章ではFunctor, ApplicativeFunctorを扱います。
import Control.Applicative
main = do
print $ [(+),(*)] <*> [1,2] <*> [3,4]
$ runghc functor_list.hs
[4,5,5,6,3,4,6,8]
第12章 モノイド
12.1 既存の型を新しい型にくるむ
12.2 Monoid大集合
12.3 モノイドとの遭遇
12.4 モノイドで畳み込む
12章では既存の型から新しい型をつくるnewtype, またMonoidを扱います。
Monoidは0 (単位元)と足し算に相当するするような値 (二項演算)が定義されている何かのことです。
さらにそれに加えて, Monoid則に沿っている必要があります。
Monoidが特に力を発揮するのは, 畳み込みを行うときです。
import Data.Monoid
-- normal style
lengthCompareNs :: String -> String -> Ordering
lengthCompareNs x y = let
a = length x `compare` length y
b = x `compare` y
in if a == EQ then b else a
-- monoid style
lengthCompareMs :: String -> String -> Ordering
lengthCompareMs x y = (length x `compare` length y) `mappend` (x `compare` y)
main = do
-- mempty
print $ LT `mappend` GT
print $ mempty `mappend` GT
-- try two-style
print $ lengthCompareNs "zen" "ants"
print $ lengthCompareNs "ants" "zen"
print $ lengthCompareMs "zen" "ants"
print $ lengthCompareMs "ants" "zen"
第13章 モナドがいっぱい
13.1 アプリカティブファンクターを強化する
13.2 Maybeから始めるモナド
13.3 Monad型クラス
13.4 綱渡り
13.5 do記法
13.6 リストモナド
13.7 モナド則
13章ではついにMonadが登場します。MonadはApplicativeFunctorの強化版です。
より抽象的には, 文脈を伴う計算同士, 特に失敗する可能性のある計算同士を組み合わせ可能にする仕組みです。
ピエールがロープから落ちないようにバランスを取るプログラムを通じてMaybeの練習をします。
do記法 (Do notation)は >>=の糖衣構文で, IOアクションを繋ぎ合わせることができます。
doブロック内は手続き型言語のようなスタイルになります。
type Birds = Int
type Pole = (Birds, Birds)
landLeft :: Birds -> Pole -> Maybe Pole
landLeft n (left, right)
| abs ((left + n) - right) < 4 = Just (left + n, right)
| otherwise = Nothing
landRight :: Birds -> Pole -> Maybe Pole
landRight n (left, right)
| abs (left - (right + n)) < 4 = Just (left, right+ n)
| otherwise = Nothing
banana :: Pole -> Maybe Pole
banana _ = Nothing
routine :: Maybe Pole
routine = do
let start = (0,0)
first <- landLeft 2 start
second <- landRight 2 first
landLeft 1 second
main = do
print $ landLeft 2 (0,0)
print $ landRight 10 (0,3)
-- use >>=
print $ return (0,0) >>= landLeft 2 >>= landRight 2 >>= landLeft 2
print $ return (0,0) >>= landLeft 2 >>= landLeft 2
print $ return (0,0) >>= landLeft 1 >>= banana >>= landRight 1
print routine
マス目を移動する騎士の移動プログラムです。
import Control.Monad
type KnightPos = (Int, Int);
-- move
moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = do
(c',r') <- [(c+2, r-1), (c-2, r+1), (c-2, r-1), (c+1, r-2), (c+1, r+2), (c-1, r-2), (c-1, r+2)]
guard (c' `elem` [1..8] && r' `elem` [1..8])
return (c', r')
-- step
in3 :: KnightPos -> [KnightPos]
in3 start = do
first <- moveKnight start
second <- moveKnight first
moveKnight second
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start
main = do
print $ moveKnight (6,2)
print $ moveKnight (8,1)
print $ (6,2) `canReachIn3` (6,1)
print $ (7,3) `canReachIn3` (7,1)
第14章 もうちょっとだけモナド
14.1 Writer？中の人なんていません！
14.2 Reader？それはあなたです！
14.3 計算の状態の正体
14.4 Errorを壁に
14.5 便利なモナディック関数特集
14.6 安全な逆ポーランド記法電卓を作ろう
14.7 モナディック関数の合成
14.8 モナドを作る
14章ではMonadsのwriterモナド, readerモナド, stateモナドを扱います。
先ほどの騎士の移動プログラムで登場したin3を一般化したinMany関数を作ります。
Monadは文脈を持つ仕組みですが, 例として上記モナドは下記の文脈を持ちます。
- writerモナド : 必要な計算の横で, 余分な別の値を一直線で合成します。アクションの代表例として, tell等。
- readerモナド : 参照できる環境を共有します。アクションの代表例として, ask等。
- stateモナド : 状態の変更を引き継ぎます。アクションの代表例として, get/put等
他にも代表的なモナドに, IOモナド, Eitherモナド, STモナド, STMモナドなどがあります。
import Control.Monad
type KnightPos = (Int, Int);
-- move
moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = do
(c',r') <- [(c+2, r-1), (c-2, r+1), (c-2, r-1), (c+1, r-2), (c+1, r+2), (c-1, r-2), (c-1, r+2)]
guard (c' `elem` [1..8] && r' `elem` [1..8])
return (c', r')
-- just 3 step
in3 :: KnightPos -> [KnightPos]
in3 start = do
first <- moveKnight start
second <- moveKnight first
moveKnight second
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start
-- inMany
inMany :: Int -> KnightPos -> [KnightPos]
inMany x = foldr (<=<) return (replicate x moveKnight)
canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start
main = do
print $ moveKnight (6,2)
print $ moveKnight (8,1)
print $ (6,2) `canReachIn3` (6,1)
print $ (7,3) `canReachIn3` (7,1)
print $ canReachIn 3 (1, 4) (1, 6)
print $ canReachIn 3 (1, 3) (1, 6)
第15章 Zipper
15.1 歩こう
15.2 リストに注目する
15.3 超シンプルなファイルシステム
15.4 足下にご注意
15.5 読んでくれてありがとう！
最終章である15章ではデータ構造の要素の扱いを簡単にできます。
ある注目点をデータ構造によって上下させるzipperを扱います。zipperの名前の由来はズボンのジップに動作が似ているためです。
木構造をzipperで移動してみます。
ata Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
data Direction = L | R deriving (Show)
type Directions = [Direction]
data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)
type Breadcrumbs a = [Crumb a]
type Zipper a = (Tree a, Breadcrumbs a)
x -: f = f x
goLeft :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goLeft (Node x l r, bs) = (l, LeftCrumb x r : bs)
goRight :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goRight (Node x l r, bs) = (r, RightCrumb x l : bs)
goUp :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goUp (t, LeftCrumb x r : bs) = (Node x t r, bs)
goUp (t, RightCrumb x l : bs) = (Node x l t, bs)
changeToP :: Directions -> Tree Char -> Tree Char
changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r
changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r)
changeToP [] (Node _ l r) = Node 'P' l r
elemAt :: Directions -> Tree a -> a
elemAt (L:ds) (Node _ l _) = elemAt ds l
elemAt (R:ds) (Node _ _ r) = elemAt ds r
elemAt [] (Node x _ _ ) = x
modify :: (a -> a) -> Zipper a -> Zipper a
modify f (Node x l r, bs) = (Node (f x) l r, bs)
modify f (Empty, bs) = (Empty, bs)
attach :: Tree a -> Zipper a -> Zipper a
attach t (_, bs) = (t, bs)
freeTree :: Tree Char
freeTree =
Node 'P'
(Node 'O'
(Node 'L'
(Node 'N' Empty Empty)
(Node 'T' Empty Empty)
)
(Node 'Y'
(Node 'S' Empty Empty)
(Node 'A' Empty Empty)
)
)
(Node 'L'
(Node 'W'
(Node 'C' Empty Empty)
(Node 'R' Empty Empty)
)
(Node 'A'
(Node 'A' Empty Empty)
(Node 'C' Empty Empty)
)
)
main = do
let newTree = changeToP [R,L] freeTree
print $ elemAt [R,L] newTree
print $ goLeft ( goRight (freeTree, []))
print $ (freeTree, []) -: goRight -: goLeft
let newFocus = (freeTree, []) -: goLeft -: goRight -: modify (const 'p')
print newFocus
本にちりばめられたジョークが面白かったです。日本語訳も良かったと思います。
" さて今度はバランス棒にとまっている鳥の数によらずに、いきなりピエールを滑らせて落っことす関数を作ってみましょう。"
" bananaはおかまいなしにNothingを返すので、以降のすべての結果はNothingになってしまいます。残念でした！ "
" Maybeモナドを使うと失敗するかもしれない処理が連続するコードをとても簡潔に書けるのです。"
" filterはhaskellプログラミングの米といっても過言ではないでしょう。(mapが塩です) "
Haskellに関しては, 命令型/手続き型プログラミング脳から関数型/宣言型プログラミング脳への頭の切り替えがまだまだ足りないと感じた。
CodeはGiHubにあります。
[1] Haskell の Monad とは言語内DSLのフレームワークである - あどけない話
[2] ウォークスルー Haskell
[3] 第12章 モノイド