Pages

Sunday, October 28, 2012

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  


Friday, October 26, 2012

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>  

Wednesday, October 24, 2012

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)

Sunday, October 21, 2012

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.

Sunday, October 14, 2012

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

F# on Algorithms - Find Triangle


find possible of elements in an array which can form a triangle.

let getTriangle (l:_ list) =
    let len = l.Length
    [
        for i=0 to len-1 do
            for j = i+1 to len-1 do
                for k=j+1 to len-1 do
                    if l.[i] + l.[j] > l.[k] &&
                       l.[j] + l.[k] > l.[i] &&
                       l.[k] + l.[i] > l.[j] then yield l.[i], l.[j], l.[k] ]

getTriangle [10; 21; 22; 100; 101; 200; 300]

Thursday, October 11, 2012

F# on Algorithms - Shuffle

Give a sequence, the following algorithm generates the randomly shuffle the sequence elements.


open System

let rand = Random()
let shuffleYateFisher (data:seq<_>) = 
    let result = System.Collections.Generic.List<_> ()
    data
    |> Seq.iter (fun n ->
                    let index = rand.Next(0, result.Count)
                    if index = result.Count then
                        result.Add(n)
                    else
                        result.Add(result.[index])
                        result.[index] <- n)

    result

let seq = seq { for i=0 to 10 do yield i }

for i=0 to 5 do
    let l = shuffleYateFisher seq
    l |> Seq.iter (printf "%A ")
    printfn ""

Wednesday, October 10, 2012

Sr. F# Developer needed


Please contact the recruiter directly.

 Sr. F# Developer

As a developer on the project, you will contribute to the design, implementation and overall quality of the web site. You will be partly an individual contributor and partly responsible for managing technical communications with other developers (who may be in remote locations) and ensure that their work gets incorporated into the product. Your individual development responsibilities will focus on server-side development (domain logic, data repository).
The candidate will have experience in the following areas:
Very strong background in .NET development using C# and/or F#.
Demonstrated experience with modern web application development using Windows Azure and ASP.NET (MVC strongly preferred).

Good understanding of HTML/HTML5, CSS, Javascript/JQuery, REST, and Silverlight to have informed discussion with other developers in the team.

If interested, please contact - -> Henry Man / Sr. Technical Recruiter / iSoftStone / henrym@isoftstone.com / 425.216.6300 ext 1136 


Saturday, October 6, 2012

F# on Algorithms - SubString


this function returns the consecutive string which has the same character. For example, the input "34445" will return "3", "444", and "5".

let str = "34445";
let getSub (str:string ref) =
    [
        let result = ref ""
        for c in (!str) do
            if !result = "" then
                result := string c
            elif (!result).EndsWith(string c) then
                result := !result + string c
            else
                yield !result
                result := string c
        yield !result]

getSub (ref str)

Thursday, October 4, 2012

F# on Algorithms - Longest Increasing Sequence (LIS)


The Longest Increasing Sequence (LIS). The approach is to use a DP array to hold the current LIS till this index. For example, if the value in DP.[10] is 3 means the LIS for array.[0..9] is 3. The DP.[i]'s value is updated only when the new value (DP.[j] + 1) is better than current value (DP.[i] < DP.[j] + 1) and the value is still increasing (array.[i] > array.[j]).

The code is listed below.

let list = [|10; 22; 9; 33; 21; 50; 41; 60; 80|]
let DP = Array.create list.Length 1

let findMax () =
    let mutable maxLength = 1
    for i=1 to list.Length - 1 do
        for j=i-1 downto 0 do
            if list.[i] > list.[j] &&
               DP.[i] < DP.[j] + 1 then
               DP.[i] <- DP.[j] + 1

        maxLength <- max maxLength DP.[i]

    maxLength

findMax()

Record and pattern matching

The record and pattern matching is a little tricky. Let us assume we have record type like the following.

    type MyRecord = { X : int list; Y : string }
    type MyRecord2 = { XX : int; YY : string; Z : int }


    let rr = { X = [100;200;300]; Y="aa" }
    let r0 = { X = [100;200;3]; Y="aa" }
    let r1 = { XX = 1; YY = "bb"; Z=9 }

    match r1 with
    | rr -> "a"
    | _ -> "b"

Execution result is "a". The record will match any record even the record is different types. 

The right way to crack the record open is to use:

    match r1 with
    | {YY=yValue} -> yValue
    | _ -> "b"

The yValue will be set to "bb".

Tuesday, October 2, 2012

F# on Algorithms - Get Combinations

