EoPL reading (51) 2.1 Specifying Data via Interfaces

Exercise.2-2

ええと Scheme number representation から。
昨晩のエントリによれば Unary representation 比べて

• 負の数を表現できる
• plus は + でいいじゃん

という事でしたがそれ以外には

• 値を戻す手続きは O(1)
  • Unary representation だと O(n)

上記の n はリストの要素の数に比例、という意味でお願いできれば幸いです。このケイスでは + は O(1) ですが、plus は O(n) っちゃ O(n) か。

Bignum representation

これ、N が 2 だと_Unary representation_と同じです。実は値の上限が決まってるのであれば、この実装は色々な意味で効果があるのではないかな、と思ってます。
これって critically な分析ではないかもしれませんが、上限超過を簡単に検出できそげ。あ、あと succ とか pred の計算量が N に依存してるので、適切な N の設定が必要、ってもの色々な意味でポイント高そげ。
あと、plus が ++ とか -- な手続きに依存してる、ってのも微妙。

この後

どう進めたものか、ちょっと考えます。