fugafuga.write

日々のログ

すごいH本 part97

安全な逆ポーランド記法電卓をつくる

前に作ったRPN電卓にエラー機能をつける。

import           Control.Monad

solveRPN :: String -> Maybe Double
solveRPN st = do
    [result] <- foldM foldingFunction [] $ words st
    return result

foldingFunction :: [Double] -> String -> Maybe [Double]
foldingFunction (x:y:ys) "*"    = return ((y * x):ys)
foldingFunction (x:y:ys) "+"    = return ((y + x):ys)
foldingFunction (x:y:ys) "-"    = return ((y - x):ys)
foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)

readMaybe :: (Read a) => String -> Maybe a
readMaybe st = case reads st of [(x, "")] -> Just x
                                _         -> Nothing

実行

*Main> solveRPN "1 2 * 4 +"
Just 6.0
*Main> solveRPN "1 2 * 4 + 5 *"
Just 30.0
*Main> solveRPN "1 2 * 4"
Nothing
*Main> solveRPN "1 8 werasdfasdefih"
Nothing

モナディック関数の合成

第13章で <=< は関数合成によく似ているけど普通の関数 a -> b ではなく、 a -> m b のようなモナディック関数に作用するということが書かれていた。

*Main> let f = (+1) . (*100)
*Main> f 4
401
*Main> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))
*Main> Just 4 >>= g
Just 401

複数の関数をリストに持っているとき、 全部合成して1つの関数を作る場合は id をアキュムレータ、. を2引数関数として畳み込むとよい。

*Main> let f = foldr (.) id [(+8),(*100),(+1)]
*Main> f 1
208

モナディック関数も同じように合成できる。 . の代わりに <=<id の代わりに return を使うとよい。

前にチェスのナイトを3手以内で移動できるかどうか判定するプログラムを改良する。

