Asp Forum - functional programming

Haris Bogdanovic

1/8/2009 1:52:00 AM

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

86 Answers

Phlip

1/8/2009 5:12:00 AM

> I'm starting to learn functional programming with Ruby.

Wouldn't learning OO programming in Haskel be easier?

Haris Bogdanovic

1/8/2009 10:23:00 AM

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" <phlip2005@gmail.com> wrote in message
news:rSf9l.8378$8_3.226@flpi147.ffdc.sbc.com...
>> I'm starting to learn functional programming with Ruby.
> t
> Wouldn't learning OO programming in Haskel be easier?

Brian Candler

1/8/2009 11:22:00 AM

Haris Bogdanovic 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.
--
Posted via http://www.ruby-....

Harry Kakueki

1/8/2009 3:13:00 PM

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]

--
A Look into Japanese Ruby List in English
http://www.kakueki.com/ruby...

M. Edward (Ed) Borasky

1/8/2009 3:31:00 PM

Brian Candler wrote:
> Haris Bogdanovic 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.

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?

pjb

1/8/2009 4:07:00 PM

"M. Edward (Ed) Borasky" <znmeb@cesmail.net> 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.

--
__Pascal Bourguignon__

Haris Bogdanovic

1/8/2009 5:25:00 PM

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 Bogdanovic" <fbogdanovic@xnet.hr> wrote in message
news:gk3m77$1ft$1@gregory.bnet.hr...
> 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
>

Brian Candler

1/8/2009 10:00:00 PM

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.
--
Posted via http://www.ruby-....

pjb

1/8/2009 10:34:00 PM

"Haris Bogdanovic" <fbogdanovic@xnet.hr> 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://clis... or http://sbcl.sourc...
Have a look at http://www.gigamonke... )

> Some links to this subject would be nice also.

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

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).

--
__Pascal Bourguignon__

Mike Gold

1/9/2009 5:44:00 AM

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.

--
Posted via http://www.ruby-....

comp.lang.ruby

functional programming

Haris Bogdanovic

Phlip

Haris Bogdanovic

Brian Candler

Harry Kakueki

M. Edward (Ed) Borasky

pjb

Haris Bogdanovic

Brian Candler

pjb

Mike Gold

x Login to ForumsZone