Multiple blocks (unfold)

ruby-talk
1

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

2

Sorry, needs some parens to parse:

Quoting mental@rydia.net:

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

-mental

3

mental@rydia.net wrote:

Anyone got some better ideas?

The only other idea I can think of at the moment is one I've seen in a lot of Java DSLs (and in FlexMock):

class Unfolder
   class << self
     def stop? &block
       new.stop? &block
     end
     def f &block
       new.f &block
     end
     def g &block
       new.g &block
     end
   end

   # reasonable defaults?
   def initialize
     @p = lambda {|s| !s}
     @f = lambda {|s| s}
     @g = lambda {|s| s.succ}
   end

   def stop?(&b) @p = b; self end
   def f(&b) @f = b; self end
   def g(&b) @g = b; self end
   def unfold(s)
     arr =
     until @p.call(s)
       arr << @f.call(s)
       s = @g.call(s)
     end
     arr
   end
end

Usage:

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

Completely untested, and full of duplication, but you get the idea.

Devin

···

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.

-mental

4

mental@rydia.net writes:

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.

C'mon, let's do complete hylomorphisms. :slight_smile:

class Hylo
  class << self
    alias_method :taking, :new
  end

  def initialize(start)
    @start = start

    # Useful defaults.
    @final = lambda { |x| x.nil? }
    @map = lambda { |x| x }

    @init =
    @each = lambda { |a, e| a << e }

    @step = lambda { |x| raise ArgumentError, "No do block given." }
  end

  def do(&block); @step = block; self; end
  def till(&block); @final = block; self; end
  def collecting(&block); @map = block; self; end
  def injecting(init, &block); @init, @each = init, (block||@each); self; end

  def to_a
    v = @start
    r = @init

    until @final[v]
      r = @each[r, @map[v]]
      v = @step[v]
    end
    
    r
  end
end

def evens(n)
  Hylo.new(0).
    do { |x| x + 2 }.
    till { |x| x >= n }.
      to_a
end

def fact(n)
  Hylo.taking(n).
    do { |x| x - 1 }.
    till { |x| x <= 1 }.
    injecting(1) { |a, e| a * e }.to_a
end

def tobin(n)
  Hylo.new(n).
       do { |x| x / 2 }.
       till { |x| x <= 0 }.
       collecting { |x| (x % 2).to_s }.
       injecting('').to_a
end

def expand(n)
  Hylo.new(n).
       do { |x| x[1..-1] }.
       till { |x| x.empty? }.
       collecting { |x| x.first[0] * x.first[1] }.
       injecting('').to_a
end

p evens(20)
p fact(7)
p tobin(42)
p expand([['a', 6], ['b', 4], ['c', 2]])

···

-mental

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

5

Quoting Devin Mullins <twifkak@comcast.net>:

Usage:

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

Hey, that's not too bad. Use the named parameter idiom from Java.

It's a little weird from a Ruby perspective, but except for being
(essentially) curried it's rather like the way you'd do it in
Smalltalk.

-mental

6

Hey, this is pretty good. It might be worth into turning into a gem.

Only thing is I don't know about to_a ... there's no real reason the
result has to be an array versus some other type (I've got lazy streams
in mind, at least).

-mental

···

On Sun, 2005-12-18 at 00:41 +0900, Christian Neukirchen wrote:

mental@rydia.net writes:

> 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.

C'mon, let's do complete hylomorphisms. :slight_smile:

7

In article <m28xujrarx.fsf@gmail.com>,

mental@rydia.net writes:

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.

C'mon, let's do complete hylomorphisms. :slight_smile:

Had to look that one up. wikipedia says:
a philosophical concept that highlights the significance of matter in the
composition of being, regarding matter to be as essential to a being as its
form.

.....but I don't feel any more enightened than I was prior to looking it up.
What does 'hylomophism' mean in this context? Most all of the google hits had
something to do with philosophy.

class Hylo
class << self
   alias_method :taking, :new
end

