豊福です。

原さん
>>  tail で次の解が見つかってから take(0) が実行されるんですね。
>>結局解2個求めるのに解3個生成していたのでした。
>>ここにも遅延評価の問題が出てくるのですね。
  ...
> Ruby じゃ self を遅延評価させるわけにもいかないですからねえ:-)。も
> ちろん、複数の Proc オブジェクトを渡したり、ブロックで条件分岐させ
> て、複数のパラメータの遅延評価をエミュレートできますが「いつ実際に
> 評価させるか」という事に関して場当たり的にならざるを得ない。

  本質的解決ではないかもしれませんがこんなのどうでしょう。
エッセンスはささださんの [ruby-math:00873] と同じだと思います。

def delay(list)
  List.new(nil) { list }
end

def List(x, &b)
  delay List.new(x, &b)
end

class List
  def head0; @head; end
  def tail0; @tail; end
  def tail0=(x); @tail = x; end

  def force
    while (@head.nil? && @tail != nil)
      x = @tail.call
      @head = x.head0
      @tail = x.tail0
    end
  end

  def head
    force
    @head
  end

  def tail
    force
    # x = List.new(nil, @tail) だとエラーになるので
    x = List.new(nil)
    x.tail0 = @tail
    x
  end

  def null?
    force
    @head.nil? && @tail.nil?
  end

  def take(n)
    if n <= 0 || null? # n <= 0 を null? より先にチェックすること
      List(nil)
    else
      List(head){tail.take(n-1)}
    end
  end
  ...
end

---
                        豊福
                        ttoyofukujp / yahoo.co.jp