Functional Programming and/or F# Conferences

There are some conferences I've noticed for year 2013. I will update this page regularly.

• A conference for Functional programmers, Chicago, USA, July 8 - 10, 2013
• Data Driven Functional Programming Workshop 2013, Rome, Italy, Jan 22, 2013
• The 18th ACM SIGPLAN International Conference on Functional Programming, Boston, USA, Sep 25 - 27, 2013
• Functional Program eXchange 2013, London, UK, March 15, 2013
• TFP 2013, Provo, Utah, USA, May 14 - 16, 2013
• Norwegian Developer Conference (NDC), Oslo, Norway, Jun 12 - 14, 2013
• Progressive F# Tutorials 2013, London, UK, Oct 31 - Nov 1, 2013
• Lambda Jam, May 16-17, 2013 at the Translink Centre for Service Excellence in the vibrant urban village of Kelvin Grove, just minutes from the Brisbane CBD
• POPL 2013: 40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Jan 23-25, Rome, Italy
• Strangeloop - September 18..20, St Louis
• ICFP - September 25..27, Boston
• GOTO Aarhus - September 30..October 2, Denmark
• GOTO Berlin - October 17..18, Germany
• Øredev - November 4..8, Sweden

Tweet to fsharp

Self Note: Get Replication status

The following script is to find the error within recent 30 min.


use distribution;
go
select
case
when COUNT(*)>0 then 'there are error for replication during the last half hour'
else 'no error found'
end
from msrepl_errors
where [time] > DATEADD(MINUTE, -30, GETDATE())
go

Azure Database Full

