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

第1章はじめの第一歩

プリミティブ、リスト、タプルの操作の話

第2章型を信じろ

:: は「の型を持つ」と読む
Char はUnicode文字
型クラス
- 何らかの振る舞いを定義するインターフェース
- 型クラスのインスタンスは型である
  - 型は型クラスが記述する振る舞いを実装する
- 具体的に言うと、（実行できる）関数の集合
  - メソッドとも言う
- ある型を型クラスのインスタンスにする場合、型クラスに集められた関数がその型でどのような意味を成すかを定義する
  - 逆説的に、関数はどの型クラスに対して意味を成すかを指定できる
    - 型クラス成約

第3章関数の構文

第4章 Hello 再帰

第5章高階関数

$ ($ x f)
- 関数f をx に適用する
.
- 関数合成する
- f.g x ⇒f(g x)
foldl
- 左から畳み込むが、遅延評価するのでアキュムレータの評価はされず、先送りするためにスタックに積んでから次の要素を見に行くため、やばいとスタックオーバーフローする

第6章モジュール

第7章型や型クラスを自分で作ろう

型を作る

data キーワード
- 代数的データ型を表す
- 型コンストラクタ
```
```haskell
  data Maybe a = ~ a | ~
```
```
  - 型を引数にとって新しい型を作る（a が型引数）
  - data の左辺が型コンストラクタ
    - 実際の値を生成するときに必ず型が設定される必要がある
  - 型ではない！
    - 型引数をとって具体型を生み出すコンストラクタである
  - 部分適用が可能
- 値コンストラクタ
```
```haskell
  data ~ = Circle Float Float Float | Rectangle Float Float Float Float
```
```
  - 指定された型の値を返す（生成する）関数
  - data の右辺が値コンストラクタ
  - 型ではない！
    - フィールドに指定された型の値を引数にとって具体型の値を生み出すコンストラクタである
      - Circle やRectangle は~ 型の値を生成するための関数である
  - パターンマッチできる
```
  ```haskell
      func (Circle a b c) = ...
  ```
```
    - パターンマッチとは値コンストラクタをマッチさせることに他ならない！
- 作成方法
  - 型コンストラクタも値コンストラクタも大文字から始める
  - フィールド名無し
```
  ```haskell
      data TupleLike = TupleLike String Float Float
      let t = TupleLike "ShapeName" 10 10
  ```
```
  - フィールド名有り（レコード構文）
```
  ```haskell
      data Record = Record { height :: Float, width :: Float }
      let r = Record {height=220.1, width=154.3}
  ```
```
    - データ型とそのフィールドの値を取得する関数が自動的に作られる
Haskellにおいて、:: の右側は型の世界
- Just 3 :: Maybe Int とするとInt 型を持つMaybe 型とできる
型引数を使うのは、そのデータ型の値コンストラクタに収納された型がデータ型自体の動作にそこまで重要な影響を与えないとき
Haskellでは、データ宣言には決して型クラス制約を付けないコーディング規則がある
- 型クラス制約を付けてしまうと、そのデータ型を引数に取る関数に対しても型クラス制約を付ける必要がある
  - Rustとかそう（ちょっとめんどくさい）
  - 引数に取る関数側で制約を設けたほうがその関数が満たす性質をより表明できて良いと感じた（個人的感想）
    - データ型はあくまで型の集合として考えて、型のある特定の部分集合に対しての関数はその関数側にそれを指定すべき
型シノニム
- 型の別名
```
```haskell
  type String = [Char]
```
```
- ただの型ではなくこういう要素を示しているという時に使用
```
```haskell
  type PhoneNumber = String
  type Name = String
```
```
  - 使いすぎるとくどいので、型をドキュメントとしての質を高める時や長い型が鬱陶しい時に使う
- あくまで型の世界にしか存在しないので、値として考えることはできない

型クラスを作る

型クラスはそのデータ型が満たす性質である
- 定義されたとおりに振る舞うことができる型は、その型クラスのインスタンスである
  - ある型T がある型クラスC のインスタンスであるとは、型クラスC が定義する関数（メソッド）たちを型T に対して使えるということを意味する
  - まずデータ型を作り、そこからそのデータ型が特定の性質を満たすならその型クラスのインスタンスにする
