Haskell入門。関数からモナドまで

このスライドは[Nakameguro.hs #1](https://nakameguro-hs.connpass.com/event/46742/)での発表に使用したHaskell入門のスライドです。

内容は全くの初心者から[Novice](http://qiita.com/lotz/items/0d68c8440d1f362d0c32#novice)の人が[Advanced Beginner](http://qiita.com/lotz/items/0d68c8440d1f362d0c32#advanced-beginner)になるための道筋が分かるように作ったつもりです。

説明だけでなく随所に演習も散りばめられているので手を動かしながら読んでいただけると幸いです。

----

## Haskellの開発環境

コンパイラ: GHC
パッケージマネージャ: Cabal
依存管理: Stack

Stackを導入すればGHCとCabalもついてくるのでまずはStackを入れましょう。

[Get Started](https://haskell-lang.org/get-started)

以下のaliasを設定しておくと便利です。

```bash
alias ghc='stack ghc --'
alias ghci='stack ghci --'
alias runhaskell='stack runhaskell --'
```

----

インストールしている間にこれから学んでいく概念を紹介。
[Ladder of Functional Programming](http://qiita.com/lotz/items/0d68c8440d1f362d0c32)

### NOVICE
* **概念**
    * イミュータブルなデータ
    * データの構築＆分解
    * 第一級関数＆ラムダ
    * 二階関数
    * 関数合成

----

### ADVANCED BEGINNER
* **概念**
    * 代数的データ型
    * パターンマッチ
    * 一般的な再帰
    * パラメータ多相
    * 型クラス、インスタンス、法則
    * 低次の抽象化(Equal, Semigroup, Monoid 等)
    * 参照透過性、完全性
    * 高階関数
    * 部分適用、カリー化、ポイントフリースタイル

----

## Haskell入門<br>~値と型と関数~

----

## 値と型

`1`, `2`, `3` のような数字や`"abc"`のような文字列は値であり、それらは`Int`や`String`と型付けされる。`1 + "abc"`のような意味のない式が作れないように型は利用される。

```hs
$ ghci

> -- 値 :: 型

> 1 :: Int
1

> "abc" :: String
"abc"


> 1 + "abc"

<interactive>:3:1: error:
    • No instance for (Num [Char]) arising from a use of ‘+’
    • In the expression: 1 + "abc"
      In an equation for ‘it’: it = 1 + "abc"
```

----

ghciでは`:t`をつかって値の型を調べることができる。

```hs
> :t 1
1 :: Num t => t

> :t "abc"
"abc" :: [Char]

> :t (+)
(+) :: Num a => a -> a -> a

> :t ()
() :: ()
```

`:i`を使って型の情報を調べることもできる。

```hs
> :i String
type String = [Char]    -- Defined in ‘GHC.Base’

```

----

## 真偽値

```hs
> :i Bool
data Bool = False | True
```

GHCi

```hs
> True
True

> :t True
True :: Bool

> not True
False

> :t not
not :: Bool -> Bool
```

----

```hs
> 1 < 2
True

> True && False
False

> 1 < 2 && 2 < 3
True

> True || False
True

> if True then 1 else 2
1
```

`if`は必ず`then`, `else`との組で使用しどちらも省略することは出来ない。`if`と`then`の間には`Bool`型の式を、`then`と`else`の後には同じ型を持つ式を書く必要がある。以下はダメな例

```hs
> if True then 1

<interactive>:21:15: error:
    parse error (possibly incorrect indentation or mismatched brackets)

> if False then 1 else "abc"

<interactive>:22:15: error:
    • No instance for (Num [Char]) arising from the literal ‘1’
    • In the expression: 1
      In the expression: if False then 1 else "abc"
      In an equation for ‘it’: it = if False then 1 else "abc"
```

----

## 数値型

|型|説明|
|:----|:----|
|`Int`|整数|
|`Integer`|多倍長整数|
|`Word`|符号なし整数|
|`Float`|浮動小数点|
|`Double`|倍精度浮動小数点|
|`Ratio`|有理数|
|`Complex`|複素数|

全て`Num`のインスタンス（型クラスに関しては後述）

----

## 数値型(GHCi)

```haskell
> 1 :: Int
1

> 1 :: Integer
1

> (1 :: Int) + (1 :: Int)
2

> -- (+) :: Num t => t -> t -> t
> -- であるので2つの引き数の型は同じでなければならない
> (1 :: Int) + (1 :: Double)
<interactive> error:
  • Couldn't match expected type ‘Int’ with actual type ‘Double’

> 1 + 1
2
```

----

```hs
> -- 小数の例
> 0.2 / 0.3
0.6666666666666667

> -- 有理数の例
> import Data.Ratio

> -- モジュールをインポートする時はこのように
> -- import モジュール名
> -- とする

> 1%2
1 % 2

> 1%2 + 1%3
5 % 6

> -- 複素数の例
> import Data.Complex

> 1 :+ 2
1 :+ 2

> (1 :+ 2) * (1 :+ 3)
(-5.0) :+ 5.0
```

----

基本的な関数

```hs
> -- 加減乗除
> 1 + 1
2
> 2 - 1
1
> 2 * 3
6
> 4 / 2
2.0

> quot 4 2
2
> mod 5 3
2

> floor 1.3
1
> ceiling 1.3
2
> round 1.3
1
```

----

## 文字と文字列

|型|説明|
|:----|:----|
|`Char`|文字|
|`String`|文字列|

文字列の型`String`は文字の型`Char`のリストの型`[Char]`のエイリアスでしかない。

```hs
> :i String
type String = [Char]
```

----

## 文字と文字列(GHCi)

```hs
> -- 文字は ' で囲む
> 'a' :: Char

> -- 文字列は " で囲む
> "文字列" :: String

> -- 文字列の結合
> "abc" ++ "def"
"abcdef"

> -- 文字列の長さを求める
> length "abcdef"
6

-- 先頭の文字を取得する
> head "abcdef"
'a'

> -- 先頭3文字とってくる
> take 3 "abcdef"
"abc"

> -- 先頭2文字以降を取得する
> drop 2 "abcdef"
"cdef"

> -- 2文字目から4文字目を取得する
> ??? "abcdef"
"bcde"

> -- 3文字目を取得する
> ??? "abcdef"
'c'

> -- n文字目を取得する演算子
> "abcdef" !! 4
'e'
```

実はこれらの関数は全てリストに対して定義された関数！

----

```hs
> -- リストの長さを求める
> length [1,2,3,4,5,6]
6

-- 先頭の要素を取得する
> head [1,2,3,4,5,6]
1

> -- 先頭3要素とってくる
> take 3 [1,2,3,4,5,6]
[1,2,3]

> -- 先頭２要素以降を取得する
> drop 2 [1,2,3,4,5,6]
[3,4,5,6]

> -- 2つ目から4つ目を取得する
> take 4 (drop 1 [1,2,3,4,5,6])
[2,3,4,5]

> -- 3つ目を取得する
> head (drop 2 [1,2,3,4,5,6])
3

> -- nつ目を取得する演算子
> [1,2,3,4,5,6] !! 4
5
```

----

## 文字列に関する関数

```hs
> :t show
show :: Show a => a -> String

> show 1
"1"

> show True
"True"

> :t words
words :: String -> [String]

> words "this is a pen"
["this","is","a","pen"]

> :t unwords
unwords :: [String] -> String

> unwords ["this","is","a","pen"]
"this is a pen"

> :t lines
lines :: String -> [String]

> lines "aaa\nbbb"
["aaa","bbb"]

> :t unlines
unlines :: [String] -> String

> unlines ["aaa", "bbb"]
"aaa\nbbb\n"
```

----

## リスト

```hs
> :i []
data [] a = [] | a : [a]
        ^
        '-- 型引数
```

リストは`[]`だけでは型ではなく別の型を与えて初めて型になる。
ex) `[Int]`, `[Char]`, `[String]`, `[[Int]]`

この様に別の型を引数にとって型になる型を高階型という。

----

## いろいろな高階型

|型          |説明|
|:-----------|:----|
|`Maybe a`   |存在しないかもしれない値を表す型|
|`[a]`       |リスト|
|`(a, b)`    |タプル|
|`Either a b`|`a`もしくは`b`を表す型|
|`a -> b`    |`a`の値を取って`b`の値を返す関数の型|
|`IO a`      |副作用を伴って`a`の値を返す型|

----

## Maybe

```hs
> :i Maybe
data Maybe a = Nothing | Just a
```

存在しないかもしれない値を表す型

```hs
> import Data.List

> :t find
find :: (a -> Bool) -> [a] -> Maybe a

> find odd [2,4,6,8]
Nothing

> find odd [2,4,6,9]
Just 9
```

----

## リスト(再び)


```hs
> :i []
data [] a = [] | a : [a]
```

リストの便利な記法

```hs
> [1..10]
[1,2,3,4,5,6,7,8,9,10]

> [1,3..20]
[1,3,5,7,9,11,13,15,17,19]

> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13...

> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"

> -- リストの内包表記
> [x | x <- [1..10]]
[1,2,3,4,5,6,7,8,9,10]

> [(x, y) | x <- [1,2], y <- ['a', 'b']]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

> [(x, y, z) | z <- [1..100], y <- [1..z], x <- [1..y], x^2 + y^2 == z^2]
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),...
```

----

## タプル

```hs
> :i (,)
data (,) a b = (,) a b
```

２つの値の組を表す型

```hs
> (1,2)
(1,2)

> -- 型が違っても大丈夫
> (1, "abc")
(1,"abc")

> :t fst
fst :: (a, b) -> a

> fst (1, "abc")
1

> :t snd
snd :: (a, b) -> b

> snd (1, "abc")
"abc"
```

3つ組`(a,b,c)`や４つ組`(a,b,c,d)`やそれ以上のタプルも存在する。

----

## Either

```hs
> :i Either
data Either a b = Left a | Right b
```

二つのうちどちらか一方を表す型。`Either String Int`と型付けられた値は`String`であるか`Int`であるかのどちらかである。


```hs
> -- 以下はどちらも同じ型

> Left "abc" :: Either String Int
Left "abc"

> Right 123 :: Either String Int
Right 123
```

`Either`は例外を扱いたい時に便利

```hs
> if 2 < 1 then Left "2は1より小さくないよ" else Right 100
Right 100
```

----

## 関数

```hs
> :i (->)
data (->) t1 t2
```

`a -> b`は`a`の値から`b`の値への対応付けの型。つまり関数。
`\`と`->`を使ったラムダ記法という関数のリテラルが存在する。

```hs
> :t (\x -> not x)
(\x -> not x) :: Bool -> Bool

> (\x -> not x) True
False
```

Haskellの関数は何か特別なものではなく関数の型の付いた値でしかない。

----
## 関数と演算子
Haskellの関数には前置記法と中置記法がある

```hs
> -- 前置記法
> elem 1 [1,2,3]
True

> -- 中置記法
> 1 + 3
4
```

英字で定義されている関数は前置記法で、記号で定義されている関数（演算子）は中置記法で書かれる。バックチックや丸括弧を用いてこれらを入れ替えることもできる。

```hs
> 1 `elem` [1,2,3]
True

> (+) 1 3
4
```

----

また演算子に関してはセクションと呼ばれる部分適用の書き方が存在する

```hs
> (3 +) 2
5

> (+ 2) 3
5
```

例えばこんなことができる

```hs
> :t map
map :: (a -> b) -> [a] -> [b]

> map (+1) [1,2,3,4,5]

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

> filter (3 <) [1,2,3,4,5]
[4,5]
```

----

## 高階関数
関数は値として扱えるので関数の返り値として関数を返すこともできる。
`map`の型は

```hs
> :t map
map :: (a -> b) -> [a] -> [b]
```

であったが`->`は右結合なのでこれは


```hs
> :t map
map :: (a -> b) -> ([a] -> [b])
```

と解釈することができる。すなわち`map`は関数を取って関数を返す関数である。このような関数を二階関数と呼ぶ。二階関数を返す関数を三階関数と呼び、より一般に関数を返す関数を**高階関数**と呼ぶ。

----

## 多変数関数
２変数関数を考えてみると以下の様な型になる

```hs
f :: (a, b) -> c
```

実はこの型は以下のような関数の型と**同型**である

```hs
g :: a -> b -> c
```

これは１変数の２階関数である。この様に２変数関数を１変数の２階関数に書き換えることをカリー化と呼ぶ。
同型であるとは互いに変換する関数が存在するということ。Haskellには上記の`f`と`g`を同型たらしめる関数`curry`, `uncurry`があらかじめ定義されている。

```hs
> :t curry
curry :: ((a, b) -> c) -> a -> b -> c

> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c

> :t take
take :: Int -> [a] -> [a]

> :t uncurry take
uncurry take :: (Int, [a]) -> [a]
```

一般に多変数関数は高階関数に変換することができる。またHaskellにおける関数は全て１変数関数である。

----

## ファイルにHaskellのプログラムを書いてみる

```bash
$ vim Main.hs
```

Haskellのプログラムの拡張子は`.hs`

```hs:Main.hs
-- ↓ 関数の定義
add10 :: Int -> Int
add10 x = x + 10

-- ↓ 実行する関数
main :: IO ()
main = do
  print (add10 5)
```

関数の定義は型の宣言と処理の実装に分けられる。
型の宣言は必須ではないがトップレベルで関数を定義する時は必ず宣言するようにするのが良い。
`main = do`と書いたあとはインデントを下げて処理を書いていくのに注意。

```bash
$ runhaskell Main.hs
15
```

----

## イミュータブル

Haskell の `=` は**代入ではない**

```hs
x = 1
```

一度`x`に`1`を **束縛する** と `x` は常に `1` を表す。
以下のようなプログラムはコンパイル時にエラーになる。
（実際に試してみて下さい）

```hs
x :: Int
x = 1
x = 2

main :: IO ()
main = do
  print x
```

```bash
$ runhaskell Main.hs
Main.hs:3:1: error:
    Multiple declarations of ‘x’
    Declared at: Main.hs:2:1
                 Main.hs:3:1
```

Haskellの変数は変更できないという意味で **イミュータブル** である。

----

## 関数の定義とラムダ
関数のリテラルとしてラムダ記法があった。これを使えば

```hs
f :: Int -> Int
f = \x -> x + 1
```

この様に`f`という変数に直接関数を束縛することができる。実は

```hs
f :: Int -> Int
f x = x + 1
```

という書き方はラムダ記法による定義の糖衣構文になっている。これを繰り返し用いれば

```hs
f = \x -> y -> x + y
```

```hs
f x = \y -> x + y
```

```hs
f x y = x + y
```

となるようにより高階な関数も糖衣構文を使って宣言できるようになる。

----

## パターンマッチ

`case`..`of`を使って値の構造を調べることができる。

```hs
isOneTwoThree :: String -> Bool
isOneTwoThree x = case x of
                      "one" -> True
                      "two" -> True
                      "three" -> True
                      _ -> False

isJust :: Maybe a -> Bool
isJust x = case x of
               Nothing -> False
               Just y  -> True
```

糖衣構文を使って以下のように書くこともできる

```hs
isOneTwoThree :: String -> Bool
isOneTwoThree "one" = True
isOneTwoThree "two" = True
isOneTwoThree "three" = True
isOneTwoThree _ = False

isJust :: Maybe a -> Bool
isJust Nothing = False
isJust (Just y) = True
```

----

## 例題

半径の値を受け取って円の面積を返すような関数を実装して実行してみて下さい。

```hs
> calcArea 2
12.566370614359172

> :t calcArea
calcArea :: Double -> Double

> -- 円周率は事前に定義されています
> pi
3.141592653589793
```

----

## 演算子の定義

演算子も関数と同じように定義できる。

```hs
(&) :: a -> (a -> b) -> b
(&) a f = f a
```

演算子の定義に使える文字はたくさんある。
<img width="492" alt="スクリーンショット 2017-01-13 23.25.15.png" src="https://qiita-image-store.s3.amazonaws.com/0/17134/cb2eba12-8b1f-f1d6-26ef-4277e9ecba7c.png">

[Haskell 2010 Language Report - Chapter 2 Lexical Structure](https://www.haskell.org/onlinereport/haskell2010/haskellch2.html)

```
(≧∀≦*) :: String
(≧∀≦*) = "すごいHaskellたのしく学ぼう!"
```

演算子の結合性と優先順位を定義することもできる

```hs
-- 左結合で優先順位は1
infixl 1 &
```

[Haskell 2010 Language Report - Precedences and fixities of prelude operators](https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-820061)

ちなみに関数適用は優先順位が最も高い

```hs
> floor 1.2 + ceiling 1.5
3
```

----

`$`は右結合で優先順位が最も低いので括弧の代わりになる

```hs
> sum $ take 10 $ map (+1) [1,2,3,4,5]
20
```

関数合成の演算子`(.)`

```hs
> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
```

例えば

```hs
> :t sum
sum :: Num a => [a] -> a

> :t take 10
take 10 :: [a] -> [a]

> :t map (+1)
map (+1) :: Num b => [b] -> [b]

> :t sum . take 10 . map (+1)
sum . take 10 . map (+1) :: Num c => [c] -> c
```

----

## ここまでくれば<br />Noviceレベル!

----

## 休憩

----

## Advanced Beginner<br>~Haskellの基本~

----

## 再帰

関数定義の中で自分自身を呼び出す。
例えば階乗を計算する関数を再帰的に定義してみる。

```hs
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)
```

```hs
factorial 3
= 3 * factorial 2
= 3 * (2 * factorial 1)
= 3 * (2 * (1 * factorial 0))
= 3 * (2 * (1 * 1))
= 6
```

次に与えられたリストの中身を全て掛け合わせる関数を再帰的に定義してみる。

```hs
prod :: [Int] -> Int
prod [] = 1
prod (x:xs) = x * prod xs
```

```hs
prod [1,2,3]
= 1 * prod [2, 3]
= 1 * (2 * prod [3])
= 1 * (2 * (3 * prod []))
= 1 * (2 * (3 * 1))
= 6
```

フィボナッチ数列のn項目の値を返す関数を実装してみて下さい。

1, 1, 2, 3, 5, 8, 13...

----

## 演習

[H-99: Ninety-Nine Haskell Problems](https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems)より

以下のような関数を実装してみて下さい

**Probrem1**

```hs
> myLast [1,2,3,4]
4
> myLast ['x','y','z']
'z'
```

**Probrem2**

```hs
> myButLast [1,2,3,4]
3
> myButLast ['a'..'z']
'y'
```

**Problem3**

```hs
> elementAt [1,2,3] 2
2
> elementAt "haskell" 5
'e'
```

**Problem4**

```hs
> myLength [123, 456, 789]
3
> myLength "Hello, world!"
13
```

**Problem5**

```hs
> myReverse "A man, a plan, a canal, panama!"
"!amanap ,lanac a ,nalp a ,nam A"
> myReverse [1,2,3,4]
[4,3,2,1]
```

----

## 代数的データ型

独自の型を定義してみる。基本は

```
data 型名 = 値1 | 値2 | ...
```

例えば

```hs
data Signal = Green | Yellow | Red

cango :: Signal -> Bool
cango Green = True
cango Yellow = False
cango Red = False
```

各値には既存の型の値を持たせることもできる

```hs
> data Value = VInt Int | VStr String | VEith Int String

> :t VInt 5
VInt 5 :: Value

> :t VEith 1 "abc"
VEith 1 "abc" :: Value
```

----

## レコード

```hs
data Person = Person { name :: String
                     , age :: Int
                     }
```

これは

```hs
data Person = Person String Int

name :: Person -> String
name (Person x _) = x

age :: Person -> Int
age (Person _ y) = y
```

を一度に定義してるのと同じ。

**例題**
`Person`のリストから２０才以上の値だけ取り出す関数を実装してみて下さい

```hs
> :t adults
adults :: [Person] -> [Person]

> map name $ adults [Person "alice" 18, Person "bob" 20]
["bob"]
```

----

## 型クラス `Show`

自分で定義した方をghciで表示するためには`Show`という型クラスのインスタンスにする必要がある。

```hs
data Signal = Green | Yellow | Red

instance Show Signal where
    show Green = "Green"
    show Yellow = "Yellow"
    show Red = "Red"
```

`show :: Signal -> String` を実装すれば良い。

```hs
instance Show Person where
    show (Person x y) = "{ name =" ++ x ++ ", age =" ++ show y ++ " }"
```

```hs
> Person "alice" 18
{ name = alice, age = 18 }
```

----

## 再帰的な型

自分でリストを定義してみる

```hs
data List a = Null | Cons a (List a)

instance Show a => Show (List a) where
    show Null = "Null"
    show (Cons x xs) = "Cons " ++ show x ++ " " ++ show xs
```

```hs
> Cons 1 (Cons 2 (Cons 3 Null))
Cons 1 Cons 2 Cons 3 Null
```

**例題**

`List`に対して`myLast`と`elementAt`を実装してみて下さい

```hs
> myLast (Cons 1 (Cons 2 (Cons 3 Null)))
3

> elementAt (Cons 1 (Cons 2 (Cons 3 Null))) 2
2
```

----

## 再帰的な型2

```hs
data Tree a = Leaf a | Branch (Tree a) (Tree a)
```

**例題**

1. `Tree`に対して`Show`のインスタンスを定義してみて下さい。
2. 以下のような`Leaf`を数える関数`myLength`を実装してみて下さい

```hs
> myLength (Branch (Leaf 1) (Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4)))
4
```

3. 以下のような最大の深さを数える関数`depth`を実装してみて下さい

```hs
> depth (Branch (Leaf 1) (Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4)))
3
```

----

## 多相性
Haskellには多相性を実現する二種類の方法がある

* パラメータ多相
* アドホック多相

**パラメータ多相**
型変数を含んだまま関数を定義する。例えばリストの長さを返す関数 `length` はリスト中身の方を知らなくても実装することができる。

```hs
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
```

`length`は`a`をどのような型に置き換えても同じ振る舞いをする。このような多相性をパラメータ多相と呼ぶ。

**アドホック多相**
引き数の型によって振る舞いが変わるような関数を定義する。

----

## 型クラス

アドホック多相を実現する仕組み。

```hs
class  Eq a  where
  (==) :: a -> a -> Bool
  x == y = not (x /= y)

  (/=) :: a -> a -> Bool
  x /= y = not (x == y)

