From: Robert Klemme <bob.news@...>
Date: 2004-08-11T06:16:15+09:00
Subject: Re: empty? and size in Enumerable


"Martin DeMello" <martindemello@yahoo.com> schrieb im Newsbeitrag
news:A7aSc.68614$M95.20909@pd7tw1no...
> Robert Klemme <bob.news@gmx.net> wrote:
> > "Martin DeMello" <martindemello@yahoo.com> schrieb im Newsbeitrag
> > >
> > > Can empty? be reliably implemented in terms of each for every
> > > enumerable? I can't think of an obvious problem with it, but that
> > > doesn't mean there isn't one.
> >
> > Yes, that's possible IMHO.  My suggestion would be:
> >
> > module Enumerable
> >   # O(1)
> >   def empty?
> >     each { return false }
> >     true
> >   end
>
> My concern was if #each created a temporary data structure in O(n) time
> (e.g. an ordered hash) - this would make sense for #each, since its
> running time is O(n) anyway, but would be a large hit for empty?

Hm, that's true.  Although that argument would not stop me from advocating
#empty?  Runtimes of each enumerable class differ anyway.  Classes override
this method usually anyway.  It's a different case with #size which has been
shown to not terminate for certain non totally esoteric implementations.

Here's maybe another reason: emty? and size both depend on an Enumerable
with a deterministic amount of elements.  This need not always be the case:

class RandEnum
  include Enumerable

  def each
    rand(10).times { yield rand 20 }
    self
  end
end

>> r=RandEnum.new
=> #<RandEnum:0x1019fc10>
>> r.to_a
=> [15, 7]
>> r.to_a
=> [12, 8, 11, 2, 17, 13, 18, 5, 16]
>> r.to_a
=> [9, 15, 19, 12, 3, 2, 0]
>>

I start believing that because of this and the termination problem it was
indeed a wise decision of Matz to not include them in Enumerable.  And a sub
module for DeterministicEnumerable that adds these two methods to Enumerable
wouldn't be a big win.  So it's probably best the way it is now.

Thanks for the discussion!

Kind regards

    robert