computation
何らかの値を受け取って、そこから何らかの値を生み出すもの
紛らわしいのでcomputationと呼ぼうmrsekut.icon
日本語のArrow解説記事では「計算」と呼んでいるものが多い
Category cat a b
catによって、aをbに変換する
computationであることの公理
以下の2つを満たす必要がある
恒等生
id . f == f . id == f
結合性
(f . g) . h = f . (g . h)
普通の関数a -> b
catを(->)にしたもの
型エイリアスにすると、type Func a b = a -> b
「Kleisli arrow」などとも言う
アクションを返す関数のようなmrsekut.icon catをモナドmにしたもの
型エイリアスにすると、type Kleisli m a b = a -> m b
非決定性a -> [b]
1つの入力に対し、複数の返り値がある
返り値が一つに決まらないのが「非決定性」
type NonDet a b = a -> [b]のような型
状態変換(s,a) -> (s,b)
state transformers
sは状態
集合と考えて良い
スタックマシンのスタックに積んでいる要素の集合とかmrsekut.icon
型エイリアスにすると、type State s a b = (s, a) -> (s, b)
写像変換(h -> a) -> (h -> b)
behaviour transformers
hを何とみなすかによって色々解釈できる
ある時刻tにおける値を返す
ある場所pにおける値を返す
ある状態sにおける値を返す
型エイリアスにすると、type MapTrans h b c = (h -> b) -> (h -> c)
「単純オートマン(simple automata)」って一般的な名詞なの？
具体的に何を指しているのかわかっていないmrsekut.icon
newtype Auto a b = A(a -> (b, Auto a b)
newtype Hyper b c = H (Hyper c b -> c)
stream transformersStream b -> Stream c
わからんmrsekut.icon
Fudgets-style stream processors
data SP a b = Put b (SP a b) | Get (a -> SP a b)
わからんmrsekut.icon
参考
Examplesが載っている
各例に論文なども載っていて良い