F# Continuation Style Programming

The more I do F#, the more I use recursive function. Consequently, I run into more stack overflow problem. :-(. The continuation CSP seems the only way I can use to avoid stack overflow. the following code is normal recursive version of function and CSP version. The key point is that the function won't return, so it does not create element on the call stack. The computation is delayed to continuation function so it does not need to keep the stack element any more.

 module FunctionReturnModule =   
   let l = [1..1000000]  
   let rec sum l =   
     match l with  
     | [] -> 0  
     | h::t -> h + sum t  
   sum l  

 module CPSModule =   
   let l = [1..1000000]  
   let rec sum l cont =   
     match l with  
     | [] -> cont 0  
     | h::t ->   
       let afterSum v =   
         cont (h+v)  
       sum t afterSum  
   sum l id  

Ok, the next problem is how to get the CSP version from the recursive version? Ok, here is the step I follow. Please keep in mind that some intermediate step codes won't compile.

Step 0

 module FunctionReturnModule =   
   let l = [1..1000000]  
   let rec sum l =   
     match l with  
     | [] -> 0  
     | h::t ->   
       let r = sum t  
       h + r  
   sum l  

Step1, introduce the continuation function.

 module FunctionReturnModule =   
   let l = [1..1000000]  
   let rec sum l cont =   
     match l with  
     | [] -> 0  
     | h::t ->   
       let r = sum t  
       cont (h + r)  
   sum l  

Step2: resolve the recursive function sum. The cont is move inside the afterSum. The afterSum function takes value (v) and pass it to cont (h+v).

 module CPSModule =   
   let l = [1..1000000]  
   let rec sum l cont =   
     match l with  
     | [] -> cont 0  
     | h::t ->   
       let afterSum v =   
         cont (h+v)  
       sum t afterSum  
   sum l id  

Well, let us use the same approach for tree traversal. The tree definition is listed below:

 type NodeType = int  
 type BinaryTree =  
   | Nil  
   | Node of NodeType * BinaryTree * BinaryTree  

the final result is

 module TreeModule =   
   let rec sum tree =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       let sumL = sum l  
       let sumR = sum r  
       v + sumL + sumR  
   sum deepTree  
 module TreeCSPModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> cont 0  
     | Node(v, l, r) ->  
       let afterLeft lValue =   
         let afterRight rValue =   
           cont (v+lValue+rValue)  
         sum r afterRight  
       sum l afterLeft  
   sum deepTree id  

Let us follow the same step.
Step0: introduce the continuation function first

 module TreeModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       let sumL = sum l  
       let sumR = sum r  
       cont (v + sumL + sumR)  
   sum deepTree  

Step1: resolve the sumR. Move the cont function to afterRight and pass afterRight to sum r as continuation function.

 module TreeModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       let sumL = sum l  
       // let sumR = sum r  
       let afterRight rValue =    
         cont (v + sumL + rValue)  
       sum r afterRight  
   sum deepTree  

Step2: resolve the sumL.

 module TreeModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       //let sumL = sum l  
       let afterLeft lValue =  
         let afterRight rValue =    
           cont (v + lValue + rValue)  
         sum r afterRight  
       sum l afterLeft  
   sum deepTree  

Ok, we can use the following code to test the code.

 let tree n =   
   let mutable subTree = Node(1, Nil, Nil)  
   for i=0 to n do  
     subTree <- Node(1, subTree, Nil)  
   subTree  
 let deepTree = tree 1000000  

Tweet to fsharp

Fix F# WinRT Application Verification Problem

When you use Visual Studio 2012 F# portable library, you can run into the application verification problem. Here is the solution for VS2012 installation.

(1)      Add the following code to your portable DLL

 [<assembly:System.Resources.NeutralResourcesLanguageAttribute("en-US")>]  
 do()  

(2)      Go to the project properties for your F# portable DLL and do the following:

a.         Click on Build and set “Configuration” to “Release”

b.         Enter “--staticlink:FSharp.Core” to the “Other flags”

c.         Click on “Build Events”

d.         Set “Run the post-build event” to “When the build updates the project output”

e.         Paste the following text into “Post-build event command line”

 if \"$(ConfigurationName)\"==\"Release\" (  
 "C:\Program Files (x86)\Microsoft SDKs\Windows\v8.0A\bin\NETFX 4.0 Tools\ildasm.exe" /linenum /nobar /out="$(TargetName).il" $(TargetFileName)  
 powershell "$lines = '}','} /*','} */'; $matchCount = 0; $clashCount = 0; filter GetOutput { if ($_ -eq ' } // end of method MatchFailureException::.ctor') { $lines[$matchCount++] } else { if ($_ -eq '  } // end of method Clash::.ctor') { $lines[$clashCount++] } else { $_ } } }; (Get-Content $(TargetName).il) | GetOutput | Set-Content $(TargetName).il"  
 "C:\Windows\Microsoft.NET\Framework\v4.0.30319\ilasm.exe" /dll /debug=opt /quiet $(TargetName).il  
 copy /y $(TargetName).dll ..\obj\Release\  
 )  

        Alternatively, just edit the .fsproj of your portable DLL project and add the following at the end of the first PropertyGroup:

 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">  
   <OtherFlags>--staticlink:FSharp.Core</OtherFlags>  
  </PropertyGroup>  
  <PropertyGroup>  
   <RunPostBuildEvent>OnOutputUpdated</RunPostBuildEvent>  
   <PostBuildEvent>if \"$(ConfigurationName)\"==\"Release\" (  
 "C:\Program Files (x86)\Microsoft SDKs\Windows\v8.0A\bin\NETFX 4.0 Tools\ildasm.exe" /linenum /nobar /out="$(TargetName).il" $(TargetFileName)  
 powershell "$lines = '}','} /*','} */'; $matchCount = 0; $clashCount = 0; filter GetOutput { if ($_ -eq ' } // end of method MatchFailureException::.ctor') { $lines[$matchCount++] } else { if ($_ -eq '  } // end of method Clash::.ctor') { $lines[$clashCount++] } else { $_ } } }; (Get-Content $(TargetName).il) | GetOutput | Set-Content $(TargetName).il"  
 "C:\Windows\Microsoft.NET\Framework\v4.0.30319\ilasm.exe" /dll /debug=opt /quiet $(TargetName).il  
 copy /y $(TargetName).* ..\..\obj\Release\  
 )  
   </PostBuildEvent>   
  </PropertyGroup>  

