From: Louis J Scoras <louis.j.scoras@...>
Date: 2005-10-26T04:24:38+09:00
Subject: Lazy Streams and Other Functional Goodies

------=_Part_20365_32955441.1130268274416
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hey all;

A really good book I read a little while ago is "Higher Order Perl", by Mar=
k
Jason Dominus. Yes, yes. It is a book about perl, but more importantly its
about doing neat things with closures. There was a thread recently about
functional techniques in Ruby, and some of the ideas in MJDs book can be
ported over pretty easily. In fact, doing this in ruby seems a bit more
natural IMHO.

Anyway, I did a quick rewrite of the lazy (infinite) streams from HOP.

# Adapted from Higher-Order Perl by Mark Dominus, published by Morgan
Kaufmann
# Publishers, Copyright 2005 by Elsevier Inc

class LazyStream

def initialize(h,&bloc)
@head =3D h
@tail =3D bloc
end

attr_reader :head

def tail
if @tail.respond_to? :call
@tail =3D @tail.call
end
@tail
end

def exhausted?
false
end

def self.upto(m, n)
return LazyStream::Terminator.new if m > n
new(m) do
self.upto(m + 1, n)
end
end

def self.upfrom(n)
new(n) do
self.upfrom(n+1)
end
end

def take(n)
stream =3D self.dup
list =3D []
n.times do
return list unless stream
list << stream.head
stream =3D stream.tail
end
list
end

def transform &bloc
t =3D yield head
LazyStream.new(t) do
tail.transform(&bloc)
end
end

def filter &bloc
s =3D self.dup
until s.exhausted? || yield(s.head)
s =3D s.tail
end
return LazyStream::Terminator.new if s.exhausted?
LazyStream.new(s.head) do
s.tail.filter(&bloc)
end
end

end

class LazyStream::Terminator < LazyStream
def initialize; end
def head; nil; end
def tail; nil; end
def transform; self; end
def filter; self; end
def exhausted?; true; end
def take(n); nil; end
end

This lets you do some cool stuff like representing all positive integers:

pos_ints =3D LazyStream.upfrom 1
p pos_ints.take(10)

Back in school I remember having to write a program to generate the first
100 prime numbers. Back then I did it in haskell, which gives you lazy
evaluation for free. But with the above class you can do this to implement
the Sieve of Eratosthenes:

def seive(s)
p =3D s.head
LazyStream.new(p) do
seive(s.tail.filter {|n| n % p !=3D 0})
end
end

def primes
seive LazyStream.upfrom(2)
end

Or you can use the recursive definition rather than the above generator,
which is faster:

$primes =3D LazyStream.new(2) { LazyStream.upfrom(3).filter{|n| is_prime? n=
} }

def is_prime?(x)
r =3D lambda do |stream|
h =3D stream.head
return false if (x % h =3D=3D 0)
return true if (h ** 2 > x)
r.call(stream.tail)
end
r.call($primes)
end

Anyway, sorry for the long post. I guess my point was to ask if anybody is
getting use out of techniques usually associated with "functional
languages?" From the Ruby I've seen--still pretty new--it seems that
closures for callbacks are pretty common, and for resource management. What
about things like Currying? Functional composition?


--
Lou

------=_Part_20365_32955441.1130268274416--