I blow up the 1G web-version database. After I delete, I still cannot insert record. :-(

After check the space used by using

select sum(reserved_page_count) * 8.0 / 1024 

from sys.dm_db_partition_stats

I find the space is still occupied. After run the rebuild index: alter index all on myTable rebuild, the space is reclaimed.

Debug F# Type Provider

Recently I am trying to use Type Provider (TP) in our production code. The first question I got is how to debug TP. The following is a way to debug it.

• download the type provider template or create your own project using the type provider API from codeplex.
• create a F# console Application in the solution
• from the F# console application add reference to the type provider project. Let us call this project ConsoleApplication2
• go to type provider project
• right click the project and open the project property
• find the "Debug" tab in the project property
• set the property like the image shown below:

•  Set the type provider project as start up project.

When the type provider project starts, it starts visual studio to open the Console application. You can put your break point in the type provider code. Once the debug is finished, the Visual Studio is closed and you are free to modify your code and rebuild the type provider code.

This approach does not requires to close and reopen the Visual Studio.

Tweet to fsharp

Self Note: SQL Azure + SSIS

I have been stuck with SQL Azure with SQL Server SSIS. My SSIS package needs to transfer data from SQL Server to SQL Azure. Everything seems working correctly until I set the "Required" field on the transaction. I get wired error indicate me that AcquireConnection failure is happening on the OLE DB during the validation period. The reason is very simple, SQL Server does not support DTC!

The SSIS package has to be executed on the SQL server. If the SSIS package is executed on a third server, the transaction is not supported and the AcquireConnection fails on OLE DB.

Remove F# snippet shortcut

I got email from Jack two weeks ago. He said F# code snippet is "too active". Yes, when you type, some shortcut keys will pop up and this is very annoying. The quick (and probably dirty) fix is to remove the shortcut key in the snippet file. The script file to remove the shortcut key is listed below. You can run it targeting to the snippet folder. Usually the folder is My Document \ < Visual Studio Folder > \Code Snippets\Visual F#.

If you are curious where is is the Shortcut key in the snippet file. Here is the screenshot.

The latest version snippets on the codeplex project does not have any shortcut key. You can download these snippets from codeplex project as well.

Although the shortcut key is removed, you still use Ctrl+K,X to show the snippet dialog.

 let (|ValidFolder|_|) folder =   
   match folder with  
   | _ when (File.GetAttributes(folder) &&& FileAttributes.Directory = FileAttributes.Directory) -> Some ValidFolder  
   | _ -> None  

 let removeShortcutTag (xmlFile:string) =   
   let doc = XDocument.Load xmlFile  
   doc.Descendants()  
   |> Seq.tryFind (fun decendent -> decendent.Name.LocalName = "Shortcut")  
   |> function  
     | Some node ->   
       File.SetAttributes (xmlFile, ~~~FileAttributes.ReadOnly  
                      &&& ~~~FileAttributes.Hidden  
                      &&& ~~~FileAttributes.System)  
       node.Value <- String.Empty  
       doc.Save(xmlFile)  
     | None -> ()  

 let processXMLFiles folder =   
   let xmlFiles = Directory.GetFiles(folder, "*.snippet")  
   xmlFiles  
   |> Seq.iter (fun xmlFile -> removeShortcutTag xmlFile)  

 let rec processXML folder =   
   match folder with  
   | ValidFolder ->   
     let subFolders = Directory.EnumerateDirectories(folder)  
     processXMLFiles folder  
     subFolders  
     |> Seq.iter processXML  
   | _ -> ()  

 processXML @"C:\MyCode\fsharpcodesnippet"  

Tweet to fsharp

F# Contract Position

Please contact recruiter directly. 

• ·         .Net (3.5 or 4.0) F# or C# programming expertise required
• In depth understanding of object-oriented analysis and design with a broad understanding of software design patterns preferred
• Understanding of IT in Financial Services background & domain knowledge –equity, fixed income, credit and derivatives products preferred
• ·         Experience in working in a fast paced, front-middle office or Risk/Margin preferred
• Experience in working with Middleware components such as Solace, Tibco RV, EMS preferred. XML, data binding and SOAP web services a plus

Self starter, passionate and enthusiastic attitude.

This is an Immediate need.

ONLY US CITIZENS PLEASE.... 

Srikanth Mandapati

HuMetis Technologies Inc

2 King Arthur Court

Lakeside W A-1

North Brunswick, NJ 08902

Phone: (609) 910-3391

Fax: (877) 451-5544

Web: http://www.humetis.com

Tweet to fsharp

F# Computational Expression Sample - File System + XML

Although I am not a PowerShell fan, I do like one feature of PowerShell. You can easily go from file system to registry. PowerShell treat file system and registry are same thing. I am afraid I have to face some Azure Virtual Machine management tasks in the future and I need to prepare in advance.

The following Computational Expression (CE) is a way to design an embedded language like PowerShell. I do not want to risk my computer's registry so I choose the File system and XML file. If you use cd "my path", it goes to either folder, file, or XML file's node or attribute.

the file system is like

and the XML file is

 // Learn more about F# at http://fsharp.net  
 // See the 'F# Tutorial' project for more help.  
 open System  
 open System  
 open System.Xml.Linq  
 type UnifiedType =   
   | Directory of string  
   | XMLFile of string  
   | Node of XElement * UnifiedType  
   | Attribute of string * XAttribute * UnifiedType  
 let rec getElement currentType (path:string list) =   
   match path with  
   | [] ->   
     currentType  
   | head::tail ->  
     let node =   
       match currentType with  
       | Directory(dir) ->   
         let dirs = System.IO.Directory.GetDirectories(dir)  
         match dirs |> Seq.tryFind (fun n -> n.EndsWith head) with  
         | Some n -> Directory(System.IO.Path.Combine(n))  
         | _ ->   
           let files = System.IO.Directory.GetFiles(dir, "*.xml")  
           match files |> Seq.tryFind (fun file ->   
                           String.Compare(System.IO.Path.GetFileName(file), head, true)=0) with  
           | Some n -> XMLFile(n)  
           | _ -> failwithf "cannot find %s" dir       
       | XMLFile (name) ->  
         let doc = XDocument.Load(name)  
         match (doc.Descendants()) |> Seq.tryFind (fun n -> n.Name.LocalName=head) with  
         | Some n -> Node(n, currentType)  
         | _ -> failwithf "cannot find %s" name    
       | Node(node, fn) ->  
         match (node.Descendants()) |> Seq.tryFind (fun n -> n.Name.LocalName=head) with  
         | Some n -> Node(n, fn)  
         | _ ->   
           match (node.Attributes()) |> Seq.tryFind(fun n -> n.Name.LocalName=head) with  
           | Some n -> Attribute(n.Name.LocalName, n, fn)  
           | _ -> failwithf "cannot find %s" node.Name.LocalName    
       | Attribute(name, value, fn) ->   
         failwithf "cannot find %s" name  
     getElement node tail  
 let setValue point (v:string) =   
   match point with  
   | Attribute (name, value, XMLFile(fn)) ->   
     value.Value <- v  
     value.Document.Save(fn)  
   | _ -> ()  
 type ExtendedFileSystem(startPoint:UnifiedType) =   
   member this.Yield( () ) = startPoint  
   [<CustomOperation("cd")>]  
   member this.GoDown(point:UnifiedType, id:string) =   
     getElement point [id]  
   [<CustomOperation("set")>]  
   member this.Set(point:UnifiedType, v:string) =   
     setValue point v  
     point  
   member this.Run(point:UnifiedType) =   
     fun () -> point  
 let fileSystem = ExtendedFileSystem(Directory(@".\"))  
 let fs =   
   fileSystem {  
     cd "Data"  
     cd "Xml"  
     cd "XmlFile1.xml"  
     cd "Xml"  
     cd "Data"  
     cd "A"  
     set "17" }  
 printfn "%A" ( fs() )  
 ignore <| System.Console.ReadKey()  

Tweet to fsharp

My First SSIS + Azure SQL Task

I need to do a task transferring data from SQL Server to Azure cloud. And this is really a good opportunity to refresh my SQL skill. One of my co-workers Haitao, who is really expert in SQL, demonstrates the SSIS. I love the way it processes data.

The core of the task is to transfer the data from SQL to SQL Azure. So the first task is to find the data flow task. I am a visual person, the colorful icon make it stands up and very easy to find out. Two yellow dots with a green arrow. :-)

Once you double click the Data Flow task on the design surface. You have to provide source and target. I had trouble using ADO.net when I set up the configuration file, so I use the OLE DB tasks whenever it is possible.

I need to create several tasks. Another lesson I learnt is the arrow between tasks are "precedence". If a node's proceeding tasks are all finished, this tasks can start right way. So you might see some tasks are executed simultaneously. 

Variable is what I I use exchange the statements from one task to the other task(s). I use select count(*) to check the existence of a table and result is put into a variable.

Be very careful, if it is ADO.net, the result uses index. For example, your SQL statement is select count(*) as AA from TableAA. OLE DB allow you use AA in the result set, but ADO.net only accept 0. This costs me 1 hour.. :(

Because the development environment is different from production environment, I have to make a configuration file. The configuration file can be created by right click anywhere on the design surface (not on any tasks). The right-click menu has the "Package configurations..." item. The connection string is what I wanted to put in the configuration file. The wizard does not put the password in the configuration file, so every time I made changes to the configuration file I had to manually add the password in the connection string.

After I successfully put the connection string into the configuration file, I tried to push the limit by dynamically generate SQL statement from the variable stored in the configuration file. The following screen shot should solve the problem pretty easy. 

Overall, I am very happy about the SSIS and its tooling support. Well, my stomach is really empty. I will blog next time.

SQL Azure Statements

I got a project to work on Azure database stuff. I will document the technical pain point(s) for this project and hopefully it help somebody and also as my own reference. (I am human, I do forget. ;-) )

• create database
  CREATE DATABASE MyDatabase (Edition='web')
  
  
• delete database
  DROP DATABASE MyDatabase
  
  
• alter database name
  ALTER DATABASE MyDatabase MODIFY NAME=NewName
  
  
• create index
  CREATE CLUSTERED INDEX index0
  ON TestTable ( < your column name >  )
  
  
• get used space
  SELECT sum(reserved_page_count) * 8.0 / 1024
  FROM sys.dm_db_partition_stats
  
  
• Check if the table is in database
  

   SELECT   
    CASE WHEN count(*) > 0 THEN 1 ELSE 0 END AS TableExist  
   FROM  
    sys.tables t  
   JOIN  
    sys.schemas s  
     ON t.schema_id = s.schema_id  
   WHERE  
    s.name = 'dbo' AND t.name = 'TestTable'  
  

  
  Another version using INFORMATION_SCHEMA
  

   SELECT   
    CASE WHEN count(*) > 0 THEN 1 ELSE 0 END   
    AS TableExists  
   FROM INFORMATION_SCHEMA.TABLES   
   WHERE TABLE_SCHEMA = 'dbo' AND TABLE_NAME = 'TestTable'  
  

F# on Algorithms - Wagner–Fischer algorithm

You never know when these algorithms can be used. This is the Levenshtein distance between two strings.　This sample code also demonstrates how to use Array2D in F#.

 let levenshteinDistance (str0:string) (str1:string) =   
   let s0 = str0.ToCharArray()  
   let s1 = str1.ToCharArray()  
   let result = Array2D.initBased -1 -1 (s0.Length+1) (s1.Length+1)  
           (fun i j ->   
             match i,j with  
             | (-1, -1) -> 0  
             | (_, -1) -> i+1  
             | (-1, _) -> j+1  
             | _ -> 0)  
   let min3 a b c = min a b |> (min c)  
   result   
   |> Array2D.iteri (fun i j v->   
             match i,j with  
             | (-1, -1)   
             | (_, -1)   
             | (-1, _) -> ()  
             | _ when s0.[i] = s1.[j] ->   
               result.[i,j] <- result.[i-1,j-1]  
             | _ ->   
               result.[i,j] <- 1 + min3 result.[i-1,j] result.[i,j-1] result.[i-1,j-1])  
   result  

Tweet to fsharp

F# / C# on Algorithms - Poisson Distribution

For this Poisson distribution variable generation. Which version you prefer? C# or F# version?

C# code

     public IEnumerable<int> Passion(int a, int n)  
     {  
       for (int i = 0; i < n; i++)  
       {  
         var L = Math.Exp(-a);  
         var k = 0;  
         var p = 1.0;  
         do  
         {  
           k++;  
           p *= rand.NextDouble();  
         }  
         while (p > L);  
         yield return k - 1;  
       }  
     }  

F# code

 open System  

 let rand = Random()  

 let passion (a:int) =   
   let getOneSample (a:int) =   
     let L = exp(float (-a) )  
     Seq.unfold (fun p ->   
             if p > L then Some (1, p*rand.NextDouble())  
             else None) 1.  
     |> Seq.length  
     |> fun len -> len - 1  
   Seq.initInfinite (fun _ -> getOneSample a)  

 passion 5  
 |> Seq.take 100  
 |> Seq.toList  

Tweet to fsharp

C# async and F# async

C# 5.0 proposed a new feature async/await. I am not totally surprised to know that C# borrow this idea from F#. Again, I am happy I can grab this idea quicker than C# background persons, just like what I did when learning LINQ.. :-)

One difference I noticed today is the sleep feature. If you do Thread.Sleep(xxx) in C#'s async function, it actually turns it into a synchronous call. But for F#, the function call is still an async function call. The following code is a sample. In the C# version, if you use the Thread.Sleep(5000), there will be a warning indicate the function call is actually a sync call. I would have to say C# feature is not perfect, because C# use static checking to decide if it is async or sync and totally delay the check to runtime.

F# version:

 let slowComputation = async {  
   System.Threading.Thread.Sleep(5000);  
   return "aa"  
   }  
 let f() = async {  
   let! v = slowComputation  
   printfn "result = %s" v  
   }  
 f()  
 |> Async.Start  
 printfn "about to wait..."  
 System.Threading.Thread.Sleep(15000);  
 printfn "Done"  

C# version:

 class Program  
   {  
     public async Task<string> SlowComputaton()  
     {  
       await Task.Delay(5000);  
       //Thread.Sleep(5000);  
       return "aaa";  
     }  
     public async void F()  
     {  
       var x = await SlowComputaton();  
       Console.WriteLine(x);  
     }  
     static void Main(string[] args)  
     {  
       var p = new Program();  
       p.F();  
       Console.WriteLine("about to wait...");  
       Thread.Sleep(15 * 1000);  
       Console.WriteLine("Done");  
     }  
   }  

Tweet to fsharp

F# on Mac

Today I decided to try F# on Mac computer. For a person working for Windows platform for years, it is not easy. Hopefully this post can help people with the same background. :)

• Go to http://fsharp.org/
• On the left side, you can find "F# On Mac"

• follow the installation instruction on the page to install MonoDevelop and Mono 3.0.

For me, the created project has a FSharp.Core.dll which cannot be resolved. I have to use the Mac OS Terminal to set up the GAC.

The Mac OS Terminal is under Application->Utilities.

then follow the instruction at http://functional-variations.net/crossplatform/installing-gac.aspx. After I execute

> sudo gacutil -i /usr/lib/fsharp/FSharp.Core.dll

I removed the FSharp.Core.dll from the reference. It actually works. :)

Now I can use Mac at home to program F#. What a nice day.. :)

Tweet to fsharp

Seq.unfold and recursive

Let me continue yesterday's post about using unfold to get rid of recursive function call.

First starts with a simple sample. the following code is a Fibonacci sequence generator.

 let seq = Seq.unfold (fun (i,j) -> Some(i, (i,i+j))) (1I, 1I)  
 seq |> Seq.take 100 |> Seq.toList  

The post-order traversal can also use unfold. The algorithm takes a list as state variable. If the head of the list is a simple value, yield it into the sequence. This operation decreases the list length by 1. If the head element is a subtree which is in (v, left, right) format, then replace the subtree element with three elements: left, right, and v. This operation increases the list length by 2 (= add 3 elements and remove 1 element). The code is listed below:

 type NodeType = int  

 type BinaryTree =   
   | Nil   
   | Node of NodeType * BinaryTree * BinaryTree  
 let tree = Node(5,  
         Node(42,   
            Node(3, Nil, Nil),  
            Node(2, Nil, Nil)),  
         Node(4,   
            Node(13,   
              Node(14, Nil, Nil),   
              Node(16, Nil, Nil)),  
            Node(12,   
              Node(15, Nil, Nil),   
              Node(21,   
                 Node(22, Nil, Nil),   
                 Nil))))  

 let postOrder state =  
   match state with   
   | [] -> None  
   | h::t ->  
     match h with  
     | Nil -> None  
     | Node(v, Nil, Nil) -> Some (Some v, t)  
     | Node(v, subTree, Nil)  
     | Node(v, Nil, subTree) -> Some (None, [subTree; Node(v, Nil, Nil)]@t)  
     | Node(v, l, r ) -> Some (None, [l; r; Node(v, Nil, Nil)] @t)  

 Seq.unfold postOrder [tree]  
 |> Seq.filter (fun n -> n.IsSome)  
 |> Seq.map (fun (Some(n)) -> n)  
 |> Seq.toList  

Tweet to fsharp

F# Seq.unfold for recursive structure

When I blogged the CSP style, I was wondering if there a better way to resolve this problem. Today I read through the Roman string generation snippet from F# snippet site. I suddenly realize the Seq.fold and Seq.unfold is something I was chasing for.

Let me first start with the Seq.unfold. The MSDN document only shows how to generate seq from a single point. I am trying to solve is to decompose a complex recursive structure and generate a sequence. A typical complex recursive structure is a tree.

The tree definition is shown like the following:

 type NodeType = int  
 type BinaryTree =   
   | Nil   
   | Node of NodeType * BinaryTree * BinaryTree  
 let tree = Node(5,  
         Node(42,   
            Node(3, Nil, Nil),  
            Node(2, Nil, Nil)),  
         Node(4,   
            Node(13,   
              Node(14, Nil, Nil),   
              Node(16, Nil, Nil)),  
            Node(12,   
              Node(15, Nil, Nil),   
              Node(21,   
                 Node(22, Nil, Nil),   
                 Nil))))  

• The first sample is to traverse the tree by layer. Do you notice where is the queue? :-)

 let f state =   
   match state with  
   | [] -> None  
   | h::t ->   
     match h with   
     | Nil -> None  
     | Node(v, Nil, Nil) -> Some (v, t)  
     | Node(v, subTree, Nil)  
     | Node(v, Nil, subTree) -> Some (v, t@[subTree])  
     | Node(v, l, r) -> Some (v, t@[l;r])  
 Seq.unfold generator2 [tree]  
 |> Seq.toList  

