不動点と再帰周りを俯瞰する
これ順番に進めないと全く非効率になる
不動点周りの基本的なことを知る
F(f) = f を満たす f を、 F の不動点と呼ぶ任意のラムダ式には不動点が存在する
それを求めるためには不動点コンビネータを使えば良い
関数の不動点を求めるための関数のようなもの
「不動点コンビネータ」は総称
領域理論の基本的なことを知る
ハッセ図式
半順序集合を図示する方法
ルールは単純なので先に知っておくと便利
半順序集合周辺の概念
上限、上界、最大限、極大元、etc.
完備束、有向部分集合、cpo
便利な具体例
cpo、単調写像の具体例
平坦領域の具体例
不動点に戻ってくる
最小不動点
良い資料
Haskellを具体例に、再帰周辺を解説している
↓元の記事と併せて読むと良い
プログラム意味論に関連する領域理論周りの教科書
行間は少なめで読みやすいが、1章分のページのみなので具体例が足りなかったりする
順序集合や束などに関する基本的な概念の説明
具体例が豊富で解説も丁寧なので、上の本の補完に良い
>#WIP
不動点と再帰
HaskellのMonadFIx
不動点はコンパイラの最適化などに用いられる #??
ref 末尾再帰
複雑製理論と接続
圏論と接続
定理
cpo と連続関数による圏はCCC
圏論に対応付ける
fixを用いた最適化？
不動点と再帰関数の関係は？
不動点が関数なら、必ず再帰関数になる #??
そんなことはない？
「再帰関数になる？」って問い、意味不明では？
ちゃんと言い直すなら、
fix + 不動点が関数になる関数 で定義される関数は、再帰関数として定義できる？とか？あらゆる再帰関数は、fixを使って、再帰形を消して定義できる
油断すると「不動点が関数である」となることの意味がわからなくなる
この疑問が頭に浮かんだ時にパッと思い出せる具体例を用意しておきたい
不動点が関数であるってどういうことだっけ？になる
不動点と聞いた時、頭に思い浮かぶのはy=x^2のグラフだったりするので、こうなるともう不動点が関数になることはイメージできなくなる
他の不動点コンビネータも最小不動点を返す #??
最小不動点以外を返す不動点コンビネータは存在する？
不動点を持たない関数もある #??
いやないか
不動点コンビネータと再帰の関係
不動点とは、以下のようなものであった
M = F(M) を満たす M を、 F の不動点と呼ぶ fact を再帰で定義するhsfact :: Int -> Int
fact x = if x == 0 then 1 else x * fact (x - 1) fact を不動点を使って定義するhsfact :: 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) fact' と fact は、再帰呼び出しがない fact は fact' の不動点であるfix関数を使う
hs> fact = fix fact'
> fact 5
120 fix fact' で fact' の不動点を求めるつまり、
f == fact' f となる関数 f を求めるこの
f こそが、 fact だから、
fact == fact' fact hsfact = fact' fact
= if x == 0 then 1 else x * fact (x - 1)これは普通に
fact を再帰的に定義したものと同じ名前を付けずに再帰関数を定義できている様子
hsfact = 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
再起する関数
hsfix :: (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' nfact, fact'内には再帰呼び出しがないのに、再帰になる
Yコンビネータと末尾再帰
Yコンビネータの不動点は？
YY
YY = Y (YY) introduction
構文木をflattenすることを題材にすすめる
flatternを定義する際に、全ての構文木に対して処理を書くのは冗長で、バグの入り込みやすい
そこで
applyExpr という関数を最初に用意しておく applyExpr :: (Expr -> Expr) -> Expr -> Expr 全ての子nodeに、関数
f を適用するものこれを使えば
flattern は2行で定義できる次に、これをもっと一般化する
Expr型に型変数を入れた
ExprF a 型を定義するapplyも一般化できる
apply :: (a -> b) -> ExprF a -> ExprF b これはmapの型に非常に似ている
ExprFをFunctorにする
Foldable、Traversableにもできる
しかし、この型は入れ子に制限が入ってしまう
元のExprと同じにするためには、
type NestedExpr = ExprF (ExprF (ExprF (ExprF …))) のように無限に入れ子を書かないといけないここで、型レベルのyコンビネータを定義できれば、これを表現できることを思いつく
Y Expr が、Expr functorの不動点になればいいちなみに↑の記事、シリーズ化されている
ts
2020/3/3
↑のサイトや、
p.139あたりを読んで、何もわからんってなってる