class キーワード
- 型クラスを定義する
```
```haskell
  class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
    x == y = not (x /= y)
    x /= y = not (x == y)
```
```
  - a はEq 型クラスのインスタンスになるであろう具体的な型を表す型変数
    - 小文字で始まる必要がある
  - (==) の実装に(/=) 、(/=) の実装に(==) を用いている
    - 相互再帰である
- サブクラス
  - 型クラスのサブクラスである型クラスの作成
```
  ```haskell
      class (Eq a) => Num a where
       ...
  ```
```
    - (A a) => B a はある型（ a ）を型クラスB のインスタンスにしたい場合、それは型クラスA のインスタンスでなければならない（ => ）と読む
instance キーワード
- 型クラスを実装する
```
```haskell
  data TtafficLight = Red | Yellow | Green
  
  instance Eq TtafficLight where
    Red == Red = True
    Yellow == Yellow = True
    Green == Green = True
    _ == _ = False
```
```
  - Eq は相互再帰的な定義であるため、(==) を実装するだけで両者が実装できる
    - 最小完全定義（minimal complete definition）という
      - 型クラスの性質を満たすために最低限定義する必要のある関数を定義すれば良い
- ある型クラスのインスタンスである型を引数とする型コンストラクタから生成される型を型クラスのインスタンスにする
```
```haskell
  data MyMaybe a = MyNothing | MyJust a
  
  instance (Eq a) => Eq (MyMaybe a) where
    MyNothing == MyNothing = True
    MyJust x == MyJust y = x == y
    _ == _ = False
```
```

色んな型クラスたち

標準型クラスの自動導出
- Eq 、Ord、Enum、Bounded、Show、Read は自動導出ができる
  - 値コンストラクタのフィールド・引数に取っているすべての型がその型クラスのインスタンスである場合のみ
  - Eq
    - 等値性を判定できる
      - 値コンストラクタが同じか、同じであればフィールドの値がすべて同じかを判定
  - Ord
    - 順序を比較できる
      - 先に定義している方が小さい
  - Enum
    - 列挙できる
    - 前者関数と後者関数を持つ
  - Bounded
    - 上限と下限を持つ
  - Show
    - 文字列として表現できる
  - Read
    - 文字列から特定の型としてパースできる
Functor 型クラス
- 全体を写せる（map over）ものであることを示す型クラス
  - つまり型に属するすべての値に対して射が存在する（全射）ということ
```
class Functor f where
 fmap :: (a -> b) -> f a -> f b
```
  - a をとってb を返す関数と、a の入った箱を引数にとって、b の入った箱にして返す
  - f a やf b は型引数（a 、b ）を引数にとって具体的な型を返すようなやつ（つなまり型コンストラクタ）を要求しているということ

Haskellの型システムについて

型（type）
- 値に付いている小さなラベル
種類（kind）
- 型に付いている小さなラベル
- 型の型のようなもの
```
:k Int
Int :: *
```
- * は具体型を表す記号である
  - スターもしくは型と読む
- 値に付けられる型は具体型だけ
```
:k Maybe
Maybe :: * -> *
```
- 1つの具体型を引数にとって、具体型を返すことが分かる

第8章入出力

第9章もっと入力、もっと出力

第10章関数型問題解決法

すべてはfold だった…

第11章ファンクターからアプリカティブファンクターへ

ファンクター

Functor 型クラス
- 全体を写せる（map over）ものであることを示す型クラス
  - つまり型に属するすべての値に対して射が存在する（全射）ということ
```
class Functor f where
 fmap :: (a -> b) -> f a -> f b
```
  - a をとってb を返す関数と、a の入った箱を引数にとって、b の入った箱にして返す
  - f a やf b は型引数（a 、b ）を引数にとって具体的な型を返すようなやつ（つなまり型コンストラクタ）を要求しているということ