• The second sample is to change the code a little bit and see what can happen.. :-). You can run the code and see if the output is same to pre-order traversal.

 let generator2 state =   
   match state with  
   | [] -> None  
   | h::t ->   
     match h with   
     | Nil -> None  
     | Node(v, Nil, Nil) -> Some (v, t)  
     | Node(v, subTree, Nil)  
     | Node(v, Nil, subTree) -> Some (v, [subTree]@t)  
     | Node(v, l, r) -> Some (v, [l;r]@t)  
 Seq.unfold generator2 [tree]  
 |> Seq.toList  

It is getting late, I will come back to give more samples using the powerful Seq.fold and Seq.unfold.

Tweet to fsharp

Word Document Type Provider

I just published Word Document Type Provider on the F# 3.0 Sample Pack. The type provider uses the Office OpenXML SDK. In the template file "AA.docx", there are several MergeField fields in the document. The type provider reads these fields and show them as class property to the type.

The type provider type uses the following code to specify the template:

    type T = Samples.ShareInfo.TPTest.TPTestType<"AA.docx">

The AA.docx is treat as the template for this type provider. And the constructor get a file name which will be generated from the template.

    let t = T("MRXYZ.docx")

The above statement is to use the AA.docx template and generate the MRXYZ.docx file. The rest of the code is to set fields.

