multiple blocks (unfold)

[men...@rydia.net]

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

[men...@rydia.net]

Sorry, needs some parens to parse:

Quoting men...@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

[Devin Mullins]

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

>-mental
>
>
>
>
>

[men...@rydia.net]

Quoting Devin Mullins <twi...@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

[Christian Neukirchen]

men...@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. :-)

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 <chneuk...@gmail.com> http://chneukirchen.org

[MenTaLguY]

On Sun, 2005-12-18 at 00:41 +0900, Christian Neukirchen wrote:
> men...@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. :-)

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

[Csaba Henk]

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

[Phil Tomson]

In article <m28xujr...@gmail.com>,

Christian Neukirchen <chneuk...@gmail.com> wrote:
>men...@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. :-)

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.

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]

pt...@aracnet.com (Phil Tomson) writes:

> In article <m28xujr...@gmail.com>,
> Christian Neukirchen <chneuk...@gmail.com> wrote:
>>men...@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. :-)
>
> 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.

> Phil

[Christian Neukirchen]

MenTaLguY <men...@rydia.net> writes:

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