F# on Algorithm - Exponential Computation

find the power(2,3) = 8 seems not that difficult. The possible solution is to multiple 2 three times. The complex is O(n), where n is the second parameter. Is there a better way to do it? Yes, the code below (O(lg n)) is a sample.  The "I" suffix is to indicate the number is a F# bigint type.

This sample is more to demonstrate how the algorithm, rather than being used for real world application. F# has built-in application pown (3I, 2), which should be applied whenever is possible.

let rec power(x,n) =
    match n with
    | _ when n=0I ->
        if x=0I then
            failwith "invalid operation"
        else
            1I
    | _ when n=1I -> x
    | _ when n=2I -> x*x
    | _ ->
        if n%2I = 0I then
            let y = power(x, n/2I)
            y*y
        else
            let y = power(x, (n-1I)/2I)
            y*y*x
         
power(10I, 3I)

F# MakeFunction

For a long time, I cannot find a sample for F#'s MakeFunction sample. Now I got one.. :)

The following code redefine the printfn function.

   open System  
   type FSV = Microsoft.FSharp.Reflection.FSharpValue  
   type FST = Microsoft.FSharp.Reflection.FSharpType  
   let notImpl<'T> : 'T = raise (NotImplementedException())  
   let printfn (fmt : Printf.TextWriterFormat<'T>) : 'T =   
     let rec chain (ty : System.Type) : obj =   
       if FST.IsFunction ty then  
         let argTy, retTy = FST.GetFunctionElements ty  
         FSV.MakeFunction(ty, (fun _ -> chain retTy))  
       else  
         if ty.IsValueType then Activator.CreateInstance(ty) else null  
     chain typeof<'T> :?> 'T  
   let printf fmt = printfn fmt  

F# on Algorithms - Reservior sampling

The reservior sampling is something related to processing large amount of data. This algorithm is also related to the shuffle algorithm. Its definition on wiki is here. In this sample, I also want to demonstrate the power of active pattern. The algorithm is trying to get N element from a large data set, the data set is so big and it is not possible to hold it in the memory. Let us treat the big data as a Seq.

the algorithm first try to fill the result set whose size is resultSize. Once successfully get resultSize elements, the rest element is selected randomly based on a uniform distribution from 0 to current. If the generated random number is in the range of [0, resultSize), replace the result set's element with the new element. So the new element has the probability resultSize/currentIndex.

 let rand = System.Random()  
 let (|InReserviorRange|_|) i resultSize =  
   if i < resultSize then  
     Some()  
   else  
     None  
 type ResultList<'a> = System.Collections.Generic.List<'a>  
 let result = ResultList<_>()  
 let reserviorSampling data resultSize =   
   let (|InReserviorRange|_|) i = (|InReserviorRange|_|) i resultSize    
   data  
   |> Seq.iteri (fun index n ->  
           match index with  
           | InReserviorRange->  
             result.Add(n)  
           | _ ->    
             let newIndex = rand.Next(index)             
             match newIndex with  
             | InReserviorRange ->   
               result.[newIndex] <- n  
             | _ -> ())  
 let seq = seq { for i=0 to 100 do yield i }  
 reserviorSampling seq 5  
 result |> Seq.iter (printfn "%A")  

Note: For a real world application, you have to rewrite the random number generator for number bigger than int32's max value.

In this code, I also want to show the power of active pattern. The InReserviorRange is an active pattern. It make sure the i
I had had made some bugs because ignore the ELSE scenario or think ELSE scenario is not necessary. The match + active pattern can prevent this kind of error. The active pattern just another way to define a function, no much extra cost than define a function. And it gives extra check with match and improves the code readability.

The active pattern can also use the higher order function idea, look at the second InReserviorRange pattern, that is the syntax how to define second pattern based on current pattern.

F# on Algorithms - Kadane algorithm

this algorithm is to find  the maximum contiguous subsequence in a one-dimensional sequence.

let kadane data =
    let mutable maxV, max_currentPoint = 0, 0
    for i in data do
        max_currentPoint <- max 0 (max_currentPoint + i)
        maxV <- max maxV max_currentPoint

    maxV

kadane [-2; -3; 4; -1; -2; 1; 5; -3; ]

F# on Algorithms - Build BST from Pre-order

I guess everyone familiar with building a tree from pre-order and in-order. But for BST, we only need a pre-order. 

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let rec buildBSTfromPreOrder (l:NodeType list) =
    match l with
    | [] -> Nil
    | [a] -> Node(a, Nil, Nil)
    | h::t ->
        let smaller =
                   t
                   |> Seq.takeWhile (fun n -> n < h)
                   |> Seq.toList
        let bigger =
                   t
                   |> Seq.skipWhile (fun n -> n < h)
                   |> Seq.toList
        Node(h, buildBSTfromPreOrder(smaller), buildBSTfromPreOrder(bigger))

let input = [10; 5; 1; 7; 40; 50]
buildBSTfromPreOrder input