t.Person <- br="br" r.="r." xyz="xyz">t.ContactInformation <- br="br" com="com">t.MyCompany <- br="br" company="company">t.MyName <- br="br" lee="lee" ohn="ohn">t.NewProduct <- blockquote="blockquote" new="new" product="product">

Please make sure you do t.Close() to flush the content to the hard disk. The generated file MRXYZ.docx is located at the same folder as AA.docx. And the content of the file is

If you click "ABC Company"  or other fields, you can find the "Update Field" is disabled. You can use this approach to get the data from any data storage and export to Word Document.

For details, please download the source code from F# 3.0 Sample Pack. See the screenshot below:

According to a user's feedback, I added a new feature for this type provider. This feature will make sure all the fields are assigned a value. If there is a field missing, then the .Close function will generate an exception.

Tweet to fsharp

F# create Word document using OpenXML document

I always want to find a way to expose F# output to a nice UI and expose it directly to user. One of the nice UI is MS Word. I download OpenXML SDK from Microsoft and this helps me to write to Word and expose the result in very professional way. :)

I checked some online tutorial and found the C# always use Append to add new element. I converted C# code to F# and the generated document always shows nothing. After unzip the package, I should AppendChild. The following code is to use F# with OpenXML SDK to create a new Word document. I will explore more on this SDK next week.

 let createDoc(record) =   

   let name, content = record  
   let filePath = sprintf @".\%s.docx" name  
   let myDoc = WordprocessingDocument.Create(filePath, WordprocessingDocumentType.Document)
  
   // Add a new main document part.   
   let mainPart = myDoc.AddMainDocumentPart()  

   //Create Document tree for simple document.   
   mainPart.Document <- Document()  

   //Create Body (this element contains other elements that we want to include  
   let body = Body()  

   //Create paragraph  
   let createParagraph(text) =   
     let paragraph = Paragraph()  
     let run_paragraph = Run()  
     // we want to put that text into the output document  
     let text_paragraph = Text text  
     //Append elements appropriately.  
     ignore <| run_paragraph.AppendChild(text_paragraph)  
     ignore <| paragraph.AppendChild(run_paragraph)  
     paragraph  

   //create a paragraph with text  
   let paragraph0 =   
       createParagraph   
         (sprintf "Dear %s" name)  
   let paragraph1 =   
       createParagraph   
         (sprintf "Congratulations! %s" content)  

   [paragraph0; paragraph1]  
   |> List.iter (body.AppendChild>>ignore)  
   ignore <| mainPart.Document.AppendChild(body)  

   // Save changes to the main document part.   
   mainPart.Document.Save()  
   myDoc.Close()  

