配列のスライスで cdr

Array オブジェクトを正規リストとみなしてみましょう。 空の Array オブジェクトは、 当然、 空リストです。 では、 3 個の要素を持つ Array オブジェクトではどうでしょうか。 car は先頭の要素なのは明らかです。 一方、 cdr は先頭を除く残りの要素が並んだリストになっているべきです。

null?([]) #=> true

car([:a, :b, :c]) #=> :a
cdr([:a, :b, :c]) #=> [:b, :c]
cddr([:a, :b, :c]) #=> [:c]
cdddr([:a, :b, :c]) #=> []

素朴には、 cdr は、 Array オブジェクトをスライスして新しく作成した Array オブジェクトを返すことになるのでしょう。

def car(x) x.first end
def cdr(x) x[1..-1] end

Ruby 処理系の内部実装が、 Array オブジェクトのスライスと元のオブジェクトとが、 実態となる要素列を共用してくれていると良いのですけど、 要素列も複写する実装になっているかもしれません。 それに、 スライスと元とでは要素列を常に共用しておかないと、 set-car! 手続きのふるまいが Pair オブジェクトの並びでリストを作る場合とで異なってしまいかねません。

そこで、 cdr のために、 あからさまにスライス・オブジェクトでラッピングすることにしましょう。

def null?(x)
  x.nil? or (Array === x and x.empty?)
end

def pair?(x)
  if Array === x
    x.size > 0
  else
    x.respond_to?(:first) and x.respond_to?(:last)
  end
end

def car(x)
  pair?(x) or raise "not a pair -- car"
  x.first
end

def cdr(x)
  pair?(x) or raise "not a pair -- cdr"
  if Array === x
    TailSlice.new(x, 1)
  else
    x.last
  end
end
  
class TailSlice
  def initialize(a, i) @ary, @cursor = a, i end
  def first() @ary[@cursor] end
  def last()
    (@cursor + 1 < @ary.size) ? self.class.new(@ary, @cursor + 1) : nil
  end
  def inspect() @ary[@cursor .. -1].inspect end
end