Functional programming


#1

Hi.

I’m starting to learn functional programming with Ruby.
I would like for someone to write me an example of finding the smallest
number in the list and a sorting algorithm.
I got the concept of map (collect), filter (select, detect and reject)
and
reduce (inject) higher order functions but I don’t know how to compose
algorithms from them.
So please write me those two algorithms or some other simple ones with
some
explanation.
Some links to this subject would be nice also.

Thanks
Haris


#2

I’m starting to learn functional programming with Ruby.

Wouldn’t learning OO programming in Haskel be easier?


#3

I know Ruby programming well but I wanted to add funtional paradigm in
my
programming as it is very usefull.
If you don’t know and are not interested in it you don’t have to insult
me.
And Haskell looks pretty useless to me because it is functional paradigm
only language.

“Phlip” removed_email_address@domain.invalid wrote in message
news:rSf9l.8378$removed_email_address@domain.invalid…


#4

Since you are using Ruby, here is one Ruby way;

list = [6,4,5,8,12,34,5,6,778,9,777,3,45]
p list.min #> 3
p list.sort #> [3, 4, 5, 5, 6, 6, 8, 9, 12, 34, 45, 777, 778]


#5

Haris B. wrote:

I know Ruby programming well but I wanted to add funtional paradigm in
my
programming as it is very usefull.

If you know Ruby well - and you obviously understand functional
programming, because you know it is “usefull” (sic) - then just start
writing functional programs. To do this, make sure that:

  1. you don’t modify any objects. Only use methods which return new
    objects.

  2. once a local variable is assigned, you don’t reassign it.

However Ruby won’t enforce (1) unless you litter your code with ‘freeze’
statements, and it can’t enforce (2) at all.

a = “hello”
a << " world" # wrong: modifies the string
a += " world" # wrong: new string, but assigned to same variable
b = a + " world" # right

Example: convert all hash keys to strings

src = {:one=>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) }

If you don’t know and are not interested in it you don’t have to insult
me.
And Haskell looks pretty useless to me because it is functional paradigm
only language.

Who’s being insulting now? What are you saying about all Haskell
programmers, and all the language designers? Do you genuinely believe
that useful systems cannot be written in Haskell?

Go and look at Erlang. Massive real-world systems are built out of this,
with incredible reliability, using only functional programming and CSP.
It’s also very straightforward to pick up and use, and has a very
comprehensive standard library.

Remember also that functional languages allow all sorts of compile-time
optimisations which are impossible in Ruby, so there is the potential
for much higher performance. For example, OCaml generates code which is
reputedly only half the speed of the equivalent C code.


#6

“M. Edward (Ed) Borasky” removed_email_address@domain.invalid writes:

In short, I suspect that a more practical solution might be a language
that has object orientation and functional coding styles both baked in
right from the start. I’m not an expert on all the dozens of “obscure”
languages out there, so I can’t give any names. But I know they exist.

Common Lisp.


#7

Thank you guys for your answers. Ruby is my favourite language mostly
because it is pure object oriented and above that you can incorporate
functional programming which has it’s advantages; smaller, clearer, less
error prone code.

“Haris B.” removed_email_address@domain.invalid wrote in message
news:gk3m77$1ft$removed_email_address@domain.invalid…


#8

Brian C. wrote:

objects.

  1. once a local variable is assigned, you don’t reassign it.

However Ruby won’t enforce (1) unless you litter your code with ‘freeze’
statements, and it can’t enforce (2) at all.

Well then … just as “it’s possible to write FORTRAN programs in any
language”, it’s possible to write “functional” programs in any
language. But as you point out, a pure functional style “goes against
the grain” in Ruby, if it doesn’t or can’t enforce (or even diagnose)
“non-functional” code.

Programming is as much, or more, about communication among the
programmers and between the programmers and the users as it is about
communication between the programmers and the “machine.” So if you have
to spend time saying, “this is functional code”, you’ve already lost
something, and introduced opportunities for mis-translation.

In short, I suspect that a more practical solution might be a language
that has object orientation and functional coding styles both baked in
right from the start. I’m not an expert on all the dozens of “obscure”
languages out there, so I can’t give any names. But I know they exist.

Go and look at Erlang. Massive real-world systems are built out of this,
with incredible reliability, using only functional programming and CSP.
It’s also very straightforward to pick up and use, and has a very
comprehensive standard library.

Remember also that functional languages allow all sorts of compile-time
optimisations which are impossible in Ruby, so there is the potential
for much higher performance. For example, OCaml generates code which is
reputedly only half the speed of the equivalent C code.

Did you mean “twice the speed?” Is OCaml faster or slower than C? And
why?


#9

M. Edward (Ed) Borasky wrote:

For example, OCaml generates code which is
reputedly only half the speed of the equivalent C code.

Did you mean “twice the speed?” Is OCaml faster or slower than C? And
why?

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.


#10

Pascal J. Bourguignon wrote:

[…]

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

[…]

I like how you sneaked in the parentheses. It’s a clever way to get
people accustomed to parens without actually using Lisp. A way-point
on the road to enlightenment. The too-many-parens complex is at the
same time a trivial psychological barrier and a roadblock to greater
understanding of the art of programming.

There comes a time when one finds oneself weary of evaling strings.
What’s needed is a language that can represent itself. To metaprogram
in the same language of the program–when the metalanguage is the
language–this is the weapon of a Lisper. Not as clumsy or random as
a string eval; an elegant weapon for a more civilized age.


#11

“Haris B.” removed_email_address@domain.invalid writes:

