## 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. 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)
``````