(->) r はFunctor である
- 関数がFunctor であるということはどういうことか
  - fmap :: (a -> b) -> f a -> f b のf を(->) r で置換するとfmap :: (a -> b) -> (r -> a) -> (r -> b) となる
    - (r -> a) の出力を(a -> b) の入力につなぐことで(r -> a -> b) となる
      - つまり(r -> b) を行う関数合成であることが分かる
ファンクターは文脈である
- Int -> Int は結果を求めるならInt 型に適用する必要があるという文脈
fmap :: (a -> b) -> (f a -> f b) と解釈した時、これは関数をとって、それと似ているがファンクター値を取るもの対して作用する関数を返すと考えることができる
- 関数の持ち上げ（Lifting）
ファンクターの考え方
- fmapは関数とファンクター値を取って、その関数でファンクター値を写して返すものである
- fmapは値から値への関数を取って、それをファンクター値からファンクター値への関数に持ち上げたものを返す関数である
  - つまり関数をファンクター値に適用できるように持ち上げてくれる（変換してくれる）

ファンクター則

ファンクターであるための規則
第一法則
- idでファンクター値を写した場合、ファンクター値が変化してはいけない
  - fmap id <ファンクター値A> は<ファンクター値A> が返る
第二法則
- 2つの関数f とg において、「f とg の合成関数でファンクター値を写したもの」と、「まずg 、次にf でファンクター値を写したもの」が等しい
ある型がファンクター則を満たすということは、適用に関する基本的な振る舞いが関数や他のファンクターと一致することが保証されるということ

アプリカティブ

多引数関数でファンクター値を写すと、関数をファンクター値を引数として部分適用したものをファンクター値としたものが返る
```
:t fmap (++) (Just "hey") :: Maybe (String -> String)
```
Applicative 型クラス
- pure と<*> を定義している
```
class (Functor f) => Applicative f where
 pure :: a -> f a
 <*> :: f (a -> b) -> f a -> f b
```
- pure
  - 任意の型の引数を受け取り、それをアプリカティブ値にして返す
- <*> （apply）
  - 関数が入っているファンクター値A と値の入っているファンクター値B を引数にとって、A の中身の関数をB の中身の値に対して適用する

アプリカティブ則

pure id <*> v = v
- 関数id をアプリカティブファンクター値のv に適用した場合、v 自体が返る
pure f <*> pure x = pure (f x)
- pure f はアプリカティブファンクター値の関数であるため、それをアプリカティブファンクター値であるpure x に適用（ <*> ）するのは、f x にpure を用いて持ち上げるのと同義である
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
- (u<func> . v<func>) w<val> がu<func> (v<func> w<val>) と同等であるということ
u <*> pure y = pure ($ y) <*> u
- y にu の関数を適用するということは、関数を引数にとってy に適用させる関数に、u の関数を渡すということ

第12章モノイド

newtype キーワード
- 1つの型を取り、それを何かにくるんで別の型に見せかける
  - 制約
    - 1つの値コンストラクタしか持てない
    - 1つのフィールドしか持てない
    - （故に）1つのアクセサしか持てない
- コンパイル時に型情報を用いるのみであり、実行時にメモリ上では元の型と同じ表現となる
- 新しい型と元の型を相互変換する関数が作られる
  - 値コンストラクタとフィールドへのアクセサが該当

モノイド

結合的な二項演算子（2引数関数）とその演算に関する単位元からなる構造
- 結合的（associativity）
  - 同じ関数を複数の同じ型に適用する際に、適用順序を変えても結果が変わらないという性質
    - (3 * 4) * 5 == 3 * (4 * 5) なので、* は結合的である
モノイド型クラスは単位元となるほか、優先順位付けにも使用できる

モノイド則

二項演算（2引数関数）である
2つの引数及び返り値の型がすべて等しい
二項演算を適用しても相手を変えないような特殊な値が存在する
二項演算が結合的である

Fordable

畳み込み可能であることを表す型クラス
単位元が存在する型にのみ実装できる（ Monoid m => ）
foldMap 関数を実装すると良い
- foldMap では実際の変換ロジックは引数として渡されるため、どこに適用して結果のモノイドをどう結合するかを決めるだけ

第13章モナドがいっぱい

モナド

