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" <pjb / informatimago.com> wrote in message 
news:87vdspbf7i.fsf / informatimago.com...
> "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 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).
>
> -- 
> __Pascal Bourguignon__