functional programming

[Brian Candler]

Ruby doesn't work like that.

irb(main):033:0> plus4 = lambda { |x| x + 4}
plus4 = lambda { |x| x + 4}
#<Proc:0x00325230@(irb):33>
irb(main):034:0> (plus4 2)
(plus4 2)
NoMethodError: undefined method `plus4' for main:Object
from (irb):34
irb(main):035:0>

plus4.call(2), or more briefly, plus4[2]

Yes, a variable holding a lambda is a different beast to a method. As
you said, methods are associated with objects, and lambdas are not.
Usually one suits the usage case better than the other.

I find the distinct behaviours of both to be very useful in practice.

 

[Mike Gold]

(2) to understand Mike's assertion
that Ruby lambdas are not first-class functions (i.e. "The difference
between lambda { } and a real first-class function is quite profound").

Ruby:

mean = lambda { |*args|
(args.inject(0) { |acc, x| acc + x })/args.size.to_f
}
data = [[1,2,3], [4,5,6,7]]

data.map(&mean) # fail
data.map(&:mean) # fail
data.map { |*numbers| mean.call(*numbers) } # fail
data.map { |numbers| mean.call(*numbers) } # phew, found it

Haskell:

map mean data

On this example alone, I think my characterization of "quite profound"
is justified.

 

[Mike Gold]

Yes, a variable holding a lambda is a different beast to a method. As
you said, methods are associated with objects, and lambdas are not.
Usually one suits the usage case better than the other.

I find the distinct behaviours of both to be very useful in practice.

Can you give an example of where the difference is "very useful"? In
every case I've encountered, it has been a hassle.

Because programmers can and should always be refactoring and changing
their mind, this entails the drudgework of adding/removing the
'.call()'s or the '[]'s or (in ruby 1.9) the '.()'s. The worst
outcome is when a programmer doesn't bother to refactor because of the
hassle.

By the way, since locals are determined at parse time, I don't see any
particular reason why this cannot work:

bisect = lambda { |x, y| (x + y)/2.0 }
# ...
bisect(5, 6)

Whether or not that _should_ work is a different story. The pro is
that I can swap lambdas and methods without changing syntax. The con
is, at least, that the meaning of existing code could change (when a
bisect method already exists).

 

[Mike Gold]

By the way, since locals are determined at parse time, I don't see any
particular reason why this cannot work:

bisect = lambda { |x, y| (x + y)/2.0 }
# ...
bisect(5, 6)

Whether or not that _should_ work is a different story. The pro is
that I can swap lambdas and methods without changing syntax. The con
is, at least, that the meaning of existing code could change (when a
bisect method already exists).

I see this is a bad idea due to the cases where the lambda is not a
local variable.

[lambda { |x, y| (x + y)/2.0 }].first(5, 6)

Since the rule couldn't apply here, the special-case exception for a
local lambda would be silly.

 

[William James]

# Example: convert all hash keys to strings
src = {ne=>1, :two=>2}

# Imperative
out = src.inject({}) { |h,(k,v)| h[k.to_s] = v; h }

# Functional
out = src.inject({}) { |h,(k,v)| h.merge(k.to_s => v) }

src = {ne,1, :two,2}
==>{ne=>1, :two=>2}
Hash[ *src.map{|k,v| [k.to_s,v]}.flatten ]
==>{"two"=>2, "one"=>1}

 

[Joel VanderWerf]

(2) to understand Mike's assertion
that Ruby lambdas are not first-class functions (i.e. "The difference
between lambda { } and a real first-class function is quite profound").

Ruby:

mean = lambda { |*args|
(args.inject(0) { |acc, x| acc + x })/args.size.to_f
}
data = [[1,2,3], [4,5,6,7]]

data.map(&mean) # fail
data.map(&:mean) # fail
data.map { |*numbers| mean.call(*numbers) } # fail
data.map { |numbers| mean.call(*numbers) } # phew, found it

Haskell:

map mean data

On this example alone, I think my characterization of "quite profound"
is justified.

Why isn't this the ruby candidate for comparison:

mean = lambda { |ary|
(ary.inject { |acc, x| acc + x })/ary.size.to_f
}
data.map(&mean) # => [2.0, 5.5]

 

[William James]

So to make a list, first, the basic building block, the cons cell:

(class Cons
(attr_accessor :car)
(attr_accessor :cdr)
(def initialize(car,cdr)
(@car = car)
(@cdr = cdr)
end)
end)


Let's wrap this object into a functional abstraction layer:

(def cons(car,cdr)
(Cons . new(car,cdr))
end)

(def car(x)
(x . car)
end)

(def cdr(x)
(x . cdr)
end)

(def null(x)
(x . nil?)
end)

irb(main):040:0> (cons 1,2)
#<Cons:0x7fdfb53eb808 @cdr=2, @car=1>
irb(main):042:0> (car (cons 1,2))
1
irb(main):043:0> (cdr (cons 1,2))
2
irb(main):044:0> (null (cons 1,2))
false
irb(main):045:0> (null (car (cons 1,nil)))
false
irb(main):046:0> (null (cdr (cons 1,nil)))
true



Then you can build a list over these cons cells:

(def list(*args)
(i = (args . length))
(r = nil)
(loop {
(if (i == 0)
(break)
else
(i = (i - 1))
(r = (cons (args [ i ]),r))
end)
})
r
end)

irb(main):127:0> (list 1,2,3)
#<Cons:0x7fdfb53b81d8 @cdr=#<Cons:0x7fdfb53b8200
@cdr=#<Cons:0x7fdfb53b8228 @cdr=nil, @car=3>, @car=2>, @car=1>


Let's print them pretty:

(def printelements(cons)
(if (Cons === cons)
(if (Cons === (car cons))
(printlist (car cons))
else
(print (car cons))
end)
(if (Cons === (cdr cons))
(print " ")
(printelements (cdr cons))
elsif (not (null (cdr cons)))
(print " . ")
(print (cdr cons))
end)
else
(print cons)
end)
end)

(def printlist(cons)
(print "(")
(printelements cons)
(print ")")
cons
end)

(def terpri()
(print "\n")
end)


irb(main):263:0> (begin
(terpri)
(printlist (list 1,2,3))
(terpri)
end)

(1 2 3)
nil

You can also add some higher level abstractions:

(def first(list)
(car list)
end)

(def rest(list)
(cdr list)
end)

(def endp(list)
(if (Cons === list)
nil
elsif (null list)
true
else
(error ("Expected a list instead of the atom " + (list . to_s)))
end)
end)



Once you've got this list abstraction, you can build functions such
as reverse:

(def revappend(list,tail)
(if (null list)
tail
else
(revappend (cdr list),(cons (car list),tail))
end)
end)

(def reverse(list)
(revappend list,nil)
end)



irb(main):267:0> (begin
(printlist (reverse (list 1,2,3)))
(terpri)
end)
(3 2 1)
nil



Now we also need the function abstraction. In ruby functions have to
be in modules, and always qualified by the module name. This is not
pretty, so we will allow any method to be treated as a function, but
we will ignore it's recipient object, always passing self.

# For methods, the first function argument is the recipient of the
# message:

(def method(designator,arity=(-1))
# Important: the given arity must include the recipient object,
but not the recipient class: # (method :==,2) .call(42,42) vs.
42.==(42) (if (arity == -1)
# This is the default, bugged behavior:
(Proc . new {| x , *args | (x . send(designator , *args))})
elsif (arity == 0)
(raise (Exception.exception("An instance method must have an
arity>=1, not 0."))) else
(arity = (arity - 1))
(args = (((arity == 0)? "" : " , ") + (((1 .. arity) . map { |
i | ("a" + i.to_s) }) . join(" , ")))) (eval("(Proc . new { |
x" + args + " | " + "( x . send( :" + (designator . to_s)
+ args + " ))})")) end)
end)


# for functions, the recipient of the message is always 'self', all
# arguments are passed as arguments.

(def function(designator,arity=(-1))
# Important: the given arity must include the recipient object, but
not the recipient class: # (function "SOME_MODULE.someFunction",1)
.call(42) vs. SOME_MODULE.someFunction(42) # (function
:someFunction ,2) .call(42) vs. self.someFunction(42)
or someFunction(42) (if (String === designator) mod , met =
(designator . split(".")) (if (arity == -1)
# This is the default, bugged behavior:
(Proc . new {| *args | ((eval mod) . send((met . to_sym) ,
*args))}) else
(args = (((1 .. arity) . map { | i | ("a" + i.to_s) }) .
join(" , "))) (sep = " ")
(if (0 < arity)
(sep = " , ")
end)
(eval("(Proc . new { | " + args + " | " +
"( " + mod + " . send( :" + met + sep + args + "
))})")) end)
else
(if (arity == -1)
# This is the default, bugged behavior:
(Proc . new {| x , *args | (x . send(designator , *args))})
elsif (arity == 0)
(eval("(Proc . new {" +
"(" + (designator . to_s) + " )})"))
else
(args = (((1 .. arity) . map { | i | ("a" + i.to_s) }) .
join(" , "))) (eval("(Proc . new { | " + args + " | " +
"(" + (designator . to_s) + " " + args + " )})"))
end)
end)
end)


(def funcall(fun,*args)
(fun . call(*args))
end)



irb(main):370:0> (funcall (method :+,2),3,4)
(funcall (method :+,2),3,4)
7

irb(main):478:0> (begin
(terpri)
(printlist (funcall (function :reverse,1),(list
1,2,3))) (terpri)
end)

(3 2 1)
nil

You have certainly proved that everything is 10 times as hard
as it should be when you use Commune Lisp!

Ruby:

[1,2,3].reverse
==>[3, 2, 1]

[1,2,3].send :reverse
==>[3, 2, 1]

Now that you have first class functions, you can start to implement
higher level functions:

(def mapcar (fun,list)
(if (endp list)
nil
else
(cons (funcall fun,(first list)),(mapcar fun,(rest list)))
end)
end)


irb(main):271:0> (begin
(printlist (mapcar (lambda {|x| (x + 1)}),(list
1,2,3))) (terpri)
end)

(2 3 4)
nil

Ruby:

[1,2,3].map{|x| x + 1}
==>[2, 3, 4]


or:

augment = proc{|x| x + 1}
==>#<Proc:0x0282c2cc@(irb):11>
[1,2,3].map &augment
==>[2, 3, 4]

So at least, now you can find the smallest element of a list:

This function implements an accumulator pattern: we pass the partial
result along with the parameters. We process the list item by item
and when its finished we return the result we've accumulated so far:

(def smallestElement(list,minimum)
(if (endp list)
minimum
elsif (minimum < (first list))
(smallestElement (rest list),minimum)
else
(smallestElement (rest list),(first list))
end)
end)

(def smallest(list)
(smallestElement (rest list),(first list))
end)



irb(main):422:0>
(begin
(terpri)
(printlist (mapcar (function :smallest,1),(list (list 1),
(list 1,1,1,1),
(list 1,2,3,4),
(list 4,3,2,1),
(list
1,2,3,4,3,2,1),
(list 4,3,2,1,2,3,4)))) (terpri)
end)

(1 1 1 1 1 1)
nil

Ruby:

[[1],[1,1,1,1],[1,2,3,4],[4,3,2,1],[1,2,3,4,3,2,1],[4,3,2,1,2,3,4]].
map{|a| a.min}
==>[1, 1, 1, 1, 1, 1]



Yes, COBOL Lisp is an ancient, cumbersome, and clunky language.
Ruby is to it as a transistor is to a vacuum tube.

 

[William James]

There's a difference between (def smallest(x) ; x ; end)
and (smallest = (lambda { |x| x }))

In the former case, you can write (smallest [1,2,3])
in the later you can't:


irb(main):001:0> (def smallest(x) ; x ; end)
(def smallest(x) ; x ; end)
nil
irb(main):002:0> (smallest [1,2,3])
(smallest [1,2,3])
[1, 2, 3]
irb(main):003:0> (smallest = (lambda { |x| x }))
(smallest = (lambda { |x| x }))
#<Proc:0x0035fdf4@(irb):3>
irb(main):004:0> (smallest [1,2,3])
(smallest [1,2,3])
(irb):3: warning: multiple values for a block parameter (3 for 1)
from (irb):4
[1, 2, 3]

foo = proc{|x| "#{x.size} items: #{ x.join ' & ' }" }
==>#<Proc:0x0282ded8@(irb):15>
foo.call( [2,3,4] )
==>"3 items: 2 & 3 & 4"
foo[ [2,3,4] ]
==>"3 items: 2 & 3 & 4"

 

[William James]

difference >> between lambda { } and a real first-class function is
quite profound").

Ruby:

mean = lambda { |*args|
(args.inject(0) { |acc, x| acc + x })/args.size.to_f
}
data = [[1,2,3], [4,5,6,7]]

data.map(&mean) # fail
data.map(&:mean) # fail
data.map { |*numbers| mean.call(*numbers) } # fail
data.map { |numbers| mean.call(*numbers) } # phew, found it

Haskell:

map mean data

On this example alone, I think my characterization of "quite
profound" is justified.

Why isn't this the ruby candidate for comparison:

mean = lambda { |ary|
(ary.inject { |acc, x| acc + x })/ary.size.to_f
}
data.map(&mean) # => [2.0, 5.5]

mean = proc{|a| a.inject{|s,x| s+x} / a.size.to_f }
==>#<Proc:0x027949e0@(irb):19>
data.map &mean
==>[2.0, 5.5]

 

[Mike Gold]

data = [[1,2,3], [4,5,6,7]]
On this example alone, I think my characterization of "quite profound"
is justified.

Why isn't this the ruby candidate for comparison:

mean = lambda { |ary|
(ary.inject { |acc, x| acc + x })/ary.size.to_f
}
data.map(&mean) # => [2.0, 5.5]

Sure, you can solve a different problem than the one I gave.
But the original problem remains. We cannot, in general, modify
'mean'.

Do you propose to change every method in the ruby standard library
to take just one argument--an array? That would work. Sounds like
Lisp.

 

[William James]

I would like if this sort could be made of Ruby functions;
inject,select, detect, reject, collect, not with "module" you
implemented. And it doesnt't have to be a list sorting; can be an
array sorting or something. I'm not an expert in knowing all
differences between all kinds of collections. And what about
recursion ? If I want to sort an array do I have to use recursion and
how ? There are tutorials on functional programming in general but
not with Ruby. Does anybody maybe has some link to something similar ?

>"Haris Bogdanovic"

I managed to find a minimum:

[1,6,4,7,8].inject {|a,b| if a < b then a else b end}

but I can't still find a way to sort list (functional way and not
with existing sort method)

One difficulty is that vectors are difficult to handle with purely
functional programming: you cannot modify them, not a single slot;
when you want to change just one slot of a vector, in purely
functionnal programming, you have to define a whole new vector,
that contains the same elements as the old vector, but for the one
that is "changed".

But you asked first for lists, and I showed you how to implement
lists. So now it should be easy to implement a functionnal sort
algorithm working on lists.

For an exemple here is a simple merge sort. We need a function to
merge two lists:

(def mergelist(list1,list2,lessp)
(if (endp list1)
list2
elsif (endp list2)
list1
elsif (funcall lessp,(first list1),(first list2))
(cons (first list1),(mergelist (rest list1),list2,lessp))
else
(cons (first list2),(mergelist list1,(rest list2),lessp))
end)
end)


irb(main):545:0>
(begin
(terpri)
(printlist (mergelist (list 1,3,5,7,8,9,11),(list
2,4,6,10,11,12,13),(method :<))) (terpri)
end)

(1 2 3 4 5 6 7 8 9 10 11 11 12 13)
nil



Then a function to split a list into two parts separated by a pivot
(one list containing all the elements smaller-or-equal to the
pivot, and the other all the elements greater than the pivot):

(def values(*values)
values
end)


(def splitlistinternal(list,pivot,lessp,less,more)
(if (endp list)
(values less,more)
elsif (funcall lessp,pivot,(first list))
(splitlistinternal (rest list),pivot,lessp,less,(cons (first
list),more)) else
(splitlistinternal (rest list),pivot,lessp,(cons (first
list),less),more) end)
end)

(def splitlist(list,pivot,lessp)
(splitlistinternal list,pivot,lessp,nil,nil)
end)


(def valuelist(values)
(list *values)
end)



irb(main):604:0>
(begin
(terpri)
(printlist (valuelist (splitlist (list 1,2,3,4,5,6,7),3,(method
:<)))) (terpri)
end)

((3 2 1) (7 6 5 4))
nil


With these two utilities, writting a functional merge sort is
trivial:

(def sortlist(list,lessp)
(if ((endp list) or (endp (rest list)))
list
else
(pivot = (first list))
(less,more = (splitlist (rest list),pivot,lessp))
(mergelist (sortlist less,lessp),(cons pivot,(sortlist
more,lessp)),lessp) end)
end)


irb(main):635:0>
(begin
(terpri)
(printlist (mapcar (lambda{|list|
(sortlist list,(method :<))
}),(list (list),(list 1),(list
5,4,3,2,1),(list 1,2,3,4,5),(list 1,3,5,4,2),(list 5,3,1,2,4))))
(terpri) end)

(nil (1) (1 2 3 4 5) (1 2 3 4 5) (1 2 3 4 5) (1 2 3 4 5))
nil

Ruby:

def merge list1, list2, &less
return list1 + list2 if list1.empty? or list2.empty?
less = ( less or proc{|a,b| a < b} )
less[ list1[0], list2[0] ] and
[ list1[0] ] + merge( list1[1..-1], list2, &less ) or
[ list2[0] ] + merge( list1, list2[1..-1], &less )
end

p merge( [1,3,5], [2,4,6] )
p merge( [-1,-3,-5], [-2,-4,-6] ){|a,b| a > b}

def merge_sort list
return list if list.size < 2
half = list.size / 2
merge merge_sort( list[0...half] ), merge_sort( list[half..-1] )
end

p merge_sort( [9,2,8,5,6,3] )
5.times{|i| p merge_sort( (0..i).to_a.reverse ) }

 

[William James]

It's a clever way to get
people accustomed to parens without actually using Lisp. A way-point
on the road to enlightenment.

There you have it. Hierophants of Commune Lisp are utter irrational.
It's a religion to them. In comp.lang.lisp you will find threads
named "How did you discover Lisp?", i.e., "How did you get religion?"

 

[William James]

I did mean half the speed, i.e. OCaml is slower.

OCaml is a high-level language, but code written in OCaml still
manages to achieve ~50% of the speed of hand-written C. Given that C
can be considered portable machine code, this is a pretty impressive
achievement.

Don't take Ed seriously. You will find that he never posts any
Ruby code that he has written.

And he has already been taught that OCaml can be as fast as C:

http://groups.google.com/group/comp.lang.ruby/browse_thread/thread/e2138
1fb5b6a47f6

 

[Robert Dober]

The interpreter is going to have many new objects created around, and
so there will be more work for the garbage collector or more memory
used, am I wrong?

Yes or let us say you will be wrong very soon .

Have a look at this to understand why:
http://rubyconf2008.confreaks.com/how-ruby-can-be-fast.html

HTH
Robert

 

[William James]

utter irrational.

utterly

 

[Mike Gold]

There you have it. Hierophants of Commune Lisp are utter irrational.
It's a religion to them. In comp.lang.lisp you will find threads
named "How did you discover Lisp?", i.e., "How did you get religion?"

Ironically, a distinguishing characteristic of zealotry is the
inability to recognize waggishness or sarcasm.

There are several clues you could have picked up.

(1) If you are at all familiar with Star Wars, you could have noticed
that I paraphrased Obi-Wan Kenobi in the same post.

(2) Even if you've never heard of Star Wars, the hyperbolic nature of
my post should have been obvious.

(3) If you cared to check whether your assumptions had any merit, you
could have noticed the 40 non-trolling posts I've made to
comp.lang.ruby. No posts to comp.lang.lisp.

(4) I contributed a small patch to Ruby; I appear in the ChangeLog.

On the other hand, your posting history reveals that you persistently
troll comp.lang.lisp with Ruby evangelism, much to the annoyance of
its inhabitants.

"If you hate a person, you hate something in him that is part of
yourself. What isn't part of ourselves doesn't disturb us."
--Herman Hesse

 

[M. Edward (Ed) Borasky]

Don't take Ed seriously. You will find that he never posts any
Ruby code that he has written.

Not to the mailing list ... but to RubyForge

And he has already been taught that OCaml can be as fast as C:

Of course any language *can* be as fast as any other language. But will
it be *predictably* so for a wide class of benchmarks or applications? I
rather doubt it.

 

[David A. Black]

Hi --

Brian Candler wrote:
(2) to understand Mike's assertion
that Ruby lambdas are not first-class functions (i.e. "The

difference >> between lambda { } and a real first-class function is
quite profound").

Ruby:

mean = lambda { |*args|
(args.inject(0) { |acc, x| acc + x })/args.size.to_f
}
data = [[1,2,3], [4,5,6,7]]

data.map(&mean) # fail
data.map(&:mean) # fail
data.map { |*numbers| mean.call(*numbers) } # fail
data.map { |numbers| mean.call(*numbers) } # phew, found it

Haskell:

map mean data

On this example alone, I think my characterization of "quite
profound" is justified.

Why isn't this the ruby candidate for comparison:

mean = lambda { |ary|
(ary.inject { |acc, x| acc + x })/ary.size.to_f
}
data.map(&mean) # => [2.0, 5.5]

mean = proc{|a| a.inject{|s,x| s+x} / a.size.to_f }
==>#<Proc:0x027949e0@(irb):19>
data.map &mean
==>[2.0, 5.5]

I believe that's the same as what Joel just posted (give or take some
cosmetics). Or is my eye skipping over something?


David

--
David A. Black / Ruby Power and Light, LLC
Ruby/Rails consulting & training: http://www.rubypal.com
Coming in 2009: The Well-Grounded Rubyist (http://manning.com/black2)

http://www.wishsight.com => Independent, social wishlist management!

 

[Joel VanderWerf]

data = [[1,2,3], [4,5,6,7]]
On this example alone, I think my characterization of "quite profound"
is justified.

Why isn't this the ruby candidate for comparison:

mean = lambda { |ary|
(ary.inject { |acc, x| acc + x })/ary.size.to_f
}
data.map(&mean) # => [2.0, 5.5]

Sure, you can solve a different problem than the one I gave.
But the original problem remains. We cannot, in general, modify
'mean'.

Do you propose to change every method in the ruby standard library
to take just one argument--an array? That would work. Sounds like
Lisp.

Sorry, I may not have followed the discussion very well.

But it seems more natural in this specific case to define mean to take
one array argument, rather than *args, since (or so I imagine), that's
usually how input will arrive. How often do you write code like

x = ...
y = ...
z = ...
m = mean.call( x,y,z )

as opposed to

a = ...
m = mean.call( a )

?

Perhaps I'm distracted by the specifics of mean and missing the general
point...

 

[Mike Gold]

Perhaps I'm distracted by the specifics of mean and missing the general
point...

'mean' stands for anything. I should have called it 'some_func'. You
can't just change its meaning. In particular, you can't change the
methods in the ruby standard library. (Well, you can, but you'll be
in danger of receiving a painful retributive wedgie from those who use
your code. Perhaps even an atomic one.)

You can always write wrappers which convert a given method or lambda
to a one-argument lambda expecting an array. But this is just another
kind of Lisp emulation in Ruby, taking non-homogeneous primitives and
making them homogeneous.