Merge Sort

LA home
 FP,  λ
 Logic,  π


A not very imaginative pfl version of merge sort:

let rec
 eoi = -999,

 L =5::6::7::19::15::12::13::0::1::4::
 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
   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,


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

free op. sys.
free office suite,
ver 3.4+

~ free photoshop
web browser
like it says!

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

© L. Allison   (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 Wednesday, 30-Jul-2014 04:51:28 EST.