From: mental@...
Date: 2005-12-17T09:18:02+09:00
Subject: multiple blocks (unfold)

I've been pondering how to write an "unfold" in Ruby lately, and
I've not really found any non-awkward ways to do it yet.

For those not familiar, unfold is basically the inverse of foldl
(Ruby's inject); in its native form (as seen in most functional
languages), it takes four arguments:

 - an initial state

 - a predicate (tests the state to know when to stop)

 - a transformer (converts a state to an output value)

 - an incrementor (converts a state to the next state)

It would look something like:

 def Array.unfold( s, p, f, g )
  arr = []
  until p.call( s )
    arr << f.call( s )
    s = g.call( s )
  end
  arr
 end

You'd use it something like:

 a = Array.unfold( 0, lambda { |s| s > 10 }, lambda { |s| s * 2 },
lambda { |s| s + 1 } )

That's pretty ugly in Ruby terms, though.  The nicest way I've
thought of so far would be something like:

 class Unfolder
   def initialize &block
     (class << self
       def self.stop? &block
         define_method :stop?, &block
       end
       def self.f &block
         define_method :f, &block
       end
       def self.g &block
         define_method :g, &block
       end
       self
     end).class_eval &block
   end

   # reasonable defaults?
   def stop?( s ) ; s ; end
   def f( s ) ; s ; end
   def g( s ) ; g.succ ; end
 end

 def Array.unfold( s, &block )
   unfolder = Unfolder.new &block
   arr = []
   until unfolder.stop? s
     arr << unfolder.f s
     s = unfolder.g s
   end
   arr
 end

Which could be used something like:

 a = Array.unfold( 0 ) {
   stop? { |s| s > 10 }
   f { |s| s * 2 }
   g { |s| s + 1 }
 }

But that's kinda icky and probably slow-like.

Anyone got some better ideas?

-mental