"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__