Project

General

Profile

Feature #14423

Enumerator from single object

Added by zverok (Victor Shepelev) 21 days ago. Updated 19 days ago.

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:85251]

Description

Sometimes (or rather often), there is a programming pattern of "start from one object, do something, look at the result, do the same, look at the result (and so on)".

Examples:

  • fetch page by URL, if pagination present, fetch next page;
  • take 10 jobs from the queue, process them, exit when queue is empty;

Typically, those are represented by while or loop + break which somehow feels "not functional enough", and even "not Ruby enough", so much less expressive than map and other Enumerable/Enumerator-based cycles.

In some functional languages or libraries, there is function named FixedPoint or converge, whose meaning is "take an initial value, repeat the block provided on the result on prev computation, till it will not 'stable'". I believe this notion can be useful for Rubyists too.

Reference implementation (name is disputable!):

class Object
  def converge(&block)
    Enumerator.new { |y|
      prev = self
      y << self
      loop do
        cur = block.call(prev)
        raise StopIteration if cur == prev
        y << cur
        prev = cur
      end
    }
  end
end

Examples of usage:

# Functional kata: find the closest number to sqrt(2):
1.0.converge { |x| (x + 2 / x) / 2 }.to_a.last # => 1.414213562373095
Math.sqrt(2) # => 1.4142135623730951

# Next page situation:
get(url).converge { |page| page.next } 
# => returns [page, page.next, page.next.next, ...til the result is nil, or same page repeated]

# Job queue situation:
queue.top(10).converge { |jobs| 
  jobs.each(&:perform)
  queue.top(10) 
}
# => takes top 10 jobs, till queue is empty (`[]` is returned two successful times)

# Useful for non-converging situations, too:
2.converge { |x| x ** 2 }.take(4)
# => [2, 4, 16, 256]

# Idiomatic Fibonacci:
[0, 1].converge { |f0, f1| [f1, f0 + f1] }.take(10).map(&:first)
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Reference to similar things:

  • Clojure iterate "Returns a lazy sequence of x, (f x), (f (f x)) etc." No converging, just infinite sequence... And maybe that is even more basic and idiomatic. The name is nice, too.
  • WolframLang FixedPoint
  • Ramda converge
  • Elixir Stream#unfold (ends iteration when nil is returned)
  • Scala Iterator#iterate (just infinite sequence)

Possible call-seq:

  • If converges: Object#converge(&block), Enumerator.converge(object, &block);
  • If just an infinite sequence: Object#iterate(&block), Object#deduce(&block) (as opposed to reduce), Enumerator.iterate(object, &block), Enumerator#enumerate(object, &block).

WDYT?..

PS: Can imagine somebody already proposed that, yet can't find nothing similar in the tracker for all keywords I've tried.

History

#1 Updated by zverok (Victor Shepelev) 21 days ago

  • Description updated (diff)

#2 [ruby-core:85258] Updated by sos4nt (Stefan Schüßler) 21 days ago

exit when queue is empty [...] til the result is nil, or same page repeated

All those conditions are quite different. Your reference implementation only handles the latter (cur == prev), it doesn't check for nil, let alone "queue is empty".

You actually need two blocks: one to calculate the next value and another one to determine whether the loop should end.

An infinite sequence seems to make more sense.

#3 [ruby-core:85264] Updated by zverok (Victor Shepelev) 21 days ago

All those conditions are quite different.

Well, you can say that next page fetching "converges" up to "no more pages left" (which in some APIs represented by infinite repetition of the same page, while in other with an empty page), and job queue "converges" to empty queue.

But the more I think about it, the more I feel like just "infinite sequence" would be quite enough. You can make the "converger" or anything from the infinite enumerator, with take_while and other nice Enumerable stuff.

#4 [ruby-core:85276] Updated by shan (Shannon Skipper) 20 days ago

I found it really interesting to compare Object#converge with an Object#unfold based on Elixir's Stream.unfold/2. Here's my Ruby implementation:

class Object
  def unfold
    Enumerator.new do |yielder|
      next_acc = self

      until next_acc.nil?
        element, next_acc = yield next_acc
        yielder << element
      end
    end
  end
end

Comparing examples, when it's converging, #converge really shines.

1.0.converge { |x| (x + 2 / x) / 2 }.to_a.last
#=> 1.414213562373095

1.0.unfold { |x| next_x = (x + 2 / x) / 2; [x, (next_x unless x == next_x)] }.to_a.last
#=> 1.414213562373095

When the return value isn't mapped at all, #converge is also simpler.

2.converge { |x| x ** 2 }.take(4)
#=> [2, 4, 16, 256]

2.unfold { |x| [x, x ** 2] }.take(4)
#=> [2, 4, 16, 256]

When it's unfolding, #unfold shines.

[0, 1].converge { |f0, f1| [f1, f0 + f1] }.take(10).map(&:first)
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

[0, 1].unfold { |f0, f1| [f0, [f1, f0 + f1]] }.take(10)
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

I'm intrigued by this proposal.

#5 [ruby-core:85285] Updated by zverok (Victor Shepelev) 20 days ago

BTW, just infinite enumerator is converted to "converger" without lot of problems:

class Object
  def iterate(&block)
    Enumerator.new { |y|
      prev = self
      y << self
      loop do
        cur = block.call(prev)
        y << cur
        prev = cur
      end
    }.lazy
  end
end

p 1.0.iterate { |x| (x + 2 / x) / 2 }.each_cons(2).take_while { |prev, cur| prev != cur }.force.last.last

So, "just lazy infinite sequence" is probably the way to go.

#6 [ruby-core:85321] Updated by sos4nt (Stefan Schüßler) 19 days ago

Maybe it could be as simple as:

class Object
  def iterate
    Enumerator.new { |y|
      obj = self
      loop do
        y << obj
        obj = yield obj
      end
    }
  end
end

1.0.iterate { |x| (x + 2 / x) / 2 }.slice_when(&:==).first.last
#=> 1.414213562373095

#7 [ruby-core:85323] Updated by zverok (Victor Shepelev) 19 days ago

1.0.iterate { |x| (x + 2 / x) / 2 }.slice_when(&:==).first.last
#=> 1.414213562373095

( ͡° ͜ʖ ͡°)
Nice.

Also available in: Atom PDF