More than 5 years have passed since last update.

MonadFixを試す

Last updated at 2016-10-11Posted at 2016-10-11

1 / 23

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

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式がパワーアップする

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

つかってみる

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

{-# 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                -- コンパイルするためにかいてるだけ

利用例

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

もうひとつ例

{-# 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`を簡約してみる

rec 1
(fix (\f x -> if x > 10 then x else f (x+2))) 1 -- rec 置き換え
(let z = (\f x -> if x > 10 then x else f (x+2)) z in z) 1 -- fix を置き換え
((\f x -> if x > 10 then x else f (x+2)) z) 1 -- zを置き換え
(\x -> if x > 10 then x else z (x+2)) 1 -- z を関数に適用
if 1 > 10 then 1 else z (1+2) -- 1を関数に適用
z (1+2) -- if を処理した
z 3 -- (1+2) を処理
(\f x -> if x > 10 then x else f (x+2)) z 3 -- z を置き換え
if 3 > 10 then 3 else z (3+2) -- z と 3を関数適用
(\f x -> if x > 10 then x else f (x+2)) z 5 -- ifを処理して zを展開 (3+2) を処理
if 5 > 10 then 5 else z (5+2) -- zと5を関数適用
(\f x -> if x > 10 then x else f (x+2)) z 7 -- 略
if 7 > 10 then 7 else z (7+2) -- 略
(\f x -> if x > 10 then x else f (x+2)) z 9 -- 略
if 9 > 10 then 9 else z (9+2) -- 略
(\f x -> if x > 10 then x else f (x+2)) z 11 -- 略
if 11 > 10 then 11 else z (11+2) -- 略
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として使おうと試みたけどうまくいかなかった)