From: William James <w_a_x_man@...>
Date: 2009-01-12T10:14:25+09:00
Subject: Re: functional programming

Haris Bogdanovic wrote:

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


Ruby:

def merge list1, list2, &less
  return list1 + list2  if list1.empty? or list2.empty?
  less = ( less or proc{|a,b| a < b} )
  less[ list1[0], list2[0] ] and
    [ list1[0] ] + merge( list1[1..-1], list2, &less ) or
    [ list2[0] ] + merge( list1, list2[1..-1], &less )
end

p merge( [1,3,5], [2,4,6] )
p merge( [-1,-3,-5], [-2,-4,-6] ){|a,b| a > b}

def merge_sort list
  return list  if list.size < 2
  half = list.size / 2
  merge merge_sort( list[0...half] ), merge_sort( list[half..-1] )
end

p merge_sort( [9,2,8,5,6,3] )
5.times{|i| p merge_sort( (0..i).to_a.reverse ) }