F# Memorization on Recursive Function

The memoization on recursive function is a topic I spent this Friday on.

Typical solution for memoization Fibonacci is listed below:

 let mem f =   
   let lookup = System.Collections.Generic.Dictionary<_,_>()  
   fun n ->  
     match lookup.TryGetValue n with  
     | true, v -> v  
     | _ ->  
       let a = f n  
       lookup.Add(n, a)  
       a  
 let rec fibonacci3 = mem (fun n ->   
               match n with   
               | 0 | 1 -> 1  
               | _ -> (fibonacci3 (n-1)) + (fibonacci3 (n-2)))  

Does this has a more general solution? Thanks to our team's Vlad, the following is a more general solution.

 let memoize wrapFunction =  
   let cache = System.Collections.Generic.Dictionary()  
   let rec f x =   
     match cache.TryGetValue x with  
     | true, v -> v  
     | false, _ ->  
       let v = wrapFunction f x  
       cache.[x] <- v  
       v  
   f  
 let fib =   
   memoize (  
     fun f x ->  
       if x < 2 then 1  
       else f(x - 1) + f(x - 2)  
   )  

Tweet to fsharp

F# ≥ C# (Pattern matching)

let us look at the following code first:

let a = 1       //nothing fancy

let b = 1, 2  // b is tuple now

