Tree とか List とか Peano数 とか Church encoding
-
- いいね！1
tomo🐧@learning
@cocoatomo
@halcat0x15a 木と区別するのであれば, やっぱり List かと思います. (ただし, functional な文脈前提ですが.)
2012-10-05 19:26:53
梶本裕介
@uskz
@cocoatomo @halcat0x15a (cons)リストはdata L a = X | Y (a, L a), Church encodingはC a = (a -> a) -> (a -> a), church 0 = \f -> \x -> x...って感じでは
2012-10-05 19:26:59
ねこはる
@halcat0x15a
@uskz あ、だとchurch encodingはちょと違いますね。 なんだろう、自身を一回だけ参照してて構成子が２つのもののこと？かなあ。
2012-10-05 19:33:42
tomo🐧@learning
@cocoatomo
@uskz @halcat0x15a あー, church encoding はそうですね. んー, リストは Y をどう見るかによると思いますが……
2012-10-05 19:34:33
梶本裕介
@uskz
@cocoatomo @halcat0x15a 僕の中でリストは何かしらの集合のデカルト冪の元という認識なので、コンストラクタでその集合の値を渡してあげるイメージがありました。A = X | Y Aでも単元集合上のリストと一対一対応があるのでリストと言っても問題ないとは思いますが
2012-10-05 19:48:47
tomo🐧@learning
@cocoatomo
@uskz @halcat0x15a 「再帰構造があり, かつ木ではない」とのことで,「直線状の構造」をリストと呼んだだけで, それ以上のイメージは持ってないです.
2012-10-05 19:57:58
hiratara
@hiratara
@cocoatomo @halcat0x15a @uskz さんの通りdata A = X | Y AだとListじゃなくてpeano数かと。data Nat = Zero | Succ Nat と data List a = Nil | Cons a (List a) ですし。
2012-10-05 20:00:03
tomo🐧@learning
@cocoatomo
@hiratara @halcat0x15a @uskz そこで,「A = List a, X = Nil, Y = Cons a」と当て嵌められない理由がよく分かりません. 何か前提を勘違いしてますか??
2012-10-05 20:02:51
梶本裕介
@uskz
@hiratara @cocoatomo @halcat0x15a グラフ <- 木 <- リスト <- ペアノ数なのでペアノ数がリストというのは間違ってはないかと
2012-10-05 20:05:05
tomo🐧@learning
@cocoatomo
なんかあらかじめ文脈があったなら分かるけど…… あー, X, Y のとこに具体的な値が1個くるようなイメージなのか. まだイメージの前提がよく分かってない感じ. 自分の発想が情報科学より数学に寄ってるのは自覚してますが.
2012-10-05 20:06:50
梶本裕介
@uskz
@cocoatomo @hiratara @halcat0x15a ああ、ぼくはコンストラクタの位置にある変数とかを具現化して考えていました
2012-10-05 20:07:10
hiratara
@hiratara
@cocoatomo @halcat0x15a @uskz たしかにそう言われてみると・・・なにか自分の中で引っかってますが。
2012-10-05 20:10:02