Paul Abraham

Uplifting experience to see concepts the software engineering  which is more than bunch of   “if thens  and while loop”. Thank you  Brain  and Charles

Thank you for the lecture and I have already bought the book to follow the lectures

F#:

#light

open System

open System.Threading

open Microsoft.FSharp.Control

 

// create a random list

let maxSize=4

let rand = new Random()

let list=[ for i in 1..maxSize do yield rand.Next(100*maxSize)]

 

printfn "%A" list

 

//1. Simple version

// 'a list -> 'a list

let rec simpleQuickSort(inL)=

    match inL with

    | []->[]

    | h::t->List.partition(fun e->e<=h) t|>fun(l,r)->simpleQuickSort(l)@ h::simpleQuickSort(r)

   

   

let sL=simpleQuickSort(list)

printfn "%A" sL

Erlang :

-module(parallelquicksort).

-export([gen_randomlist/2,simplesort/1]).

 

 

%% generates a list of random numbers

 

gen_randomlist(N,MaxNumber)->

   lists:map(fun(_)->random:uniform(MaxNumber) end,lists:seq(1,N)).

  

%% simple version

simplesort([])->[];

simplesort([H|Tail])->simplesort([X||X<-Tail,X<H])

                      ++++

                      simplesort([X||X<-Tail,X>=H]).

F# :

////2 ASynchronous version

// create asynchronous task for list partition

//'a list * ('a -> bool) -> Async<'a list>

// f is function for partition

let asyncPartition(l,f)= async{ return l|>List.filter(f)}

                           

                                                                   

let rec asyncQuickSort(inL)=

       match inL with

         |[]->[]

         |h::t-> let asynTasks=[asyncPartition(t,fun(x)->x<=h);asyncPartition(t,fun(x)->x>h)]

       let asynResult=Async.Run(Async.Parallel asynTasks)// execute

1.        asyncQuickSort(asynResult.[0])@h::asyncQuickSort(asynResult.[1])//join                                 

 

let asynSortedList=asyncQuickSort(list)

printfn "%A" asynSortedList

F#:

//3. Message Passing Style Version

type MsgListPartition = | GetList of int list*(int->bool)*AsyncReplyChannel<int list>

                        | Stop

             

type PartitionServer(srvName:string)=

     let receiver =  MailboxProcessor<MsgListPartition>.Start(fun inbox->

              let rec loop() =

                    async {

                            let! msg=inbox.Receive()

                            match msg with

                            |Stop->return()

                            |GetList(l,f,rep)-> let p =l|>List.filter(f)

                                                rep.Reply(p)

                                                return! loop()

 

                          }

              loop())

              

     member o.Stop() = receiver.Post(Stop)

     member o.GetList(l,f)=receiver.AsyncPostAndReply(fun aS->GetList(l,f,aS))

    

 

let s1Server = new PartitionServer("Server-l")

let s2Server = new PartitionServer("Server-r")

let rec mpsQuickSort(inL)=

        match inL with

         |[]->[]

         |h::t-> let asynL=[s1Server.GetList(t,fun(x)->x<=h);s2Server.GetList(t,fun(x)->x>h)]

        let asynResult=Async.Run(Async.Parallel asynL)

        mpsQuickSort(asynResult.[0])@h::mpsQuickSort(asynResult.[1])

 

let z=mpsQuickSort(list)

printfn "%A" z

 

Erlang:

%% parallelversion

left_sort()->

  receive

    {From,Pivot,List} -> From ! {self(),[X||X<-List,X<Pivot]}

  end.

 

right_sort()->

  receive

    {From,Pivot,List} -> From ! {self(),[X||X<-List,X>=Pivot]}

  end.

 

gather(SPId) ->

    receive

                        {SPId, Ret} -> Ret

    end.

 

psort([])->[];

psort()->;

psort([H|Tail])-> [LPId,RPId]=[spawn(fun left_sort/0),spawn(fun right_sort/0)],

                  LPId! RPId! {self(),H,Tail},

                  psort(gather(LPId))++++psort(gather(RPId)).

                 

                 

 

 

// F# code

#light
open System
open System.Text

// State Monad

//  label a binary tree to demonstrate state-monad
//  implement non-monadically and monadically

type Tree<'a> =
| Leaf of string*'a
| Branch of Tree<'a>*Tree<'a>  


// prints binary tree
// val printTree : Tree<'a> -> unit
let printTree(a)=
    let rec print(a,level)=
            let emptyString =new String(' ',level*2)
            printfn "%s" emptyString
            match a with
            |Leaf (sym,e)-> Console.Write(emptyString)
                            Console.Write("Leaf: "+sym+" ")
                            Console.Write(e.ToString())
                            Console.WriteLine()  
            |Branch (left,right) -> Console.Write(emptyString)
                                    Console.WriteLine("Branch:");
                                    print(left,level+1)
                                    print(right,level+1)
    print(a,2)
    
//non-monad version
let rec labelTreeNM(t,s) =
         match t with
         |Leaf(sym,_)-> let l=Leaf(sym,s)
                        (s+1,l)
         |Branch(left,right)-> let(sL,nLeft)=labelTreeNM(left,s)
                               let(sR,nRight)=labelTreeNM(right,sL)
                               (sR+1,Branch(nLeft,nRight))                 

let demoTree=Branch(Leaf("A",0),Branch(Leaf("B",0),Branch(Leaf("C",0),Leaf("D",0))))

let (_,demoTreeNM)=labelTreeNM(demoTree,0)
//printTree(demoTreeNM)

// monad version
type State<'s,'a> = State of ('s ->'s*'a)

////type StateMonad =
//  class
//    new : unit -> StateMonad
//    static member
//      Bind : sm:State<'a,'b> * f:('b -> State<'a,'c>) -> State<'a,'c>
//    static member Return : a:'a -> State<'b,'a>
//  end

type StateMonad() =
        static member Return(a) = State (fun s -> s, a)
        static member Bind(sm,f) =
           State (fun s0 ->let (s1,a1)= match sm with
                                        | State h -> h s0
                           let (s2,a2)= match f a1 with
                                        | State h->h s1
                           (s2,a2))                                                                      
                                                                       

// succinct functors for state monad

//val ( >>= ) : State<'a,'b> -> ('b -> State<'a,'c>) -> State<'a,'c>
let (>>=)m  f = StateMonad.Bind( m, f)
//val Return : 'a -> State<'b,'a>
let Return =StateMonad.Return


// Tree<'a> -> State<int,Tree<int>>
let rec mkMonad(t)
          =match t with
           |Leaf(sym,_) -> State(fun s->((s+1),Leaf(sym,s)))
           |Branch(oldL,oldR)-> mkMonad(oldL)>>=
                                  (fun newL->mkMonad(oldR) >>=
                                              fun newR->Return(Branch(newL,newR)))

// monad version
let monadLabel(t,s)= let(nS,nT)=  match mkMonad(t) with
                                  | State f-> f(s)
                     nT

let mTree=monadLabel(demoTree,0)
printTree(mTree)