The b is a tuple.  For a C# developer who wants to get the first and second element of the tuple, the obvious way is to call fst and snd function. Now we can use pattern matching

let c,d = b   // c = 1 and d = 2

now let us decompose a list

let l = [1;2;3;4]
match l with
| h::t -> ...     // h is 1 and t is [2;3;4]
| _ -> ...

match l with
| h0::h1::t -> ... // h0 is 1, h2 is 2, and t is [3;4]
| _ -> ...

Or you can decompose the list if the list length is known.

match l with
| [a;b;c;d] ->     //a=1, b=2, c=3, and d=4
| _ -> ...

I do not know how to use C# code to do the same thing. :)

Self Note: Debug Type Provider

With the type provider template, there can still be something odd and you need to debug it.

use the following settings to debug the type provider:

In the project property's "Debug" tab, set

Start external Program: C:\Program Files\Microsoft SDKs\F#\3.0\Framework\v4.0\fsc.exe
Start Options's Command line arguments:

-o:obj\Debug\ConsoleApplication1.exe -g --debug:full --noframework --define:DEBUG --define:TRACE --doc:bin\Debug\ConsoleApplication1.XML --optimize- --tailcalls- --platform:anycpu32bitpreferred -r:"C:\Program Files\Reference Assemblies\Microsoft\FSharp\3.0\Runtime\v4.0\FSharp.Core.dll" -r:"C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.5\mscorlib.dll" -r:"C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.5\System.Core.dll" -r:"C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.5\System.dll" -r:"C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.5\System.Numerics.dll" -r:"C:\ TypeProviderTemplate2\TypeProviderTemplate2\bin\Debug\TypeProviderTemplate2.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --validate-type-providers --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ "C:\Users\taliu\AppData\Local\Temp\.NETFramework,Version=v4.5.AssemblyAttributes.fs" Program.fs

and working directory as: C:\\TypeProviderTemplate2\ConsoleApplication1\ 

the working directory points to a ConsoleApplication which consume the generated type from the type provider.

F# on Algorithms - Neural Network