The code below generates the combination of elements in a list. The number of elements in the combination is  provided by user in the "elementNeeded" variable.

let getCombination (list:int list) elementNeeded =
    let rec getCombinationFunction (list:int list) elementNeeded currentList =
        if elementNeeded = 0 then
            [ currentList ]
        else
            [ for n in list do
                let newList =
                    list
                    |> Seq.skipWhile (fun x -> x<>n)
                    |> Seq.skip 1
                    |> Seq.toList
                let newElementNeeded = elementNeeded - 1
                for l in getCombinationFunction newList newElementNeeded (currentList@[n]) do
                    yield l ]

    getCombinationFunction list elementNeeded []

getCombination [1;2;3;4] 3

F# on Algorithms - Josephus Problem

the description Josephus problem is listed here. The algorithm below listed the one survive at last and his number in the initial circle.


let rec josephusProblem n k =
    match n with
    | 1 -> 1
    | _ -> ((josephusProblem (n-1) k) + k - 1 ) % n + 1

josephusProblem 14 2

Monday, October 1, 2012

F# and C# optional parameter

F# optional parameter is defined like:

namespace MyClassNamespace

type MyClass() =
    member this.PrintValue(?value:int) =
        match value with
            | Some(n) -> printfn "value is %A" n
            | None -> printfn "sorry, no value"

the C# code invoke the F# code is like:

static void Main(string[] args)
{
    var myValue = new MyClassNamespace.MyClass();

    myValue.PrintValue(Microsoft.FSharp.Core.FSharpOption< int >.None);
    myValue.PrintValue(new Microsoft.FSharp.Core.FSharpOption< int >(1));
}

The C# side code is not that nice.

If you prefer the C# side does not need to reference to FSharp.Core.dll. The the Optional and DefaultParameterValue is your friend. :)

namespace MyClassNamespace

open System.Runtime.InteropServices

type MyClass() =
    member this.PrintValue(?value:int) =
        match value with
            | Some(n) -> printfn "value is %A" n
            | None -> printfn "sorry, no value"

    member this.PrintValue2([< Optional;DefaultParameterValue(0) >]value:int,
                            [< Optional;DefaultParameterValue(null) >]str:string) =        
        let defaultStr = if str = null then "null value" else str
        printfn "(%A, %A)" value defaultStr

The F# side invoke C# optional code is fairly easy.

public class CSharpClass
{
    public void MyMethod(int a = 11)
    {
        Console.WriteLine("a = {0}", a);
    }
}

let c = ConsoleApplication1.CSharpClass()

c.MyMethod()
c.MyMethod(100)
c.MyMethod(a=199)




F# on Algorithms - Graph library and Dijkstra

This post is a graph library. I have a C# version which is based on interfaces. The concrete class is just abstract class and all my algorithms are based on the C# interface. This approach makes algorithm code does not rely on concrete class. The C# design is nice except that I have to write both interface and class. Anything making me repeat the work drives me nuts.

I was trying to explore use the concrete type and F# type inference feature. I put a Data field without specify the type. I want F# to figure the type for me when I start use the library. By doing this, I was hoping get rid of the interface part in C# design.  So far so good. I can get rid of the interface and the code is more straightforward.

