09/04/03 11:16:16
carやcdrがちゃんと理解できん・・・
アセンブラの方が簡単かも。
694:デフォルトの名無しさん
09/04/03 12:14:13
そんなに難しいかな？
単方向リンクリストの、先頭を取り出すか、それ以外を取り出すか、
だけなんだが。
695:デフォルトの名無しさん
09/04/03 12:16:17
括弧とドットの表記法でつまづくか、ポインタでつまづくかのどっちかですよねー
696:デフォルトの名無しさん
09/04/03 12:42:44
carは左って覚えれば良いと思うよ
697:デフォルトの名無しさん
09/04/03 12:48:44
>>693
コンスは単なる2つのポインタの対
Lispよりも低レベルではcarとcdrは可換で線形リストとは何の関係もない
線形リストに利用しているのはLispより高レベルだけの話
アセンブラ的に考えればこう
698:デフォルトの名無しさん
09/04/03 13:05:28
まずボックス表記を手で書いて
それからいろんな構造をconsだけで組み立てる
ドット対→線形単リスト→２分木みたいに徐々に複雑にしていくといい
699:デフォルトの名無しさん
09/04/03 13:14:01
Common Lisp: A Gentle Introduction to Symbolic Computation 付録の sdraw 使うと図示してくれる
CL-USER> (sdraw '(1 2 3 (4 5)))
[*|*]--->[*|*]--->[*|*]--->[*|*]--->NIL
| | | |
v v v v
1 2 3 [*|*]--->[*|*]--->NIL
| |
v v
4 5
URLﾘﾝｸ(www.cs.cmu.edu)
700:デフォルトの名無しさん
09/04/03 13:17:57
ちゃんと理解できないったって(と)の対応はわかりますよね？
Lispのリスト記法はドット記法の構文糖
任意のリスト記法はドット記法で表せる（逆は偽）
ドット記法の基本は( A . B )でホワイトスペース＋ドット＋ホワイトスペースがcarとcdrの間の仕切り
（開き／閉じ括弧の周りはホワイトスペースの省略可）
そしてドット記法を(A B C)みたいなに直すのは
ドット＋開き括弧を見つけたら、それと、それに対応する閉じ括弧を消しゴムで消すだけ
701:デフォルトの名無しさん
09/04/03 13:22:22
( A . B ) ≡ [ A | B ]
702:デフォルトの名無しさん
09/04/03 14:15:16
(cons 'a 'b) => (a . b)
(cons 'a (cons 'b '())) => (a b)
'(a . (b . (c . ()))) => (a b c)
703:デフォルトの名無しさん
09/04/03 14:22:09
'とかquoteが絡んでくると解りづらくなるから
任意のアルファベット１文字のシンボルと空リストは自己評価的という設定にしよう
(cons A B) => (A . B) ;; [ A | B ]
(cons A ()) => (A . ()) ≡ (A) ;; [ A | NIL ]
(cons (cons A B) ()) => ((A . B) . ()) ≡ ((A . B)) ;; [ [ A | B ] | NIL ]
(cons () (cons A ())) => (() . (A . ())) ≡ (() A) ;; [ NIL | [ A | NIL ] ]
(cons A (cons B C)) => (A . (B . C)) ≡ (A B . C) ;; [ A | [ B | C ] ]
704:デフォルトの名無しさん
09/04/03 14:24:40
lispのリストはヘテロジニアスリストでさらにペアにもなるから難しいよな
ML系みたいにリストは空か値とリストを持つコンスって定義だとまだわかりやすいのに
705:デフォルトの名無しさん
09/04/03 15:27:28
分かりにくくないだろw
706:デフォルトの名無しさん
09/04/03 15:48:41
ふと思ったんですけど
効率の為にlistではなくvectorを使っているアルゴリズムって
静的にコンパイル＋破壊的代入なしって条件なら
プログラマにはlistとして見せつつ
内部的にはvectorとして処理できませんかね？
たとえば(list 1 2 3 4 5)は
表面的にはコンスによる線形リストなんだけど内部的には#(1 2 3 4 5)であるオブジェクトを返すとか。
書き換えられない事が解っているn要素の線形リストは2ワードのセルをn個アロケートするより
nワード+αのベクタで記憶するほうがよさそう。
Haskellが文字列をリストとして実装してるのはそんな理由だったりするのでしょうか？
707:デフォルトの名無しさん
09/04/03 15:50:16
それは「cdr coding」と呼ばれるもので散々実験済み。
708:デフォルトの名無しさん
09/04/03 15:52:55
書き込んでから気づいたけど、
部分リストを複数オブジェクトで共有している場合
先頭部分の参照がはずれてもGCで回収できなくて逆に効率が悪くなりますね。
ベクタの最初の方だけGCできる方法を取れば別ですけど
そうするとベクタの情報が増えて結局コンスと大差なくなるかも
709:デフォルトの名無しさん
09/04/03 16:14:39
>>707
おや、そうでしたか。不勉強でした。
見た所、線形リストを少しでも効率よく処理する為の物の様で
ベクタを置き換えるには至らなかったようですね。
710:デフォルトの名無しさん
09/04/03 16:35:18
vector的利用がはっきりしているところでは、
vectorを使えばいいしね。
listで構造体を模倣してprototypingしても、
accessor使っておけば簡単に移行できるし。
711:デフォルトの名無しさん
09/04/03 17:59:01
evalと大域変数でhashを模倣する初心者を見てニヤニヤするんですよねー
712:デフォルトの名無しさん
09/04/03 18:02:44
それは君だけ。
713:デフォルトの名無しさん
09/04/03 22:15:13
やべえ、サボってたらSeasoned Schemerわかんねえw
また後戻りか…英語もやってないし… λ.......