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

lotz (@lotz84_)

"Grokking Fix"

一見するとよく分からない fix 関数の挙動を、実際に不動点を求めたりリストの関数を実装したりモナドと組み合わせたりしながら、例を通して解説した記事

https://www.parsonsmatt.org/2016/10/26/grokking_fix.html