The sample code is in three parts:
  1. graph library
  2. DGML deserializer
  3. Dijkstra algorithm
 module DGMLGraph  
 open System  
 type Graph() =   
   let mutable nodes = []  
   let mutable edges = []  
   member this.Nodes with get() = nodes  
   member this.Edges with get() = edges  
   member this.CreateNode(id) =   
     match this.FindNode(id) with  
       | Some(n) -> None  
       | None ->   
         let node = Node(this, ID=id)  
         nodes <- nodes @ [ node ]  
         Some node  
   member this.CreateEdgeFromNode(from:Node, ``to``:Node, id) =   
     match this.FindEdge id with  
     | Some(edge) -> None  
     | None ->   
       let edge = Edge(this, from, ``to``, ID=id)  
       from.AddOutgoingEdge(edge)  
       ``to``.AddIncomingEdge(edge)  
       edges <- edges @ [edge]  
       Some edge  
   member this.CreateEdgeFromID(from, ``to``, id) =   
     let fromNode = this.FindNode(from)  
     let toNode = this.FindNode(``to``)  
     match fromNode, toNode with  
       | Some(n0), Some(n1) -> this.CreateEdgeFromNode(n0, n1, id)  
       | _ -> None  
   member this.FindNode(id) =   
     (nodes:Node list) |> Seq.tryFind(fun n -> n.ID = id)  
   member this.FindEdge(id) =   
     (edges:Edge list) |> Seq.tryFind(fun edge -> edge.ID = id)  
   member this.RemoveEdge(edge:Edge) =   
     (edge.FromNode:Node).RemoveOutgoingEdge(edge)  
     (edge.ToNode:Node).RemoveIncomingEdge(edge)  
     edges <- edges |> List.filter (fun n -> n<>edge)  
   member this.RemoveNode(node:Node) =   
     node.OutgoingEdges @ node.IncomingEdges |> List.iter this.RemoveEdge  
     nodes <- nodes |> List.filter (fun n -> n<>node)    
 and Node(g) =  
   let mutable incomingEdges = []  
   let mutable outgoingEdges = []   
   member val ID = Unchecked.defaultof<_> with get, set  
   member val Data = Unchecked.defaultof<_> with get, set  
   member this.IncomingEdges with get() = incomingEdges  
   member this.OutgoingEdges with get() = outgoingEdges  
   member this.AddIncomingEdge(edge:Edge) =   
     if edge.ToNode = this then  
       incomingEdges <- incomingEdges |> List.append [edge]  
   member this.AddOutgoingEdge(edge:Edge) =   
     if edge.FromNode = this then  
       outgoingEdges <- outgoingEdges |> List.append [edge]  
   member this.RemoveIncomingEdge(edge:Edge) =   
     incomingEdges <- incomingEdges |> List.filter (fun n -> n<>edge)  
   member this.RemoveOutgoingEdge(edge:Edge) =   
     outgoingEdges <- outgoingEdges |> List.filter (fun n -> n<> edge)  
   override this.ToString() =  
     sprintf "Node(%A)" this.ID  
 and Edge(g, from:Node, ``to``:Node) =   
   member val ID = Unchecked.defaultof<_> with get, set  
   member val Data = Unchecked.defaultof<_> with get, set  
   member this.FromNode with get() = from  
   member this.ToNode with get() = ``to``  
   override this.ToString() =   
     sprintf "Edge(%A, %A -> %A)" this.ID this.FromNode this.ToNode  
 open System.IO  
 open System.Xml.Linq  
 type DGMLReader(textReader:TextReader) = class  
   let doc = XDocument.Load(textReader:TextReader)  
   let graph = Graph()  
   do  
     let nodes = doc.Descendants() |> Seq.filter (fun n->n.Name.LocalName="Node")  
     let graphNodes =   
       nodes  
       |> Seq.map (fun node ->   
               let (Some graphNode) = graph.CreateNode(node.Attribute(XName.Get("Id")).Value)  
               graphNode.Data <- System.Int32.MaxValue)  
       |> Seq.toList  
     let edges = doc.Descendants() |> Seq.filter (fun n->n.Name.LocalName="Link")  
     edges  
     |> Seq.iteri (fun i edge->  
             let fromNode = edge.Attribute(XName.Get("Source")).Value  
             let toNode = edge.Attribute(XName.Get("Target")).Value  
             let (Some graphEdge) = graph.CreateEdgeFromID(fromNode, toNode, i)  
             graphEdge.Data <- Convert.ToInt32 ( edge.Attribute(XName.Get("Label")).Value )  
             ())  
   member this.Graph with get() = graph  
 end  
 type Path = System.Collections.Generic.List<Node>  
 let openList = Path()  
 let closedList = Path()  
 open System.Collections.Generic  
 open System.Linq  
 let getNeighbours (currentNode:Node) =   
   currentNode.OutgoingEdges  
   |> List.map (fun edge -> edge.ToNode)  
   |> List.filter (fun node -> not <| closedList.Contains(node))  
 let getCost (node:Node, currentNode:Node) =   
   let (Some edge) =   
     currentNode.OutgoingEdges  
     |> List.tryFind (fun edge -> edge.ToNode = node)  
   edge.Data  
 let ``Dijkstra's algorithm`` startPoint =   
   openList.Add(startPoint)  
   startPoint.Data <- 0  
   while openList.Count > 0 do  
     let currentNode = openList |> Seq.minBy (fun n-> n.Data)  
     let neighbours : Node list = getNeighbours currentNode  
     neighbours   
     |> List.iter (fun node ->   
             let distance = getCost (node, currentNode)  
             node.Data <- min (currentNode.Data + distance) node.Data)  
     openList.AddRange(neighbours)  
     ignore <| openList.Remove(currentNode)  
     closedList.Add(currentNode)