ある男の物語

Zipper Haskellで木構造の要素を変更したい場合、ルート要素から指定の要素が見つかるまで探索が必要になる。 また、前回更新した要素の近くの要素を更新したい場合などでもルートから探す必要がある。 これは効率が悪い。 そこでZipperを使ってデータ構造の…

モナドを作る モナドは作りたいと思って作るものではない。 ある問題の側面をモデル化した型を作り、 後からその型が文脈付きの値を表現していてモナドのように振る舞うとわかった場合に、 Monadインスタンスを与える場合が多い。 リスト [3,5,9] を、整数3,…

安全な逆ポーランド記法電卓をつくる 前に作ったRPN電卓にエラー機能をつける。 import Control.Monad solveRPN :: String -> Maybe Double solveRPN st = do [result] <- foldM foldingFunction [] $ words st return result foldingFunction :: [Double] -…

便利なモナディック関数 モナドを扱う関数はモナディック関数と呼ばれる。 liftM 関数とモナド値をとって、関数でモナド値を写してくれる。 fmapっぽい。 liftM :: Monad m => (a1 -> r) -> m a1 -> m r fmap の型 fmap :: Functor f => (a -> b) -> f a -> …

Eitherモナド Maybeモナドは値に失敗するかもしれないという文脈をつけられる。 Eitherモナドも失敗の文脈を扱える。しかも、失敗に値を付加できるので失敗の説明ができたりする。 Either e a は、Right値であれば正解や計算の成功、Left値であれば失敗を表…

計算の状態 状態を扱うためにHaskellにはStateモナドが用意されている。 状態付きの計算 状態付きの計算とは、ある状態を取って、更新された状態と一緒に計算結果を返す関数として表現できる。 s -> (a, s) s は状態の型で、 a は状態付き計算の結果。 この…

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

プログラムにログを追加する ユークリッド互除法。2つの数を取り、最大公約数を求めるアルゴリズム。 gcd関数を自前で作る gcd' :: Int -> Int -> Int gcd' a b | b == 0 = a | otherwise = gcd' b (a `mod` b) 実行 *Main> gcd' 8 3 1 8 と 3 の最大公約数…

Writer Writerモナドはもう1つの値がくっついた値を表し、付加された値はログのように振る舞う。 Writerモナドを使うと、一連の計算を行っている間全てのログが単一のログ値にまとめて記録されることを保証できる。 盗賊団の人数をとり、それが大きな盗賊団…

モナド則 ある型がMonadのインスタンスとなっていることは、その型が真にモナドであることを保証しない。 真にモナドになるために、ある型はモナド則を満たす必要がある。 左恒等性 return x >>= f と f x は等価である。 return がある値を最小限の文脈に入…