import           Control.Monad

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = do
    (c', r') <- [(c+2,r-1),(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')

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

モナディックに合成して、より一般化する

import           Control.Monad
import           Data.List

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = do
    (c', r') <- [(c+2,r-1),(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')

inMany :: Int -> KnightPos -> [KnightPos]
inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start

moveKnight を replicate して指定した数だけ実行できるようにしている。

実行

*Main> canReachIn 5 (0,0) (8,3)
True

所感

文脈もたせたまま処理できる術がちゃんと用意されている。使えるようになるまでは時間かかりそうである。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part96

便利なモナディック関数

モナドを扱う関数はモナディック関数と呼ばれる。

liftM

関数とモナド値をとって、関数でモナド値を写してくれる。 fmapっぽい。

liftM :: Monad m => (a1 -> r) -> m a1 -> m r

fmap の型

fmap :: Functor f => (a -> b) -> f a -> f b

ファンクター則とモナド則を満たしている場合、fmap と liftM はまったく同じものになる。

liftM を試す

*Main> liftM (*3) (Just 8)
Just 24
*Main> fmap (*3) (Just 8)
Just 24
*Main> runWriter $ liftM not $ writer (True, "chickpeas")
(False,"chickpeas")
*Main> runWriter $ fmap not $ writer (True, "chickpeas")
(False,"chickpeas")
*Main> runState (liftM (+100) pop) [1,2,3,4]
(101,[2,3,4])
*Main> runState (fmap (+100) pop) [1,2,3,4]
(101,[2,3,4])

fmap と liftM は同じ動きしてる。

次はアプリカティブ値

*Main> (+) <$> Just 3 <*> Just 5
Just 8
*Main> (+) <$> Just 3 <*> Nothing
Nothing

<$>はただのfmap。<*>はこう

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

fmap に似ているが、関数自身も文脈の中に入っている。

ap という関数があり、本質的には<*>と同じだが、Applicativeの代わりにMonad型クラス制約がついている。

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf m = do
    f <- mf
    x <- m
    return (f x)

mf は結果が関数であるようなモナド値。

使ってみる

*Main> Just (+3) <*> Just 4
Just 7
*Main> Just (+3) `ap` Just 4
Just 7
*Main> [(+1),(+2),(+3)] <*> [10,11]
[11,12,12,13,13,14]
*Main> [(+1),(+2),(+3)] `ap` [10,11]
[11,12,12,13,13,14]

モナドの威力は少なくともアプリカティブやファンクター以上である。 すべてのモナドはファンクターでもアプリカティブでもあるのにそのインスタンスになっているとは限らない。 また、ファンクターやアプリカティブファンクターが使う関数と等価なモナド版の関数が存在する。

join

任意の入れ子になったモナドは平らにできる。 このために join がある。

join :: (Monad m) => m (m a) -> m a

使ってみる

*Main> join (Just (Just 9))
Just 9
*Main> join (Just Nothing)
Nothing
*Main> join Nothing
Nothing
*Main> join [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]
*Main> runWriter $ join (writer (writer (1, "aaa"), "bbb"))
(1,"bbbaaa")
*Main> join (Right (Right 9))
Right 9
*Main> join (Right (Left "error"))
Left "error"
*Main> join (Left "error")
Left "error"
*Main> runState (join (state $ \s -> (push 10, 1:2:s))) [0,0,0]
((),[10,1,2,0,0,0])

filterM

filter関数は、Haskellプログラミングの米らしい。 map は塩らしい。

filterは述語とフィルタ対象のリストを取り、述語を満たす要素だけを残してくれる。

filter :: (a -> Bool) -> [a] -> [a]

文脈を持った値を filterしたい場合、filterMを使う。Control.Monad モジュールに定義されている。

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

リストを取って、4より小さい要素だけを残す関数。

*Main> filter (\x -> x < 4) [9,1,5,2,10,3]
[1,2,3]

True か False だけを返すのではなく、何をしたかのログを残すような述語を作る。

import           Control.Monad.Writer.Lazy

keepSmall :: Int -> Writer [String] Bool
keepSmall x
    | x < 4 = do
        tell ["Keeping " ++ show x]
        return True
    | otherwise = do
        tell [show x ++ " is too large, throwning it away"]
        return False

実行

*Main> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
[1,2,3]

ログを表示してみる

*Main> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
9 is too large, throwning it away
Keeping 1
5 is too large, throwning it away
Keeping 2
10 is too large, throwning it away
Keeping 3

filterM を使って冪集合を作る

powerset :: [a] -> [a]
powerset xs = filterM (\x -> [True, False]) xs

実行

*Main> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

foldM

foldl のモナド版が foldM

foldl の型

foldl :: (a -> b -> a) -> a -> [b] -> a

foldM の型

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

foldl 使ってみる

*Main> foldl (\acc x -> acc + x) 0 [2,8,3,1]
14

整数のリストを加算したいが、リストのいずれかの要素が9より大きい場合、 計算全体を失敗させたい。Maybeアキュムレータを返すようにする。

import           Control.Monad

binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
    | x > 9 = Nothing
    | otherwise = Just (acc + x)

実行

*Main> foldM binSmalls 0 [2,8,3,1]
Just 14
*Main> foldM binSmalls 0 [2,11,3,1]
Nothing

リストに9より大きい数が入っている場合、Nothingになっている。

所感

モナディック関数。中2っぽくてよい。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part95

Eitherモナド

Maybeモナドは値に失敗するかもしれないという文脈をつけられる。 Eitherモナドも失敗の文脈を扱える。しかも、失敗に値を付加できるので失敗の説明ができたりする。

Either e a は、Right値であれば正解や計算の成功、Left値であれば失敗を表す。

*Main Lib> :t Right 4
Right 4 :: Num b => Either a b
*Main Lib> :t Left "out of cheese error"
Left "out of cheese error" :: Either [Char] b

EitherのMonadインスタンスはMaybeとよく似ている。 Control.Monad.Error モジュールで定義されている。

instance (Error e) => Monad (Either e) where
    return x = Right x
    Right x >>= f = f x
    Left err >>= f = Left err
    fail msg = Left (strMsg msg)

Left e の e は、Error型クラスのインスタンスでないといけない。 Error型クラスはエラーメッセージのように振る舞える型クラス。 Error型クラスにはエラーを文字列として受け取って、その型に変換する strMsg 関数が定義されている。

モジュールロード時に以下内容の警告が出た。

<interactive>:1:1: warning: [-Wdeprecations]
    In the use of ‘strMsg’
    (imported from Control.Monad.Error, but defined in transformers-0.5.2.0:Control.Monad.Trans.Error):
    Deprecated: "Use Control.Monad.Trans.Except instead"
strMsg :: Error a => String -> a

Control.Monad.Trans.Except を使ったほうがよさそうである。

strMsg :: Error a => String -> a

String を受け取って Error型に変換する

Eitherを使ってみる

*Main Lib> Left "boom" >>= \x -> return (x+1)
Left "boom"
*Main Lib> Left "boom " >>= \x -> Left "no way!"
Left "boom "
*Main Lib> Right 100 >>= \x -> Left "no way!"
Left "no way!"

Maybeぽい動きをしている。

Right を成功する関数に渡すパターン

*Main Lib> Right 3 >>= \x -> return (x + 100)
Right 103

成功した...

本の中では型シグネチャが無いとエラーになると書いてあった

*Main Lib> Right 3 >>= \x -> return (x + 100) :: Either String Int
Right 103

こんな感じで指定する

練習問題

以前やったピエールのバランス棒に何羽の鳥が止まっていたかわかるようにする。

import           Control.Monad.Except

type Birds = Int
type Pole = (Birds, Birds)

landLeft :: Birds -> Pole -> Either String Pole
landLeft n (left, right)
    | abs (left + n - right) < 4 = Right (left + n, right)
    | otherwise = Left $ birdsCount (left, right)

landRight :: Birds -> Pole -> Either String Pole
landRight n (left, right)
    | abs (left - (right + n)) < 4 = Right (left, right + n)
    | otherwise = Left $ birdsCount (left, right)

birdsCount :: Pole -> String
birdsCount (left, right) = "Pierre fell off the rope!!" ++
                            " birds on the left: " ++ show left ++
                            ",birds on the right: " ++ show right

banana :: Pole -> Either String Pole
banana p = Left $ birdsCount p

routine :: Either String Pole
routine = do
    start <- return (0, 0)
    first <- landLeft 2 start
    second <- landRight 2 first
    third <- landLeft 1 second
    banana third

最終的にバナナで滑って落ちるようにした。

実行

*Main> routine
Left "Pierre fell off the rope!! birds on the left: 3,birds on the right: 2"

最後のバナナを取り除き、落ちないパターン

*Main> routine
Right (3,2)

所感

初めて自分の力で練習問題ができたように思う。嬉しい。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part94

計算の状態

状態を扱うためにHaskellにはStateモナドが用意されている。

状態付きの計算

状態付きの計算とは、ある状態を取って、更新された状態と一緒に計算結果を返す関数として表現できる。

s -> (a, s)

s は状態の型で、 a は状態付き計算の結果。 このような状態付きの計算も、文脈付きの値だとみなすことができる。 計算の結果が「生の値」 であり、その計算結果を得るためには初期状態を与える必要があること、 そして、計算の結果を得るのと同時に新しい状態が得られるというのが文脈にあたる。

スタックと石

stackデータ構造をモデル化する。

  • Push : スタックのてっぺんに要素を積む
  • Pop : スタックのてっぺんの要素を取り除く
type Stack = [Int]

pop :: Stack -> (Int, Stack)
pop (x:xs) = (x, xs)

push :: Int -> Stack -> ((), Stack)
push a xs = ((), a:xs)

スタックをシミュレートするコードを書く

stackManip :: Stack -> (Int, Stack)
stackManip stack = let
    ((), newStack1) = push 3 stack
    (a, newStack2) = pop newStack1
    in pop newStack2

実行

*Main> stackManip [5,8,2,1]
(5,[8,2,1])

ところが、Stateモナドを使うと次のように書けちゃう

stackManip = do
    push 3
    a <- pop
    pop

Stateモナド

Control.Monad.Stateモジュールは、状態付き計算を包んだ newtype を提供している。

newtype State s a = State { runState :: s -> (a, s) }

State s a は s 型の状態を操り、a 型の結果を返す状態付き計算。

状態付き計算のMonadインスタンス

instance Monad (State s) where
    return x = State $ \x -> (x, s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State, g) = f a
                                    in g newState

return は値を取って常にその値を結果として返すような状態付き計算。 >>= は2つの状態付き計算を繋げられる。

先程の処理をStateモナド使って書き換える

import Control.Monad.State

pop :: State Stack Int
pop = state $ \(x:xs) -> (x, xs)

push :: Int -> State Stack ()
push a = state $ \xs -> ((), a:xs)

stackManip :: State Stack Int
stackManip = do
    push 3
    a <- pop
    pop

実行

*Main> runState stackManip [5,8,2,1]
(5,[8,2,1])

pop の結果 a は一度も使っていないのでこう書ける

stackManip :: State Stack Int
stackManip = do
    push 3
    pop
    pop

もう少し複雑なスタックの処理を書く。 スタック1つの数を取り出して、5だったら元に戻す。 5ではなかった場合、3と8を積む。

stackStuff :: State Stack ()
stackStuff = do
    a <- pop
    if a == 5
        then push 5
        else do
            push 3
            push 8

実行

*Main> runState stackStuff [9,0,1,2,0]
((),[8,3,0,1,2,0])

stackManip と stackStuff はどちらも状態付き計算なのでこの2つをつなげることができる。

moreStack :: State Stack ()
moreStack = do
    a <- stackManip
    if a == 100
        then stackStuff
        else return ()

実行

*Main> runState moreStack [100,9,3,6,22,1,0]
((),[8,3,3,6,22,1,0])

状態の取得と設定

Stateモナドを扱うための便利な型クラスMonadStateがある。 get と put という関数が使える。

get の実装

get = state $ \s -> (s, s)

put の実装

put newState = state $ \s -> ((), newState)

put と get を使う

stackeyStack :: State Stack ()
stackeyStack = do
    stackNow <- get
    if stackNow == [1,2,3]
        then put [8,3,1]
        else put [9,2,1]

get と put を使って pop と push を書き換える

pop :: State Stack Int
pop = do
    (x:xs) <- get
    put xs
    return x

push :: Int -> State Stack ()
push x = do
    xs <- get
    put (x:xs)

乱数とStateモナド

Stateモナド使って乱数を扱う処理を書く

import System.Random
import Control.Monad.State

randomSt :: (RandomGen g, Random a) => State g a
randomSt = state random

乱数ジェネレーターは状態付き計算であるので、state関数を使ってStateのnewtypeに包めば、 状態の扱いをモナドに任せることができる。

コインを3枚投げる処理はこう書けるようになる。

threeCoins :: State StdGen (Bool, Bool, Bool)
threeCoins = do
    a <- randomSt
    b <- randomSt
    c <- randomSt
    return (a, b, c)

実行

*Main> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)

所感

だいたいわからん。複雑なモナドになるとコードが何してるかわからなくなる。 とりあえず前に進むこととする。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part93

Reader

関数の型 (->) r はファンクターであり、アプリカティブファンクターであるばかりでなく、モナドでもある。 関数にとっての文脈とは、値がまだ手元になく、値がほしければその関数を別の何かに適用しないといけない。 というもの。

instance Monad ((->) r) where
    return x = \_ -> x
    h >>= f = \w -> f (h w) w

return は最小限の文脈。値を取って値を返す。引数を無視すると必ず同じ値を返す。 >>=は、モナド値を入力してモナド値を返すので、ある関数を別の関数に入力した結果として関数を返す。 この場合、f に h を適用している。

Readerモナド

関数モナドを使っている do 式

import Control.Monad.Instances

addStuff :: Int -> Int
addStuff = do
    a <- (*2)
    b <- (+10)
    return (a+b)

実行

*Main> addStuff 3
19

do式は常にモナド値を生み出すもの。この場合、do式は関数モナドを返す。 (*2)(+10)はどちらも3に適用される。return (a+b)も3に適用されるが、 引数を無視して常にa+bを返している。

関数モナドはReaderモナドと呼ばれている。全ての関数が共通の情報を読むから。

最後の引数が届くのを待っている関数がたくさんあって、 しかもそれらに渡したい値は全部同じという状況であればReaderモナドを使って未来の結果を取り出すことができる。

所感

理解が苦しくなってきた。モナドをはじめから復習する必要がある。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る