MonadFixを試す


ghc 8.0から `Alt`、`Dual`、`First`、`Last`、`Product`、`Sum`が`MonadFix`のインスタンスになったそうです。

https://github.com/ghc/ghc/blob/ghc-8.0/libraries/base/changelog.md#new-instances

---

# MonadFixって何

`fix`のモナド版である`mfix`メソッドを持つ型クラス

```
> :i MonadFix
class Monad m => MonadFix (m :: * -> *) where
  mfix :: (a -> m a) -> m a
  {-# MINIMAL mfix #-}
        -- Defined in ‘Control.Monad.Fix’
```

---

## なにが嬉しいのか?

* do式で`rec`というキーワードが使えるようになる。
* 再帰束縛という機能
* 登場する前の名前を利用できる(再帰することになる)

---

### do式がパワーアップする

(まだまだ強くなりそうな画像を置く)

---


## つかってみる

簡単な実用性のない使い方

```haskell
{-# LANGUAGE RecursiveDo #-}
import Data.Monoid
import Control.Monad.Fix

ones :: MonadFix m => m [Int]
ones = do
 rec xs <- return (1:xs)  -- xsを束縛する前にxsという名前が利用できる
 return xs                -- コンパイルするためにかいてるだけ
```

---

### 利用例

```haskell
ones :: Maybe [Int] -- Just [1,1,1,1, と1がずっと続く
ones :: Sum [Int] -- Sum { getSum = [1,1,1, と1がずっと続く
fmap (take 5) (ones :: Maybe [Int]) -- Just [1,1,1,1,1]

fmap sum . fmap (take 5) $ (ones :: Maybe [Int])  -- Just 5
mconcat . sequence . fmap (take 5) $ (ones :: Sum [Int])  -- Sum { getSum = 5 }

-- 型を指定すると処理を変えられる
sample = mconcat . sequence . fmap (take 5) $ ones
sample :: Sum Int       --- Sum { getSum = 5 }
sample :: Product Int   --- Product { getProduct = 5 }
```

---

### mdo

`rec`を自動でつけてくれる `mdo`というのも使える。
こっちはghciでも使えた。

```
> :set -XRecursiveDo
> mdo xs <- return (1:xs); return xs
```

---

### もうひとつ例

```haskell
{-# LANGUAGE RecursiveDo #-}
import Data.Monoid
import Control.Monad.Fix

oneTwos :: MonadFix m => m [Int]
oneTwos = do
 rec xs <- return (1:ys)  -- ysを束縛する前にysがつかえる
     ys <- return (2:xs)  -- トランポリン再帰
 return xs                -- コンパイルするためにかいてるだけ
 
oneTwos  -- [1,2,1,2,1,2 .....
```

---

# もっと詳しく

---

## fix とは

mfixはfixのモナド版

```
> :t fix
fix :: (a -> a) -> a
> :t mfix
mfix :: MonadFix m => (a -> m a) -> m a

```

`a -> m a` あたりがモナド版っぽい

---

### 不動点コンビネータ

> 不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数fの不動点とは、f(x) = xを満たすようなxのことをいう。
>
> https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF

---

### fixは関数の不動点のひとつ求める高階関数

お、おう。

---

### 無名関数で再帰できる

雑に言うとそういうことらしい。

---

### 利用してみる

```
> :t fix
fix :: (a -> a) -> a
> fix $ \f -> 3
3
> fix $ \f -> f  -- \f -> f を呼び出してしまい再帰して停止しない
```

入力がないため定数を返すぐらいしかできない。

第１引数に、「第１引数を適用済みの自分自身」が入ってくる感じ。

---

### 引数を追加してつかってみる

引数が10より大きくなるまで2を足し続ける

```
> let rec = fix $ \f x -> if x > 10 then x else f (x+2)
> rec 1
11
> rec 2
12
> rec 11
11
```

`f = \x -> if x > 10 then x else f (x+2)`って感じ。

---


### `rec 1`を簡約してみる


1. rec 1
1. **(fix (\f x -> if x > 10 then x else f (x+2)))** 1 -- rec 置き換え
1. (**let z =** (\f x -> if x > 10 then x else f (x+2)) **z in z**) 1 -- fix を置き換え
1. **((\f x -> if x > 10 then x else f (x+2)) z)** 1 -- `z`を置き換え
1. **(\x -> if x > 10 then x else z (x+2))** 1 -- z を関数に適用
1. **if 1 > 10 then 1 else z (1+2)** -- 1を関数に適用
1. **z (1+2)** -- if を処理した
1. z **3** -- (1+2) を処理
1. **(\f x -> if x > 10 then x else f (x+2)) z** 3 -- z を置き換え
1. **if 3 > 10 then 3 else z (3+2)** -- z と 3を関数適用
1. (\f x -> if x > 10 then x else f (x+2)) z 5 -- ifを処理して zを展開 (3+2) を処理
1. if 5 > 10 then 5 else z (5+2) -- zと5を関数適用
1. (\f x -> if x > 10 then x else f (x+2)) z 7  -- 略
1. if 7 > 10 then 7 else z (7+2)  -- 略
1. (\f x -> if x > 10 then x else f (x+2)) z 9  -- 略
1. if 9 > 10 then 9 else z (9+2)  -- 略
1. (\f x -> if x > 10 then x else f (x+2)) z 11  -- 略
1. if 11 > 10 then 11 else z (11+2)  -- 略
1. 11 -- 解

---

### リストの和をとってみる

fixをつかってリストの和を計算してみます

```
> let sum = fix $ 
	\f acc (x:xs) ->	if xs == []
					  	then
					   		f
					   	else
					   		f (acc+x) xs
> sum 0 [1..10]
55
```

コピペ用

```
let sum = fix $ \f acc (x:xs) -> if xs == [] then f else f (acc+x) xs
```

---

## mfixをつかってみる

---

## IOでループしてみる

空行が入力されるまでエコーし続ける例

```
rpl = mfix \f -> return $ do \x ->
	putStrLn x
	if x == ""
	then
		putStrLn ">> finish"
	else
		input <- getLine
		f input
rpl >>= \f -> f ">> start"   -- 関数がMonadに包まれてるので取り出してから利用  (Applicativeとして使おうと試みたけどうまくいかなかった)
```

コピペ用

```
let rpl = mfix (\f -> return (\x -> putStrLn x >> if x == "" then putStrLn ">> finish" else getLine >>= \y ->  f y))
rpl >>= \f -> f ">> start"
```

---

## MonadFix則

* mfix (return . h) = return (fix h)   
	* returnしてからmfixしても fixしてからreturnしても結果が同じになる
* 
mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
	* f に適用する値 x はmfixから不動点をみつけて、取り出して使う
		* yはaから取り出してつかう
		* xとyの取り出し順序はどちらからでもよい
* mfix (liftM h . f) = liftM h (mfix (f . h)), for strict h.
	* 値が決まるまで繰り返すんだからきまった後に適用する関数は外に出せる
* mfix (\x -> mfix (\y -> f x y)) = mfix (\x -> f x x)
	* ネストは一つにまとめられる

---

# まとめ

* fixは無名関数で再帰できる
* mfixはfixのモナド版
* MonadFixを使うと再帰的do記法が使える
  * mfixをつかうと再帰的な束縛ができる
* GHC8.0からMonadFix増えてる

---

# 参考文献

* https://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Monad-Fix.html
* https://wiki.haskell.org/MonadFix
* https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#the-recursive-do-notation