Merge Sort

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

FP
 PFL
  Examples
  Syntax

A not very imaginative pfl version of merge sort:

let rec
 eoi = -999,

 L =5::6::7::19::15::12::13::0::1::4::
    3::2::8::18::17::16::9::10::11::14::nil,
 LU=0::1::2::3::4::5::6::7::8::9::nil,
 LD=9::8::7::6::5::4::3::2::1::0::nil,  {data sets}

 listtochan = lambda L. lambda ch.
   if null L then ch!eoi -> stop
   else ch!hd L -> listtochan tl L ch,


 split = lambda inch. lambda out1. lambda out2.
   let rec {alternate elements from inch go to each output channel}
     flip = lambda out1. lambda out2.
       inch?x ->
       if x=eoi then out1!eoi -> stop || out2!eoi -> stop
       else out1!x -> flip out2 out1
   in flip out1 out2,


 merge = lambda in1. lambda in2. lambda outch.
   let rec
     copy = lambda inch.
       inch?x -> outch!x -> if x=eoi then stop else copy inch,

     f = lambda x. lambda y. {NB. x<>eoi or y<>eoi}
       if      x=eoi then outch!y -> copy in2
       else if y=eoi then outch!x -> copy in1
       else if x in1?z -> f z y
                   else outch!y -> in2?z -> f x z

   in in1?x -> in2?y -> f x y |
      in2?y -> in1?x -> f x y,


 msort = lambda inch. lambda outch.
   inch?x -> inch?y ->
   if y=eoi then outch!x -> outch!eoi -> stop
   else
   let a=chan, b=chan, c=chan, d=chan
   in a!x -> b!y -> split inch a b ||
      msort a c || msort b d ||
      merge c d outch,


 c=chan

in listtochan L c || msort c output

{\fB Parallel Merge Sort. \fP}

example c1993.

Note the use of a "special" value, eoi, to indicate the end of transmission on a channel.


window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

pfl...
|   choice
|| parallel
-> sequence
? input act
! output act
chan new channel

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 17-Apr-2014 22:44:12 EST.