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


"Kristof Bastiaensen" <kristof@vleeuwen.org> schrieb im Newsbeitrag
news:pan.2004.08.10.22.30.13.485476@vleeuwen.org...
> Hi,
>
> On Tue, 10 Aug 2004 23:11:43 +0200, Robert Klemme wrote:
> >> 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
> >
>
> That's all nice and esoteric, but I don't see why it is a
> reason against empty? or size.

It is.  Regard:

if enum.empty?
  puts "it's empty"
else
  enum.each {|x| puts "found #{x}"}
end

This code could not do what you expect because the properties empty? and
size would change between invocations.  The guarantee, that each iteration
returns the same sequence of elements is just not part of the contract of
Enumerable.

>  In fact, if that would be
> important, than the other methods in Enumerable shouldn't
> also be there.  Take for example the following:
>
>   require "enumerator"
>   to_enum(:loop).map
>
> There is nothing that prevents that.  In fact I currently have
> irb eating up slowly all the memory. Does that mean there
> shouldn't be a map method?

No.  Same holds for recursion.  But it's a different story:

>  I think it is possible to find
> pathological cases for the other methods in Enumerable

RandomEnum is not a pathological case, it's a completely legitimate
implementation that conforms to all that is expected from #each.  And
while these kinds of implementations are not widely used I still don't
regard them esoteric.

And infinite loop will always lead to problems, regardless whether it
appears due to endless recursion or as infinite iteration.  So IMHO that's
not an argument agains any construct.

> (I'll leave that as an exercise for the reader).
>
> IMO the reason against size is that is not possible to implement
> efficiently.

That's not an argument IMHO because classes including Enumerable most
likely override size and empty? with their own efficient implementations.

>  As for empty?, I don't know.  I find it useful,
> and as shown by other people easy to implement.

I've changed my mind here: the contract of Enumerable (or of #each if you
like) is too weak to guarantee a proper implementation of size and empty?.
The requirements on #each are really very weak and you can't provide a
proper size and empty? method for each classes using Enumerable.  So IMHO
it's best to leave them out or put them in a separate module.

Kind regards

    robert