I’m starting to learn functional programming with Ruby.
I would like for someone to write me an example of finding the smallest
number in the list and a sorting algorithm.
I got the concept of map (collect), filter (select, detect and reject) and
reduce (inject) higher order functions but I don’t know how to compose
algorithms from them.
So please write me those two algorithms or some other simple ones with some
explanation.

You would have first to define the concept of list. Indeed, the other
answer may have you misled into believe that [1,2,3] was a list, but it
is not, it is an Array:

irb(main):477:0> [1,2,3].class
Array

(actually it’s a vector, Ruby has no multidimentional arrays like
Fortran or Lisp, or any other serrious programming language).

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

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

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

Oh, and by the way, instead of using Matzacred Lisp aka Ruby, you could
as well use directly the original, Lisp, and without dilation type away:

C/USER[7]> (defun smallest (list)
(labels ((smallest-element (list minimum)
(cond
((endp list) minimum)
((< minimum (first list)) (smallest-element
(rest list) minimum))
(t (smallest-element
(rest list) (first list))))))
(smallest-element (rest list) (first list))))
SMALLEST
C/USER[8]> (mapcar (function smallest) (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)))
(1 1 1 1 1 1)
C/USER[9]>

( Try out http://clisp.cons.org or http://sbcl.sourceforge.net
Have a look at http://www.gigamonkey.com/book )

Some links to this subject would be nice also.

http://www.stanford.edu/class/cs242/readings/backus.pdf

For purely functional programming you could learn Haskel, or a language
of the ML family, but Common Lisp is more useful since it’s a
multi-paradigm programming language: when you reach the limits of a
given paradigm, such as OO, or functional, you always have yet another
programming paradigm available in lisp (logical, declarative, you name
it).


#12

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)

Thanks

“Haris B.” removed_email_address@domain.invalid wrote in message
news:gk3m77$1ft$removed_email_address@domain.invalid…


#13

In Ruby everything is an object. That’s my favourite Ruby’s feature. And
you
showed that by just making one module you can have Lisp like functional
programming. So I’ll stick with Ruby.

“Pascal J. Bourguignon” removed_email_address@domain.invalid wrote in message
news:removed_email_address@domain.invalid…


#14

“Haris B.” removed_email_address@domain.invalid writes:

In Ruby everything is an object. That’s my favourite Ruby’s feature. And you
showed that by just making one module you can have Lisp like functional
programming. So I’ll stick with Ruby.

In Lisp too, everything is an object. But there are several kinds of
objects, and you can create your own kinds too (you can write new
meta-classes in CLOS).

C/USER[15]> (defclass automobile () ())
#1=#
C/USER[16]> (defvar car (make-instance 'automobile))
CAR
C/USER[17]> (class-of car)
#1=#
C/USER[18]> (class-of 1)
#1=#
C/USER[19]> (class-of “string”)
#1=#
C/USER[20]> (defstruct wheel)
WHEEL
C/USER[21]> (defclass automobile () ((wheels :accessor wheels :initform
(list (make-wheel) (make-wheel) (make-wheel) (make-wheel)))))
WARNING: DEFCLASS: Class AUTOMOBILE (or one of its ancestors) is being
redefined, instances are obsolete
#1=#<STANDARD-CLASS AUTOMOBILE :VERSION 1>
C/USER[22]> (wheels car)
(#S(WHEEL) #S(WHEEL) #S(WHEEL) #S(WHEEL))
C/USER[23]> (class-of (wheels car))
#1=#
C/USER[24]> (class-of (first (wheels car)))
#1=#
C/USER[25]>


#15

I meant, every expression is an object. Not sure that’s the case with
clisp.

“Pascal J. Bourguignon” removed_email_address@domain.invalid wrote in message
news:removed_email_address@domain.invalid…


#16

“Haris B.” removed_email_address@domain.invalid writes:

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


#17

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 ?

“Pascal J. Bourguignon” removed_email_address@domain.invalid wrote in message
news:removed_email_address@domain.invalid…


#18

Very interesting discussion, I love ruby and I love also haskell,
which I think made me a better programmer.

But does it really make sense to program in a functional way in ruby??

“Functional” code can be much more clean and elegant (in my opinion)
but what about performance issues???

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?


#19

Only the bits of a program that are appropriate for that.
I don’t know how can a Haskell programmer live without objects in larger
projects ? You loose track of what is where in the program.

“andrea” removed_email_address@domain.invalid wrote in message
news:removed_email_address@domain.invalid…


#20

On Jan 9, 2009, at 6:39 AM, andrea wrote:

But does it really make sense to program in a functional way in ruby??

That’s a great question.

Functional languages have been a hot topic lately and it seems with
that comes the need to make all languages functional. We’ve seen
plenty of that in Rubyland. Try to count the number of actor style
networking libraries (heavily inspired by Erlang I’m guessing) we have
now.

But you’ve nailed the key question: is this right for Ruby? My
feeling is probably not.

Don’t get me wrong. I like functional languages. I’ve learned a lot
from using them even just a little. I think there are projects where
I would prefer them.

However, Ruby is almost a flat opposite to them in many ways. Ruby
loves side effects and data is just about never locked down in Ruby.
That’s not bad, it’s just Ruby.

There may be times when we should adopt a functional approach here and
there. but if you are trying to avoid calling standard iterators in
Ruby because they aren’t functional, you’re trading Ruby advantages
away for heavy Ruby minuses. Performance is just one example of
this. If you are willing to make that trade, why not trade languages
and get back to the things you want being an advantage?

Of course, that’s all just my opinion. I mean no offense.

James Edward G. II