From: Haris Bogdanovic <fbogdanovic@...>
Date: 2009-01-09T22:09:38+09:00
Subject: Re: functional programming

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" <pjb@informatimago.com> wrote in message 
news:87d4ewbrgz.fsf@informatimago.com...
> "Haris Bogdanovic" <fbogdanovic@xnet.hr> 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
>
>
> -- 
> __Pascal Bourguignon__