不動点と再帰周りを俯瞰する

不動点周りの基本的なことを知る

任意のラムダ式には不動点が存在する

それを求めるためには不動点コンビネータを使えば良い

関数の不動点を求めるための関数のようなもの

「不動点コンビネータ」は総称

ハッセ図式

半順序集合を図示する方法

ルールは単純なので先に知っておくと便利

半順序集合周辺の概念

上限、上界、最大限、極大元、etc.

完備束、有向部分集合、cpo

便利な具体例

cpo、単調写像の具体例

平坦領域の具体例

不動点に戻ってくる

最小不動点

良い資料

Haskellを具体例に、再帰周辺を解説している

↓元の記事と併せて読むと良い

プログラム意味論に関連する領域理論周りの教科書

行間は少なめで読みやすいが、1章分のページのみなので具体例が足りなかったりする

順序集合や束などに関する基本的な概念の説明

具体例が豊富で解説も丁寧なので、上の本の補完に良い

不動点と再帰

複雑製理論と接続

圏論と接続

定理

圏論に対応付ける

fixを用いた最適化？

不動点と再帰関数の関係は？

そんなことはない？

あらゆる再帰関数は、fixを使って、再帰形を消して定義できる

油断すると「不動点が関数である」となることの意味がわからなくなる

不動点が関数であるってどういうことだっけ？になる

最小不動点以外を返す不動点コンビネータは存在する？

不動点コンビネータと再帰の関係

不動点とは、以下のようなものであった

code:hs

fact :: Int -> Int

fact x = if x == 0 then 1 else x * fact (x - 1)

code:hs

fact :: Int -> Int

fact = fact' fact -- M = F M

fact' :: (a -> a) -> a -> a

fact' m x = if x == 0 then 1 else x * m (x - 1)

fix関数を使う

code:hs

fact = fix fact'

fact 5

120

code:hs

fact = fact' fact

= if x == 0 then 1 else x * fact (x - 1)

名前を付けずに再帰関数を定義できている様子

code:hs

fact = fix $ \f x -> if x == 0 then 1 else x * f (x - 1)

f = YF

f = YM

f = Ff

f = M(YM)

Y

Yコンビネータ

適用すると不動点を返す

F

なんかの高階関数

f

再起する関数

code:hs

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

fix g = g (fix g)

fact' :: (Eq p, Num p) => (p -> p) -> p -> p

fact' next n = if n == 0 then 1 else n * next (n - 1)

fact n = fix fact' n

fact, fact'内には再帰呼び出しがないのに、再帰になる

Yコンビネータと末尾再帰

Yコンビネータの不動点は？

YY

YY = Y (YY)

introduction

構文木をflattenすることを題材にすすめる

flatternを定義する際に、全ての構文木に対して処理を書くのは冗長で、バグの入り込みやすい

applyExpr :: (Expr -> Expr) -> Expr -> Expr

次に、これをもっと一般化する

applyも一般化できる

apply :: (a -> b) -> ExprF a -> ExprF b

これはmapの型に非常に似ている

ExprFをFunctorにする

Foldable、Traversableにもできる

しかし、この型は入れ子に制限が入ってしまう

ここで、型レベルのyコンビネータを定義できれば、これを表現できることを思いつく

ちなみに↑の記事、シリーズ化されている

ts

2020/3/3