"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://clisp.cons.org or http://sbcl.sourceforge.net
Have a look at gigamonkey.com - gigamonkey Resources and Information. )
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).
···
--
__Pascal Bourguignon__