This is a neural network (NN) implementation with F#. For a long time, I wanted to learn how NN works. I remember I started my genetic algorithm thesis from a simple C# implementation. I still remember the code and how I used it finished my first assignment. :) When I graduated, the simple GA code became a 600K source code library and C# was the default way I talked to a computer.

I was hoping this can happen to F# as well. Many successful business, in my opinion,  are based on some simple ideas. Hopefully these algorithm can be one of these simple ideas and F# will become the default way in a successful business.

 namespace FSharp.NN 
 
 open System  
 open System.Collections.Generic 
 
 // NN factor which serve as the linkage between neurons
 type NeuralFactor(weight:float) =  
   member val HVector = 0. with get, set  
   member val Weight = weight with get, set  
   member this.SetWeightChange rate =   
     this.Weight <- this.Weight + this.HVector * rate  
   member this.Reset() =   
     this.HVector <- 0.  
   override this.ToString() =   
     sprintf "(HVector=%A, Weight=%A)" this.HVector this.Weight  

 type Map = Dictionary<Neuron, NeuralFactor>  
 
 // the neuron class
 and Neuron(bias) =   
   let sigmoid v = 1. / (1. + exp(-v))  
   member val Bias = NeuralFactor(bias) with get, set  
   member val Error = 0. with get, set  
   member val Input = Map() with get, set  
   member val LastError = 0. with get, set  
   member val Output = 0. with get, set  
   member this.Pulse() =   
     this.Output <- 0.  
     for item in this.Input do  
       this.Output <- this.Output + item.Key.Output * item.Value.Weight  
     this.Output <- this.Output + this.Bias.Weight  
     this.Output <- sigmoid this.Output  
   member this.ApplyLearning rate =   
     for value in this.Input.Values do  
       value.SetWeightChange rate  
     this.Bias.SetWeightChange rate  
   member this.Initialize() =   
     this.Input.Values  
     |> Seq.iter (fun value -> value.Reset())  
     this.Bias.Reset()  
   override this.ToString() =   
     sprintf "(Bias=%A, Error=%A, Output=%A)" this.Bias this.Error this.Output  

 // the neural layer which hosts one or more neurons
 type NeuralLayer() =   
   inherit List<Neuron>()  
   member this.Pulse() =   
     this  
     |> Seq.iter (fun n->n.Pulse())  
   member this.Apply rate =   
     this  
     |> Seq.iter (fun n->n.ApplyLearning rate)  
   member this.Initialize() =   
     this  
     |> Seq.iter (fun n->n.Initialize()) 
 
 // the neural network class
 type NeuralNet()=   
   let sigmoidDerivative v = v * ( 1. - v)  
   let rand = new Random()  
   member val LearningRate = 3.0 with get, set  
   member val InputLayer = NeuralLayer() with get, set  
   member val HiddenLayer = NeuralLayer() with get, set  
   member val OutputLayer = NeuralLayer() with get, set  
   member this.Initialize(inputNeuronCount, hiddenNeuronCount, outputNeuronCount) =   
     [1..inputNeuronCount] |> Seq.iter (fun _ -> this.InputLayer.Add(Neuron(0.)))  
     [1..outputNeuronCount] |> Seq.iter (fun _ -> this.OutputLayer.Add(Neuron(0.)))  
     [1..hiddenNeuronCount] |> Seq.iter (fun _ -> this.HiddenLayer.Add(Neuron(0.)))  
     for hiddenNode in this.HiddenLayer do  
       for inputNode in this.InputLayer do  
         hiddenNode.Input.Add(inputNode, new NeuralFactor(rand.NextDouble()))  
     for outputNode in this.OutputLayer do  
       for hiddenNode in this.HiddenLayer do  
         outputNode.Input.Add(hiddenNode, new NeuralFactor(rand.NextDouble()));  
   member this.Pulse() =   
     [ this.HiddenLayer; this.OutputLayer]   
     |> Seq.iter (fun n->n.Pulse())  
   member this.Apply() =   
     [ this.HiddenLayer; this.OutputLayer]   
     |> Seq.iter (fun n->n.Apply(this.LearningRate))  
   member this.InitializeLearning() =   
     [ this.HiddenLayer; this.OutputLayer]   
     |> Seq.iter (fun n->n.Initialize())  
   member this.Train(input: float list list, expected: float list list, iteration) =   
     [1..iteration]  
     |> Seq.iter (fun n ->   
             this.InitializeLearning()  
             for i=0 to input.Length-1 do  
               this.BackPropogation(input.[i], expected.[i])  
             this.Apply())  
   member this.Prepare(input) =   
     Seq.zip this.InputLayer input  
     |> Seq.iter (fun (a,b) -> a.Output <- b)  
   member this.Calculate() =   
     for outputNode in this.OutputLayer do  
       for hiddenNode in this.HiddenLayer do  
         outputNode.Input.[hiddenNode].HVector <- outputNode.Input.[hiddenNode].HVector + outputNode.Error * hiddenNode.Output;  
       outputNode.Bias.HVector <- outputNode.Bias.HVector + outputNode.Error * outputNode.Bias.Weight;  
     for hiddenNode in this.HiddenLayer do  
       for inputNode in this.InputLayer do  
         hiddenNode.Input.[inputNode].HVector <- hiddenNode.Input.[inputNode].HVector + hiddenNode.Error * inputNode.Output;  
       hiddenNode.Bias.HVector <- hiddenNode.Bias.HVector + hiddenNode.Error * hiddenNode.Bias.Weight;  
   member this.CalculateErrors desiredResults =   
     Seq.zip this.OutputLayer desiredResults  
     |> Seq.iter (fun (outputNode,v) ->   
             outputNode.Error <- (v - outputNode.Output) * sigmoidDerivative(outputNode.Output))  
     for hiddenNode in this.HiddenLayer do  
       hiddenNode.Error <-   
         this.OutputLayer   
         |> Seq.sumBy (fun outputNode -> (outputNode.Error * outputNode.Input.[hiddenNode].Weight) * sigmoidDerivative(hiddenNode.Output))  
   member this.BackPropogation(input, expected) =   
     this.Prepare(input)  
     this.Pulse()  
     this.CalculateErrors(expected)  
     this.Calculate()  
   member this.Inputs with get(i) = this.InputLayer.[i]  
   member this.Output with get(i) = this.OutputLayer.[i]  
   member this.GetOutputs() =   
     [ for output in this.OutputLayer do yield output.Output ]  
   member this.PrepareInput(input:float list) =   
     Seq.zip this.InputLayer input  
     |> Seq.iter (fun (a,b) -> a.Output <- b)  
 module Test =   
   let high = 0.99  
   let low = 0.01  
   let mid = 0.5  
   let rate = 3.4  
   let input = [ [high;high]; [low;high]; [high;low]; [low;low] ]  
   let output = [ [low]; [high]; [high]; [low] ]  
   let mutable cont = true  
   let net = NeuralNet()  
   net.Initialize(2,2,1)  
   let mutable count = 0  
   while cont do  
     count <- count + 1  
     net.Train(input, output, 5)  
     net.PrepareInput([low;low])  
     net.Pulse()  
     let [ll] = net.GetOutputs()  
     net.PrepareInput([high;low])  
     net.Pulse()  
     let [hl] = net.GetOutputs()  
     net.PrepareInput([low;high])  
     net.Pulse()  
     let [lh] = net.GetOutputs()  
     net.PrepareInput([high;high])  
     net.Pulse()  
     let [hh] = net.GetOutputs()  
     cont <- hh > (mid + low)/2.  
           || lh < (mid + high)/2.  
           || hl < (mid + low) /2.  
           || ll > (mid + high)/2.  
   net.PrepareInput([high;low])  
   let [v] = net.GetOutputs()  
   let result = v<0.5  