計算に連結可能な文脈を持たせる
モナドの目的
- 普通の値a を取って文脈を持った値を返す関数に、文脈を持つ値m a を渡したい
  - つまり、文脈を持った値に対してなにかの処理をする場合に、その文脈を保存したい
- 例えば
  - 成功の文脈なのであれば値を取り出しそれに対して関数適用し次の文脈に包む、失敗の文脈なのであれば何もせず次の文脈での失敗値を返す、またその処理を連結しても問題無く動作する、ということをしたい
    - （Maybeの場合。他の場合は成功・失敗という文脈ではない場合もある）
モナドは>>= をサポートするアプリカティブファンクター
Monad 型クラス
```
class Applicative m => Monad m where
 return :: a -> m a

 (>>=) :: m a -> (a -> m b) -> m b

 (>>) :: m a -> m b -> m b
 x >> y = x >>= \_ -> y

 fail :: String -> m a
 fail msg = error msg
```
- Monad のインスタンスは必ずApplicative のインスタンスである必要がある
  - ~~型クラス制約が無いのは歴史的経緯（Applicativeが後から実装された）~~
    - GHC 7.10 (2015)より型クラス制約が実装
    - https://wiki.haskell.org/Functor-Applicative-Monad_Proposal
- return
  - 値を取り、この文脈において、その値を復元できる最小限の表現を返す
  - Applicative におけるpure と同じ
- >>= （bind）
  - モナディックな値を、通常の値を取り文脈付きの値を返す関数に食わせる
- >>
  - 直前のモナディックな値を無視して新しいモナディックな値を返す
  - ただし、文脈自体は引き継ぐ
    - 成功・失敗という文脈なら失敗状態を引き継ぐ
- fail
  - モナド構文において、パターンマッチに失敗してもプログラムを異常終了させず、モナドの文脈として扱えるようにするためのもの
  - 主にHaskellシステムが呼び出すため、ユーザが呼び出すことはほとんど無い
