Is it possible, a fully general Enumerable#recursive ?
in [Ruby]
|
From: Colin Bartlett on 11 Apr 2010 08:51 On Sat, Apr 10, 2010 at 7:05 PM, Intransition <transfire(a)gmail.com> wrote: > On Apr 9, 6:38 pm, Colin Bartlett <colin...(a)googlemail.com> wrote: >> I'm not sure that it is a bug. ... > > Thanks, that helped me understand a little better. > > After working on this for far too long, I have concluded that a highly > generalized implementation of recursion for all (or at least most) > enumerable methods not feasible. http://www.askoxford.com/concise_oed/feasible?view=uk feasible: adjective 1 possible and practical to achieve easily or conveniently. 2 informal likely. I think that's the precise word: I'd concluded that it was probably possible, but probably too complicated, and I was having difficulties getting things to work with "to_enum" in a consistent way, or indeed sometime at all. (For example, a recursive Array#map! worked, but a recursive Array#map didn't.) > But there are still many things in common between recursion methods, > so instead I have created a Recursor class > to act something like an Enumerator for recursive operations. The idea of having a Recursor class hadn't occurred to me, and that seems (at first thoughts) quite possibly fruitful as a solution.
From: Robert Klemme on 11 Apr 2010 16:51 On 04/09/2010 08:53 PM, Intransition wrote: > > On Apr 9, 2:03 pm, Robert Dober <robert.do...(a)gmail.com> wrote: >> On Thu, Apr 8, 2010 at 5:51 AM, David Masover <ni...(a)slaphack.com> wrote: >>> On Wednesday 07 April 2010 04:49:15 pm Intransition wrote: >> <snip> >> >>>> This works for #each and #map but not #sort. >>> #sort isn't a method of Enumerable, it's a method of Array. >> ruby-1.9.1-p378 > Enumerable.instance_methods.grep /sort/ >> => [:sort, :sort_by] >> However you will need to define #<=> on the return value of recursive. Why that? The whole point would be to sort all elements that would be recursively returned. The #recursive return value would never be seen then. > Yep. That's trick b/c comparing and array or other enumerable to a non > enumerable raises an error. So sorting with this is probably out of > the question. On a side note, I am not so sure that raising an error > is best. Why not just assume that too non-comparable things are equal? See above. Here are my two solutions with plain old Enumerator approach. I do not see the benefit of a Functor here. 1. simple module Enumerable def recursive(&b) if b each do |e| if Enumerable === e e.recursive(&b) else b[e] end end self else Enumerator.new(self, :recursive) end end end 2. catch loops module Enumerable def recursive(items = {}, &b) if b each do |e| items.fetch e.object_id do |oid| items[oid] = e if Enumerable === e e.recursive(items, &b) else b[e] end end end self else Enumerator.new(self, :recursive) end end end This one suffers the fragility that callers providing something else than an empty Hash can break it. That could be fixed with a bit more effort by using a thread local. Just using the simple approach is probably better since there is no notification of loops anyway so the using code has zero chance to handle the case of loops which might be important to know. Another note: your original code suffered from the inability to mix different Enumerables because you use "self.class" for the type check. I changed that by only testing for Enumerable. Kind regards robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/
From: Robert Dober on 12 Apr 2010 07:35 On Sun, Apr 11, 2010 at 10:55 PM, Robert Klemme <shortcutter(a)googlemail.com> wrote: > On 04/09/2010 08:53 PM, Intransition wrote: >> >> On Apr 9, 2:03 pm, Robert Dober <robert.do...(a)gmail.com> wrote: eed to define #<=> on the return value of recursive. > > Why that? The whole point would be to sort all elements that would be > recursively returned. The #recursive return value would never be seen then. #each takes care of structure #<=> takes care of order, IOW #recursive is called from #each, or did I miss something here? Cheers R. -- Learning without thought is labor lost; thought without learning is perilous. --- Confucius
From: Robert Klemme on 12 Apr 2010 11:08 2010/4/12 Robert Dober <robert.dober(a)gmail.com>: > On Sun, Apr 11, 2010 at 10:55 PM, Robert Klemme > <shortcutter(a)googlemail.com> wrote: >> On 04/09/2010 08:53 PM, Intransition wrote: >>> >>> On Apr 9, 2:03 pm, Robert Dober <robert.do...(a)gmail.com> wrote: > eed to define #<=> on the return value of recursive. >> >> Why that? The whole point would be to sort all elements that would be >> recursively returned. The #recursive return value would never be seen then. > #each takes care of structure #<=> takes care of order, IOW As far as I understand the initial posting of this thread the whole point is to create "something" (aka an Enumerator) whose #each method recursively iterates through nested Enumerables. This implies that during that iteration only elements inside Enumerables are yielded which are not Enumerable. Hence there is no need to provide a generalized <=> because x.recursive.sort only ever sees those non Enumerable elements. Of course, sort only can work properly if all elements have the same type, are compare compatible or an explicit comparison block is passed to #sort. > #recursive is called from #each, or did I miss something here? Technically speaking yes, but more correct would be to say that #recursive is invoked from #recursive. (=> my implementation for an example) I don't really understand why this thread seems to be so complicated. I suspect that either I am missing something or not understanding properly, or other contributors to this thread are missing something. :-) Kind regards robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/
From: Intransition on 12 Apr 2010 11:51
On Apr 11, 4:55 pm, Robert Klemme <shortcut...(a)googlemail.com> wrote: > >> However you will need to define #<=> on the return value of recursive. > > Why that? The whole point would be to sort all elements that would be > recursively returned. The #recursive return value would never be seen then. Do you run into the issue of sorting [1,2,3, [:a,:b,:c]] where by an error is raised when it tries, 1 <=> [:a,:b,:c] ? > > Yep. That's trick b/c comparing and array or other enumerable to a non > > enumerable raises an error. So sorting with this is probably out of > > the question. On a side note, I am not so sure that raising an error > > is best. Why not just assume that too non-comparable things are equal? > > See above. > > Here are my two solutions with plain old Enumerator approach. I do not > see the benefit of a Functor here. > > 1. simple > > module Enumerable > def recursive(&b) > if b > each do |e| > if Enumerable === e > e.recursive(&b) > else > b[e] > end > end > self > else > Enumerator.new(self, :recursive) > end > end > end Yes, that's the basic definition. It does have issues though. For one, the Enumerator isn't very useful, as it doesn't seem able to handle the recursion very will (compare #with_index and #map, etc.). Another issue is hashes, they won't iterate well here. In Ruby 1.8.7 or less you also get an infinite loop b/c String's are Enumerable, so an exception really needs to be made for them. Other than all that it works ;-) > 2. catch loops > > module Enumerable > def recursive(items = {}, &b) > if b > each do |e| > items.fetch e.object_id do |oid| > items[oid] = e > > if Enumerable === e > e.recursive(items, &b) > else > b[e] > end > end > end > self > else > Enumerator.new(self, :recursive) > end > end > end Nice use of #fetch, btw. > This one suffers the fragility that callers providing something else > than an empty Hash can break it. That could be fixed with a bit more > effort by using a thread local. Just using the simple approach is > probably better since there is no notification of loops anyway so the > using code has zero chance to handle the case of loops which might be > important to know. Is it important? recursive graphs seem so rare anyway, and if your doing an recursive iteration wouldn't an infinite loop be expected? Just as if one were iterating over an infinite sequence? > Another note: your original code suffered from the inability to mix > different Enumerables because you use "self.class" for the type check. > I changed that by only testing for Enumerable. I have two versions actually, one testing for Enumerable and one testing for self.class, I think both are useful. But you are right, to address the original question (of the previous thread on this topic) testing for Enumerable is the one needed.. |