F# on Algorithm - String KMP Algorithm

the KMP algorithm is used for string matching. The algorithm is listed below.

 type List = System.Collections.Generic.List<int>  
 let kmp ( w: string ) =   
   let t = List([1..w.Length])  
   let mutable pos = 2  
   let mutable cnd = 0  
   t.[0] <- -1  
   t.[1] <- 0  
   while pos < w.Length do  
     if w.[pos-1] = w.[cnd] then  
       cnd <- cnd + 1  
       t.[pos] <- cnd  
       pos <- pos + 1  
     elif cnd>0 then  
       cnd <- t.[cnd]  
     else  
       t.[pos] <- 0  
       pos <- pos + 1  
   t |> List.ofSeq  
 type ResultType =   
   { mutable Result : int; mutable Found : bool }  
     with  
       member this.SetFound(b) = this.Found <- b  
       member this.SetResult(c)= this.Result<- c  
       static member InitialValue = { Result = -1; Found=false }  
 let kmpSearch (s:string) (w:string) : int =   
   let mutable m = 0  
   let mutable i = 0  
   let t = kmp w  
   let v = ResultType.InitialValue  
   while (i+m) < s.Length && not v.Found do  
     if w.[i] = s.[m+i] then  
       if i = w.Length - 1 then  
         v.SetFound true  
         v.SetResult m  
       i <- i + 1  
     else  
       m <- m + i + t.[i]  
       i <- if t.[i] > -1 then t.[i] else 0  
   v.Result  
 let s = "ABCABCDABABCDABCDABDE"  
 kmpSearch s "ABCDABD"  

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

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]