def initialize(start)
   @start = start

   # Useful defaults.
   @final = lambda { |x| x.nil? }
   @map = lambda { |x| x }

   @init =
   @each = lambda { |a, e| a << e }

   @step = lambda { |x| raise ArgumentError, "No do block given." }
end

def do(&block); @step = block; self; end
def till(&block); @final = block; self; end
def collecting(&block); @map = block; self; end
def injecting(init, &block); @init, @each = init, (block||@each); self; end

def to_a
   v = @start
   r = @init

   until @final[v]
     r = @each[r, @map[v]]
     v = @step[v]
   end
   
   r
end
end

def evens(n)
Hylo.new(0).
   do { |x| x + 2 }.
   till { |x| x >= n }.
     to_a
end

def fact(n)
Hylo.taking(n).
   do { |x| x - 1 }.
   till { |x| x <= 1 }.
   injecting(1) { |a, e| a * e }.to_a
end

def tobin(n)
Hylo.new(n).
      do { |x| x / 2 }.
      till { |x| x <= 0 }.
      collecting { |x| (x % 2).to_s }.
      injecting('').to_a
end

def expand(n)
Hylo.new(n).
      do { |x| x[1..-1] }.
      till { |x| x.empty? }.
      collecting { |x| x.first[0] * x.first[1] }.
      injecting('').to_a
end

p evens(20)
p fact(7)
p tobin(42)
p expand([['a', 6], ['b', 4], ['c', 2]])

this is quite cool even if I'm not quite sure how hylomorphism applys.

BTW: in regards to the other 'advanced Ruby book' threads recently, this is
just the sort of thing I'd like to see in a 'Higher Order Ruby' type book.

Phil

···

Christian Neukirchen <chneukirchen@gmail.com> wrote:

8

I wrote up a small metaprogramming library back in the spring which
adds this syntax to Ruby classes/modules in an (IMHO) convenient way:

http://creo.hu/~csaba/ruby/multiblocks/

Csaba

···

On Sat, Dec 17, 2005 at 10:03:32AM +0900, mental@rydia.net wrote:

Quoting Devin Mullins <twifkak@comcast.net>:

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

Hey, that's not too bad. Use the named parameter idiom from Java.

It's a little weird from a Ruby perspective, but except for being
(essentially) curried it's rather like the way you'd do it in
Smalltalk.

9

MenTaLguY <mental@rydia.net> writes:

mental@rydia.net writes:

> 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.

C'mon, let's do complete hylomorphisms. :slight_smile:

Hey, this is pretty good. It might be worth into turning into a gem.

Only thing is I don't know about to_a ... there's no real reason the
result has to be an array versus some other type (I've got lazy streams
in mind, at least).

True, #to_a is left-over. Not sure what it should be called, tho.

···

On Sun, 2005-12-18 at 00:41 +0900, Christian Neukirchen wrote:

-mental

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

10

ptkwt@aracnet.com (Phil Tomson) writes:

In article <m28xujrarx.fsf@gmail.com>,

mental@rydia.net writes:

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.

C'mon, let's do complete hylomorphisms. :slight_smile:

Had to look that one up. wikipedia says:
a philosophical concept that highlights the significance of matter in the
composition of being, regarding matter to be as essential to a being as its
form.

.....but I don't feel any more enightened than I was prior to looking it up.
What does 'hylomophism' mean in this context? Most all of the google hits had
something to do with philosophy.

I use the term hylomorphism in the context of category theory, where a
hylomorphism is a compsite of an anamorphism (unfold) and an
catamorphism (fold/inject).

http://tunes.org/wiki/Morphism

http://www.cs.nott.ac.uk/~cvh/hylos/hylos.pdf

this is quite cool even if I'm not quite sure how hylomorphism applys.

BTW: in regards to the other 'advanced Ruby book' threads recently, this is
just the sort of thing I'd like to see in a 'Higher Order Ruby' type book.

Yeah, me too.

···

Christian Neukirchen <chneukirchen@gmail.com> wrote:

Phil

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org