do 記法
- モナド専用構文
```
```haskell
  foo = Just 3 (\x ->
     Just "!" (\y ->
     Just (show x ++ y)
```

これを

```haskell
  foo = do
   x <- Just 3
   y <- Just "!"
   Just (show x ++ y)
```

こう書ける
```
- let 行を除いてすべてモナディックな値で構成される
- もしどこかでNothing だった場合はdo 式全体の値もNothing となる
- <- を用いてモナドの結果を調べられる
- それ以前の行に依存する値の列が、（成功または失敗などの）文脈とともに書いてあるにすぎない
リストモナド
- 非決定的な計算を行う
  - 非決定性を持つということが文脈
```
do
 n <- [1, 2]
 ch <- ['a', 'b']
 return (n, ch)
-- [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
```
  - あり得る選択肢すべてを列挙したものが、最小限の表現になる
    - 非決定的な計算の結果を引き継いでいる
- リスト内包表記はリストモナドの糖衣構文である
  - リスト内包表記などで用いる出力要素の選別は、guard 関数とMonadPlus 型クラスによって行える

MonadPlus

モノイドの性質を併せ持つモナドを表す型クラス

class Monad m => MonadPlus m where
 mzero :: m a
 mplus :: m a -> m a -> m a

guard
- 真理値を引数にとって、True なら() を成功を表す最小限の文脈に入れ、False なら失敗したモナディックな値を作る
```
guard :: (MonadPlus m) => Bool -> m ()
guard True = return ()
guard False = mzero
```
- guard 関数を用いてモナディックな値をフィルタリングできる
```
```haskell
  -- フィルタリングされない場合
  guard True >> return "cool" :: [String] -- x = [()] // 文脈を持った()
  -- ["cool"]
  
  -- フィルタリングされる場合
  guard False >> return "cool" :: [String] -- x = [] // 失敗なのでmzeroを返す
  -- []
```
```
  - >> なので成功時は左辺の結果から伝搬してきた値を無視する
- 言い換えると、引数がFalse なら直ちに失敗を投げる、True ならダミーの値() が入っている成功を作る
(->) r もモナドである
- 値がまだ手元になく、値が欲しければその関数を別のなにかに適用しないといけない、という文脈

モナド則

左恒等性
- return を用いて値をデフォルトの文脈に入れたものを、>>= を用いて関数に食わせた結果は、単にその値にその関数を適用した結果と等しくなければならない
  - return x >>= f とf x が等価である、ということ
右恒等性
- >>= を用いてモナディック値をreturn に食わせた結果は、元のモナディック値と不変である
  - (Monad m) => m a >>= return がm a である、ということ
結合法則
- >>= を用いたモナド関数適用の連結がある時、どの順序で評価しても結果が変わらない
  - (m >>= f) >>= g とm >>= (\x -> f x >>= g) が等価である、ということ

第14章もうちょっとだけモナド

Maybe モナド
- 失敗する可能性という文脈付きの値を表す
[] モナド
- 非決定性が付いた値を表す
IO モナド
- 標準入出力によって得られる値を表す
Writer モナド
- 1つの値が付加された値を表し、その値はログのように振る舞う
- 一連の計算を行っている間、すべてのログが単一のログ値にまとめて記録されることを保証する
  - ログはMonoid であり、つまりmappend によって貯めていくことができる（ロギング）、ということを表す

Reader モナド

関数に対する適用がされ値が取得されたとみなす（実際はまだされていない）ことを表す

関数が返すであろう値をすでに知っているつもりができる

addStuff = do
 a <- (*2)
 b <= (+10)
 return (a+b) -- aとbは既に適用されたと思っているが、実際はまだ引数を取っていない

addStuff 3 -- 6 + 13 = 19

こうも書ける

addStuff x = let
 a = (*2) x
 b = (+10) x
 in a + b

State モナド
- 状態付きの計算
  - 状態を引数にとって、新たな状態と一緒に計算結果を返す関数として表現できる
  - 文脈
    - 計算結果が生の値であり、その計算結果を得るためには初期状態を与える必要があること
    - 計算結果を得るのと同時に新しい状態が得られること
```
instance Monad (State s) where
 return x = \s -> (x, s)
 (State h) >>= f = State $ \s -> let (a, newState) = h s
                   (State g) = f a
                   in g newState
```
- return
  - 状態を変えずにx をそのまま結果として提示する
    - 値を取って最小限の文脈にいれるため
- >>=
  - 状態付き計算を>>= を用いて関数に食わせた結果も状態付き計算になる必要がある
    - State に渡されているラムダ式が新しい状態付き計算になる
      - 状態付き計算h を用いて、引数に取った状態s から新たな状態(a, newState) を計算する
      - 計算結果a に後続の状態付き計算f を適用し、後続の状態付き計算g を取得する
      - 取得した後続の状態付き計算g を新たな状態newState に適用し、最終結果と最終状態を得る
  - 2つの状態付き計算を糊付けすることが可能に
Either モナド
- 失敗の文脈を与え、さらにその失敗に原因を指すような値を付加できる
- Right 値であれば正解や計算の成功を、Left 値であれば失敗を表す
- モナドのインスタンスになるには* -> * である必要があるため、実質使うときはEither e とする必要がある

便利なモナディック関数

liftM
- 関数とモナド値を取って、その関数でモナド値を写す
```
`liftM :: (Monad m) => (a -> b) -> m a -> m b`
```
- fmap そのもの
join
- 入れ子になったモナド地を平らにする
```
`join :: (Monad m) => m (m a) -> m a`
```
- モナド値を>>= で関数に食わせたものと、その関数でモナド値を写し、出てきた入れ子のモナドをjoin で平らにしたものは一致する
  - >>= は常にjoin (fmap f m) であるということ
filterM
- モナディック述語を用いてリストをフィルタリングする
```
`filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]`
```

foldM

モナド版の畳み込み演算

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

モナドの作成

ある問題のある側面をモデル化した方を作り、後からその型が文脈付きの値を表現していてモナドのように振る舞うとわかった場合のみ、Monad インスタンスを与える

作ったやつ

import Data.Ratio ((%))

newtype Prob a = Prob {getProb :: [(a, Rational)]} deriving (Show)

instance Functor Prob where
  fmap :: (a -> b) -> Prob a -> Prob b
  fmap f (Prob xs) = Prob $ map (\(a, r) -> (f a, r)) xs

instance Applicative Prob where
  pure :: a -> Prob a
  pure a = Prob [(a, 1)]

  (<*>) :: Prob (a -> b) -> Prob a -> Prob b
  (<*>) (Prob fs) (Prob xs) = Prob [(f a, fr * r) | (f, fr) <- fs, (a, r) <- xs]

instance Monad Prob where
  (>>=) :: Prob a -> (a -> Prob b) -> Prob b
  (>>=) xs f = flatten $ fmap f xs

flatten :: Prob (Prob a) -> Prob a
flatten (Prob ms) = Prob [(a, or * ir) | ((Prob m), or) <- ms, (a, ir) <- m]

data Coin = Heads | Tails deriving (Show, Eq)

coin :: Prob Coin
coin = Prob [(Heads, 1 % 2), (Tails, 1 % 2)]

loadedCoin :: Prob Coin
loadedCoin = Prob [(Heads, 1 % 10), (Tails, 9 % 10)]

flipThree :: Prob Bool
flipThree = do
  a <- coin
  b <- coin
  c <- coin
  return (all (== Tails) [a, b, c])

fmap で作ったモナドのモナドをまとめるだけやないかーい
- Applicative 作るほうがむずい！

第15章 Zipper

データ構造の一部分に注目するためのやつ
- 要素の更新や探索を効率的にしてくれる
あるデータ構造の注目点、及び周辺の情報を含んでいるデータ構造
- 基本的に、データ構造を復元できる情報をすべて持つことが多い

作ったやつ

type Name = String

type Data = String

data FSItem = File Name Data | Folder Name [FSItem] deriving (Show)

data FSCrumb = FSCrumb Name [FSItem] [FSItem] deriving (Show)

type FSZipper = (FSItem, [FSCrumb])

fsUp :: FSZipper -> FSZipper
fsUp (item, (FSCrumb name front rear) : crumbs) = (Folder name (front ++ [item] ++ rear), crumbs)

fsTo :: Name -> FSZipper -> FSZipper
fsTo name (Folder folderName items, bs) =
  let (ls, item : rs) = break (nameIs name) items
   in (item, FSCrumb folderName ls rs : bs)

nameIs :: Name -> FSItem -> Bool
nameIs name (Folder folderName _) = name == folderName
nameIs name (File fileName _) = name == fileName

必要な情報は全部引数として持っとけということ
Data.Generics.Zipper モジュールにほぼあらゆる型に対してジッパーを自動実装してくれるやつがある

第1章 はじめの第一歩#

第2章 型を信じろ#

第3章 関数の構文#

第4章 Hello 再帰#

第5章 高階関数#

第6章 モジュール#

第7章 型や型クラスを自分で作ろう#

型を作る#

型クラスを作る#

色んな型クラスたち#

Haskellの型システムについて#

第8章 入出力#

第9章 もっと入力、もっと出力#

第10章 関数型問題解決法#

第11章 ファンクターからアプリカティブファンクターへ#

ファンクター#

ファンクター則#

アプリカティブ#

アプリカティブ則#

第12章 モノイド#

モノイド#

モノイド則#

Fordable#

第13章 モナドがいっぱい#

モナド#

モナド則#

第14章 もうちょっとだけモナド#

便利なモナディック関数#

モナドの作成#

第15章 Zipper#

第1章はじめの第一歩

第2章型を信じろ

第3章関数の構文

第4章 Hello 再帰

第5章高階関数

第6章モジュール

第7章型や型クラスを自分で作ろう

型を作る

型クラスを作る

色んな型クラスたち

Haskellの型システムについて

第8章入出力

第9章もっと入力、もっと出力

第10章関数型問題解決法

第11章ファンクターからアプリカティブファンクターへ

ファンクター

ファンクター則

アプリカティブ

アプリカティブ則

第12章モノイド

モノイド

モノイド則

Fordable

第13章モナドがいっぱい

モナド

モナド則

第14章もうちょっとだけモナド

便利なモナディック関数

モナドの作成

第15章 Zipper