instance Eq Bool where
  True  == True  = True
  False == False = True
  _     == _     = False
```

`Eq`のインスタンスを型ごとに定義することで`(==)`の振る舞いを型ごとに実装することができる。

```hs
elem :: Eq a => a -> [a] -> Bool
```

`elem`は`Eq`のインスタンスであるような型`a`に対して実装されている。

**例題**

```hs
data Person = Person { name :: String
                     , age :: Int
                     }
```

`Person`は`name`と`age`が等しければ同じとみなすとし`Eq`のインスタンスを定義してみて下さい。
また以下の式が実行できることを確かめて下さい。

```hs
> import Data.List

> elem (Person "alice" 18) [Person "bob" 20, Person "alice" 18]
True
```

----

## 型クラスの例

|型クラス|型クラスが表す性質|
|:----|:----|
|`Eq`|等しいかどうかを判定できる|
|`Ord`|順序を定義できる|
|`Bounded`|最大値と最小値を持つ|
|`Show`|文字列に変換できる|
|`Read`|文字列から変換できる|
|`Num`|数値のように扱える|

----

## Eq

等しいかどうかを判定できる性質を表す型クラス

```hs
> :i Eq
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  {-# MINIMAL (==) | (/=) #-}
```

**例題**

```hs
data List a = Null | Cons a (List a)
```

に対してすべての要素が等しい時に等しいリストとみなす、というような`Eq`のインスタンスを定義して下さい。

```hs
instance Eq a => Eq (List a) where
    ...
```

```hs
> Cons 1 (Cons 2 Null) == Cons 1 (Cons 2 Null)
True

> Cons 1 (Cons 2 Null) == Cons 1 (Cons 2 (Cons 4 Null))
False
```

----

## Ord

順序を定義できる性質を表す型クラス

```hs
> :i Ord
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  (>) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  max :: a -> a -> a
  min :: a -> a -> a
  {-# MINIMAL compare | (<=) #-}
```

**例題**

```hs
data Signal = Green | Yellow | Red
```

に対して `Green < Yellow < Red` となるような`Ord`のインスタンスを定義してみて下さい

----

## Bounded

最大値と最小値を持つという性質を表す型クラス

```hs
> :i Bounded
class Bounded a where
  minBound :: a
  maxBound :: a
  {-# MINIMAL minBound, maxBound #-}
```

```hs
> maxBound :: Int
9223372036854775807

> minBound :: Int
-9223372036854775808

> maxBound :: Word
18446744073709551615

> minBound :: Char
'\NUL'

> minBound :: Bool
False
```

例

```hs
instance Bounded Signal where
    maxBound = Red
    minBound = Green
```

----

## Show
文字列に変換できるという性質を表す型クラス

```hs
> :i Show
class Show a where
  showsPrec :: Int -> a -> ShowS
  show :: a -> String
  showList :: [a] -> ShowS
  {-# MINIMAL showsPrec | show #-}
```

```hs
> show 123
"123"

> show [1,2,3]
"[1,2,3]"

> show (Just "abc")
"Just \"abc\""
```

----

## Read

文字列から変換できるという性質を表す型クラス

```hs
> :i Read
class Read a where
  readsPrec :: Int -> ReadS a
  readList :: ReadS [a]
  {-# MINIMAL readsPrec | readPrec #-}

> :t read
read :: Read a => String -> a
```

```hs
> read "1234" :: Int
1234

> read "1234" :: Char
*** Exception: Prelude.read: no parse

> read "Just 123" :: Maybe Int
Just 123

> read "[1,2,3,4]" :: [Int]
[1,2,3,4]

> read "123"
*** Exception: Prelude.read: no parse
```

----

## Num

数値のように扱える性質を表す型クラス

```hs
> :i Num
class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
  {-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}

instance Num Word 
instance Num Integer
instance Num Int
instance Num Float
instance Num Double
```

----

## deriving

型クラスの定義は面倒くさい？コンパイラに自動で定義させよう！

```hs
data Signal = Green | Yellow | Red deriving (Eq, Ord, Bounded)
```

```hs
> data Signal = Green | Yellow | Red deriving (Eq, Ord, Bounded, Show)

> Green == Yellow
False

> Green < Red
True

> maxBound :: Signal
Red
```

**例題**

`List`に対しても`Eq`と`Show`のインスタンスが期待通りに導出されることを確かめてみましょう。

----

## 休憩2

休憩前に以下ののコマンドを実行しておいて下さい

```bash
$ stack install gloss http-conduit
```

----

## IO入門<br>~副作用の扱い方~
----

## 参照等価性

> ある式が参照透過であるとは、その式をその式の値に置き換えてもプログラムの振る舞いが変わらないことを言う。

[wiki - 参照等価性](https://ja.wikipedia.org/wiki/参照透過性)

例えば`1 + 1`は勝手に`2`に置き換えても式の意味は変わらない。Haskellではどれだけ複雑な関数になってもこの性質が保たれる※。

逆に参照等価性を満たさない例

```js
var count = 0;

function addCount(i) {
  count += i;
  return count;
}

console.log(addCount(1))
console.log(addCount(1))
console.log(addCount(1))
```

`addCount(1)`の値は評価するたびに変わってしまう。Haskellではこのようなことは起こらない。つまり **参照等価性を満たす関数は引き数が同じであれば常に同じ値を返す**。

----

## 副作用を起こす関数？
標準入力から値を受け取る関数は評価されるたびに値が変わるので参照等価性を満たさないのではないか？

```hs
main :: IO ()
main = do
  putStrLn "あなたの名前は何ですか？"
  name <- getLine
  putStrLn ("こんにちは" ++ name ++ "さん！")
```

```hs
-- 標準出力に文字列を出力する関数
putStrLn :: String -> IO ()

-- 標準入力から文字列を受け取る関数
getLine :: IO String
```

Haskellでは副作用を起こす処理を`IO`という型に包むことで参照等価性が破られないようにしている。詳しい話は難しいので割愛。

----

## IOプログラミング

`main = do`と書いた下に行いたい処理を順番に書いていく。

```hs
main :: IO ()
main = do
    -- アクション1
    -- アクション2
    -- 結果 <- アクション3
    -- アクション4
    -- ...
```

アクションの例

```hs
type FilePath = String

-- FilePathにあるファイルの中身をStringとして返す
readFile :: FilePath -> IO String

-- FilePathにあるファイルの中にStringの値を書き込む
writeFile :: FilePath -> String -> IO ()
```

**例題**
テキストファイルを読み込んで各行の文字数を出力するプログラムを書いてみて下さい。

----

## gloss

```hs
import Graphics.Gloss

main :: IO ()
main = do
    display (InWindow "Hello gloss." (640, 480) (100, 200)) orange Blank
```

```bash
$ runhaskell Main.hs
```

<img width="150" alt="スクリーンショット 2017-01-14 3.12.08.png" src="https://qiita-image-store.s3.amazonaws.com/0/17134/2679edb3-f708-8dbb-2207-9a9e65ee17d5.png">

Haddock を読んでみましょう: [gloss](https://www.stackage.org/lts-7.15/package/gloss-1.10.2.5)


----

## Haskellの文字列事情

`String`はただの`Char`型のリストなのでメモリ的にも時間的にも効率が悪い。効率の良い文字列を表す型として`ByteString`と`Text`が存在する。

* `ByteString` - 文字列をバイト列として扱う型
* `Text` - ユニコード文字列を表す型

通常文字列リテラル`"abc"`は`String`と型付けされるが、ファイルの先頭に

```hs
{-# LANGUAGE OverloadedStrings #-}
```

書くと`ByteString`や`Text`としても扱うことができるようになる。

```hs
{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString.Char8 as BS

main :: IO ()
main = do
  BS.putStrLn "This is bytestring."
```

実は`IsString`のインスタンスになっている型なら文字列リテラルで表すことができる。

----

## http-conduit

```hs
{-# LANGUAGE OverloadedStrings #-}
import Network.HTTP.Simple
import qualified Data.ByteString.Lazy.Char8 as BS

main :: IO ()
main = do
  response <- httpLBS "http://example.com"
  BS.putStrLn (getResponseBody response)
```

```bash
$ runhaskell Main.hs
<!doctype html>
<html>
<head>
    <title>Example Domain</title>
```

[http-conduit](https://www.stackage.org/lts-7.15/package/http-conduit-2.1.11)

----

## 高次の抽象化

----

## Functor

リストのmapの性質を型クラスを使って一般化する

```hs
map :: (a -> b) -> [a] -> [b]
```

`a -> b`という関数を`a`が別の型に包まれていても適用できるようにする

```hs
class Functor f where
  fmap :: (a -> b) -> f a -> f b

instance Functor [] where
  fmap = map
```

Functorとは`a -> b`を`f a -> f b`という関数に対応付けることができるような性質を表す型クラス。

----

## Functorのインスタンスたち

`Maybe`

```hs
instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just a) = Just (f a)
```

```hs
> fmap (+1) Nothing
Nothing

> fmap (+1) (Just 1)
Just 2

> fmap show (Just 123)
Just "123"
```

`((,) a)`

```hs
instance Functor ((,) a) where
    fmap f (a, b) = (a, f b)
```

```hs
> fmap (+1) ("a", 1)
("a",2)

> fmap show ("b", 123)
("b","123")
```

`((->) r)`

```hs
instance Functor ((->) r) where  
    fmap f g = f . g
```

```hs
> :t fmap (+1) (+2)
fmap (+1) (+2) :: Num b => b -> b
```

----

## Applicative

関数適用の関数

```hs
($) :: (a -> b) -> a -> b
```

Functor の fmap

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

Applicativeは関数と値がその型に包まれていても関数適用ができるような性質を表す

```hs
class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
```

----

## Applicativeのインスタンスたち

`Maybe`

```hs
instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> k = fmap f k
```

```hs
> Just (*2) <*> Just 123
Just 246

> Nothing <*> Just 123
Nothing

> Just (*2) <*> Nothing
Nothing

> take <$> Just 3 <*> Just [1,2,3,4,5]
Just [1,2,3]
```

`[]`

```hs
instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
```

```hs
> [(+1), (*2)] <*> [1,2,3]
[2,3,4,2,4,6]
```

`((->) r)`

```hs
instance Applicative ((->) r) where
    pure = const
    f <*> k = \r -> (f r) (k r)
```

```hs
> :t take
take :: Int -> [a] -> [a]

> (take <*> (\i -> map (^i) [1..])) 1
[1]

> (take <*> (\i -> map (^i) [1..])) 2
[1,4]

> (take <*> (\i -> map (^i) [1..])) 3
[1,8,27]

> (take <*> (\i -> map (^i) [1..])) 4
[1,16,81,256]
```

----

## Monad

```hs
($)   :: (a -> b) -> a -> b

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

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

???   :: (a -> f b) -> f a -> f b
```

Functor であれば `fa :: f a` と `k :: a -> f b` がある時

```hs
> :t fmap k fa
fmap k fa :: f (f b)
```

が作れる。しかし欲しかったのは`f b`。

Monad はその型で二重に包まれている時に一重に潰すことができるような性質を表す

```hs
class Applicative m => Monad m where
    join :: m (m a) -> m a
```

この時

```hs
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>=) fa k = join (fmap k fa) 
```

とすると、これが欲しかった`???`である。
逆に`(>>=)`を使って

```hs
join :: Monad m => m (m a) -> m a
join = (>>= id)
```

と定義することもできる。
実はHaskellではMonadは`(>>=)`を使って定義されている

```hs
class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
```

モナドはただの型クラスでした。

----

実は`(>>=)`と`pure`があれば`fmap`が作れる

```hs
> :t pure
pure :: Applicative f => a -> f a

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

> :t flip
flip :: (a -> b -> c) -> b -> a -> c

> :t flip (>>=)
flip (>>=) :: Monad m => (a -> m b) -> m a -> m b

> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

> :t (pure .)
(pure .) :: Applicative f => (a -> a1) -> a -> f a1

> :t flip (>>=) . (pure .)
flip (>>=) . (pure .) :: Monad m => (a -> b) -> m a -> m b
```

`fmap`と`(>>=)`があれば`(<*>)`が作れる

```hs
> :t ($)
($) :: (a -> b) -> a -> b

> :t flip ($)
flip ($) :: a -> (a -> c) -> c

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

> :t fmap . flip ($)
fmap . flip ($) :: Functor f => a -> f (a -> b) -> f b

> :t flip (fmap . flip ($))
flip (fmap . flip ($)) :: Functor f => f (a -> b) -> a -> f b

> :t flip (>>=)
flip (>>=) :: Monad m => (a -> m b) -> m a -> m b

> :t flip (>>=) . flip (fmap . (flip ($)))
flip (>>=) . flip (fmap . (flip ($)))
  :: Monad m => m (a -> b) -> m a -> m b
```

**例題**
`(<*>)`と`pure`を使って`fmap`を作ってみて下さい

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

> :t pure
pure :: Applicative f => a -> f a

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

----

## 則

実はFunctor, Applicative, Monadは好き勝手に実装する事はできず、以下の則を満たしていることが要請されている。

**Functor則**

```hs
fmap id == id

fmap f . fmap g = fmap (f . g)
```

**Applicative則**

```hs
pure id <*> v = v
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u
```

**Monad則**

```hs
pure x >>= f == f x
m >>= pure == m
(m >>= f) >>= g == m >>= (\x -> f x >>= g)
```

しかし、これら要請はコンパイラによって検知できるわけではないのでベストエフォートでしかない

----

## Monadのインスタンスたち

`Maybe`

```hs
instance Monad Maybe where
    Nothing >>= _ = Nothing
    _ >>= Nothing = Nothing
    (Just f) >>= k = fmap f k
```

```hs
> :t elemIndex
elemIndex :: Eq a => a -> [a] -> Maybe Int

> Just 'a' >>= (\x -> elemIndex x "I have a pen")
Just 3
```

`[]`

```hs
instance Monad [] where
    xs >>= ks = concat [k x | k <- ks, x <- xs]
```

```hs
> import Data.Char

> :t \c -> [toUpper c, toLower c]
\c -> [toUpper c, toLower c] :: Char -> [Char]

> "abc" >>= (\c -> [toUpper c, toLower c])
"AaBbCc"
```

----

## do構文

`(>>=)`は合成していくとすぐにぐちゃぐちゃになる

```hs
> elemIndex 2 [1,2,3] >>= (\x -> elemIndex 3 [3,4,5] >>= (\y -> if y == 0 then Just (-1) else Just (x + y)))
Just (-1)
```

実は`do`は`(>>=)`を使った合成の糖衣構文になっている。
上記の例はdo構文を使うと

```hs
do
  x <- elemIndex 2 [1,2,3]
  y <- elemIndex 3 [3,4,5]
  if y == 0 then Just (-1) else Just (x + y)
```

のように書ける。
糖衣構文を剥がすと

```hs
  elemIndex 2 [1,2,3] >>= \x ->
  elemIndex 3 [3,4,5] >>= \y ->
  if y == 0 then Just (-1) else Just (x + y)
```

となる。これを一行で書けば

```hs
elemIndex 2 [1,2,3] >>= (\x -> elemIndex 3 [3,4,5] >>= (\y -> if y == 0 then Just (-1) else Just (x + y)))
```

となり元の式と一致する

----

## あらためてmain関数

```hs
main :: IO ()
main = do
  putStrLn "あなたの名前は何ですか？"
  name <- getLine
  putStrLn ("こんにちは" ++ name ++ "さん！")
```

`IO`は実はモナドなのでdo構文が使われている。
糖衣構文を剥がすと

```hs
main :: IO ()
main =
  putStrLn "あなたの名前は何ですか？" >>= \_ ->
  getLine >>= \name ->
  putStrLn ("こんにちは" ++ name ++ "さん！")
```

つまり

```hs
main :: IO ()
main = putStrLn "あなたの名前は何ですか？" >>= (\_ -> getLine >>= (\name -> putStrLn ("こんにちは" ++ name ++ "さん！")))
```

`putStrLn`と`getLine`の型が

```hs
putStrLn :: String -> IO ()
getLine :: IO String
```

であったことを思い出すと、結果は確かに`IO ()`となっており`main`関数もただのHaskellの関数であったことがわかる。

----

## おわり