Multiple blocks (unfold)


#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 removed_email_address@domain.invalid:

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

removed_email_address@domain.invalid 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


#4

Quoting Devin M. removed_email_address@domain.invalid:

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


#5

removed_email_address@domain.invalid 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]])


#6

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

removed_email_address@domain.invalid 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).

-mental


#7

On Sat, Dec 17, 2005 at 10:03:32AM +0900, removed_email_address@domain.invalid wrote:

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.

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


#8

MenTaLguY removed_email_address@domain.invalid writes:

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.


#9

In article removed_email_address@domain.invalid,
Christian N. removed_email_address@domain.invalid wrote:

removed_email_address@domain.invalid 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.

Useful defaults.

def till(&block); @final = block; self; end
end
to_a
Hylo.new(n).
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