EoPL reading (50) 2.1 Specifying Data via Interfaces
もう 50 か。
Exercise.2-2
ええと、提示されたそれぞれの実装を批判的に分析せよ、それらがデータ型の仕様を満足させるか否かの範囲は何か、という理解で良いのかな。
まず Unary representaion から
これは大きい値の表現が微妙。length で簡単に値が取れますが、例えば 1000 とかもう一桁上の数値とか、値を取得するだけで O(n) なのは微妙。
# いちいち指で数えてる的?
あと、plus をトレイスしてみる。
(plus '(#t #t) '(#t #t #t)) (succ (plus (pred '(#t #t)) '(#t #t #t))) (succ (plus '(#t) '(#t #t #t))) (succ (succ (plus (pred '(#t)) '(#t #t #t)))) (succ (succ (plus '() '(#t #t #t)))) (succ (succ '(#t #t #t))) (succ '(#t #t #t #t)) '(#t #t #t #t #t)
append の実装ってどうなってるんだろ。と言いつつ gauche の実装が以下。
#define SCM_APPEND1(start, last, obj) \ do { \ if (SCM_NULLP(start)) { \ (start) = (last) = Scm_Cons((obj), SCM_NIL); \ } else { \ SCM_SET_CDR((last), Scm_Cons((obj), SCM_NIL)); \ (last) = SCM_CDR(last); \ } \ } while (0) #define SCM_APPEND(start, last, obj) \ do { \ ScmObj list_SCM_GLS = (obj); \ if (SCM_NULLP(start)) { \ (start) = (list_SCM_GLS); \ if (!SCM_NULLP(list_SCM_GLS)) { \ (last) = Scm_LastPair(list_SCM_GLS); \ } \ } else { \ SCM_SET_CDR((last), (list_SCM_GLS)); \ (last) = Scm_LastPair(last); \ } \ } while (0)
この実装だと単純に append した方が早いな。あとこの形は負の値の表現は絶対に不可能ですね。