騎士の旅 チェス盤の上にナイトの駒が1つだけ乗っており、ナイトを3回動かして特定のマスまで移動させられるかという問題を解く。 type KnightPos = (Int, Int) moveKnight :: KnightPos -> [KnightPos] moveKnight (c,r) = do (c', r') <- [(c+2,r-1),(c+2,…

do 記法とリスト内包表記 リスト内包表記はリストモナドの構文糖衣である。 listOfTuples :: [(Int, Char)] listOfTuples = do n <- [1,2] ch <- ['a','b'] return (n, ch) ↓ *Main> [(n, ch) | n <- [1,2], ch <- ['a','b']] [(1,'a'),(1,'b'),(2,'a'),(2,'…

リストモナド 5という値は決定的である。一方、[1,2,3]のような値は複数の計算結果を含んでいるとも、複数の候補地を同時に重ね合わせたような1つの値であるとも解釈できる。 リストをアプリカティブスタイルで使う *Main> (*) <$> [1,2,3] <*> [10,100,1000…

ピエールリターンズ ピエールの綱渡りの一連の処理を do を使って書く routine :: Maybe Pole routine = do start <- return (0, 0) first <- landLeft 2 start second <- landRight 2 first landLeft 1 second 実行 *Main> routine Just (3,2) 手続き型のよ…

do 記法 do 記法は IOモナドだけでなく、他のモナドにも使える *Main Lib> Just 3 >>= (\x -> Just (show x ++ "!")) Just "3!" 入れ子にする *Main Lib> Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y))) Just "3!" let式と似ている *Main Lib>…

ピエールを落とす バナナを仕掛けてピエールを問答無用で落とす関数を作る banana :: Pole -> Maybe Pole banana _ = Nothing これを一連の関数の中に混ぜて使う *Main> return (0, 0) >>= landLeft 1 >>= banana >>= landRight 1 Nothing 落ちた。 入力に関…

ピエールの人生とは せっかくの休暇にバランス棒やってんのに鳥に邪魔されるピエール まず、鳥とポールを定義 その後に、ポールの右と左に鳥が止まる関数を定義 type Birds = Int type Pole = (Birds, Birds) landLeft :: Birds -> Pole -> Pole landLeft n …

モナド モナドは強化されたアプリカティブファンクターである。 モナドはある願いを叶えるための、アプリカティブ値の自然な拡張である。 願いとは、 普通の値 a を取って文脈付きの値を返す関数に、文脈付きの値 m a を渡したい というもの。 言い換えると…

モノイドで畳み込む いろいろなデータ構造の上に畳み込みを定義したい時にモノイドは便利。 *Main Lib F> F.foldr (*) 1 [1,2,3] 6 *Main Lib F> F.foldl (+) 2 (Just 9) 11 *Main Lib F> F.foldr (||) False (Just True) True もう少し複雑なデータ構造を畳…

リストはモノイド インスタンス宣言 instance Monoid [a] where mempty = [] mappend = (++) リストは中身の型がなんであっても常に Monoid のインスタンスにできる。 *Main> [1,2,3] `mappend` [4,5,6] [1,2,3,4,5,6] *Main> ("one" `mappend` "two") `mapp…

Monoid 大集合 以下のような共通の性質をもつ関数が存在する。 関数は引数を2つとる 2つの引数および返り値の型はすべて等しい 2引数関数を施して相手を変えないような特殊な値が存在する ++ なら空リスト * なら 1 例: x * 1, "hoho" ++ [] 例 *Main> (3 * …

newtype と 遅延評価 undefined という値がある。これは、ぶっ壊れた計算を表す。 この値を評価すると Haskell はすごく怒る。 *Main> undefined *** Exception: Prelude.undefined CallStack (from HasCallStack): error, called at libraries/base/GHC/Err…

モノイド Monoid は、値を2項演算子で結合できるような型を表現する。 newtype キーワード newtype キーワードを使うと、既存の型から新たな型を作ることができる。 リストをアプリカティブファンクターにする方法は複数ある。 左辺のリストの関数と右辺のリ…

アプリカティブの便利な関数 Control.ApplicativeにliftA2という関数がある。 liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c liftA2 f a b = f <$> a <*> b 1つの関数を2つのアプリカティブ値に適用する関数。 これを、 liftA2 :: (Appl…

Zipリスト ZipList という型があり、これは Applicative のインスタンスである。 instance Applicative ZipList where pure x = ZipList (repeat x) ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs) <*> は1つ目の関数を1つ目の値に、2…

IOはアプリカティブファンクター IO は Applicative instance Applicative IO where pure = return a <*> b = do f <- a x <- b return (f x) return は何もしない I/Oアクションを返す。 IOに関する <*> 演算子は、 2つのI/O アクションを1つに糊付けするに…

アプリカティブファンクターを使う 2引数関数でファンクター値を写すとどうなるか *Main> :t fmap (*) (Just 3) fmap (*) (Just 3) :: Num a => Maybe (a -> a) *Main> :t fmap compare (Just 'a') fmap compare (Just 'a') :: Maybe (Char -> Ordering) *Ma…

ファンクター則 Functor のインスタンスはファンクター則の2つの性質を満たす必要がある。 自前のファンクターを作る時はこの性質を満たす必要がある。 第1法則 idでファンクター値を写した場合、ファンクター値が変化してはいけない idは引数をそのまま返す…

アプリカティブファンクター ファンクターとは関数で写せるもののこと。リスト、Maybe、木など。 *Main Lib> :i Functor class Functor (f :: * -> *) where fmap :: (a -> b) -> f a -> f b (<$) :: a -> f b -> f a {-# MINIMAL fmap #-} -- Defined in ‘G…