fix関数 - mrsekut-p

fix関数

不動点コンビネータの1つ

引数に取る関数fの最小不動点を返す

Control.Monad.Fixに定義されている

定義 ref

code:hs

fix :: (a -> a) -> a

fix f = f (fix f)

不動点コンビネータの定義をそのまま書き下している

定義2

code:hs

fix :: (a -> a) -> a

fix f = let x = f x in x

不動点反復法の定義をそのまま書き下している

let x_{n+1} = f x_nのようなイメージから発想すれば、自然に↑のような定義になる

定義を見れば分かる通り、引数に与えた関数が無限に適用される

code:_

fix g

= g (fix g)

= g (g (fix g))

...

= g (g (g (g (... (g (fix g)) ...))))

例えば、(0:)という関数を適用すれば、0の無限リストが得られる

code:hs

fix (0:)

関連

https://stackoverflow.com/questions/25876042/what-does-fixio-do

参考

Haskell/不動点と再帰 - Wikibooks

「最も定義されていない不動点」というのは、意味近似順序における最小であるということ

不動点の話 - あどけない話

fix関数の導出

Fix関数の教科書 (Haskell) - Qiita