F# Enum usage II

I want to take a quick note on the F# enum usage again. The supporting of the space and unique character in F# language and editor is a great feature can make your development work much more comfortable. I am in the Web API front these days.

One of the requirement is to provide options to end users. If an application only takes "excellent choice", "good option", "ok choice", and "bad and never go there" as options, I'd like to offload these values check to the type system instead of handling the error in my code.

If I can declare the enum like the following

type enum MyEnum =
    ``excellent choice`` = 0
    | ``good option`` = 1
    ....

After declaring the enum-as-string attribute on the attribute [JsonConverter(typeof(StringEnumConverter))], the output and input validation is solved in one shoot.

F# Enum's Usage

I have a web service project and I found my team constantly needs to convert enum to a string. The only conversion is adding space. It wastes lots of time and involves in reflection which slows down the run time performance.

Enum type is one of the favorite types in F#. C#'s enum type does not have the ability to define a value with space. Having an enum value with space is very important because this feature can save me lots of time to output enum value as string.

For example, if the enum value can be "Post Release", the ToString function can output a nice string and won't have to use attribute and reflection to do the job. C# does have the ability to have space in enum but it will need to use reflect and emit to generate the type. If you can use F#, the problem can be easily solved. Please check the following F# code:

namespace ClassLibrary1

type public EnumEng =
    Registration = 0
    | ``Under Review``=1
    | Approval = 2
    | Release = 3
    | ``Post Release`` = 4

type public EnumChn =
    注册 = 0
    | 审批 = 1
    | 批准 = 2
    | 发布 = 3
    | 发布后 = 4

type public EnumIndex =
    Reg = 0
    | Review = 1
    | Approval = 2
    | Release = 3
    | PostRelase = 4


module Test =
    let a = EnumEng.``Under Review``
    let b = EnumChn.审批

In the C# side, the intellisense won't display the enum value if it contains space. However, it will be displayed in debug mode. You can execute the following code and stop at the end of the function.

        static void Main(string[] args)
        {
            //get all string from enum0
            var strs = Enumerable.Range(0, 5)
                                 .Select(n => (ClassLibrary1.EnumEng)n)
                                 .Select(n => n.ToString())
                                 .ToList();

            // get all string from enum2
            var i = Enumerable.Range(0, 5)
                              .Select(n => (ClassLibrary1.EnumChn)n)
                              .Select(n => n.ToString())
                              .ToList();

            // parse string to enum
            var v = strs.Select(n => Enum.Parse(n))
                        .ToList();

            var x = ClassLibrary1.EnumIndex.PostRelase;

            var str = (ClassLibrary1.EnumChn)x;
        }

Both # and C# support non-English variable name, it will provide a way to localize the output as well. From the sample above, the EnumIndex is the type can used in C#/F# code. Once the value needs to be output as string, it can be convert to EnumEnglish (English string) or EnumChinese(Chinese string).

Is that convenient?

Tweet to fsharp

Reverse List Every K Node

Today I found an question and decide to use F# pattern match to give it a try.

The question is reverse a list every k node. For example, if the input list is [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] and k = 3, the output will be [3; 2; 1; 6; 5; 4; 9; 8; 7; 10].

When I use pattern matching, I always like recursive implementation.

 let arr = [1..10]  
 let rec reverse arr i =   
   let reverse2 arr =   
     arr |> List.rev  
   let rec getHeadTail arr i =   
     match i with  
     | 0 -> ([], arr)  
     | _ ->   
       match arr with   
       | [] -> ([], [])  
       | h::t ->   
         let (head,tail) = getHeadTail t (i-1)  
         ([h]@head, tail)  
   let headArr, tail = getHeadTail arr i  
   match tail with  
   | [] -> reverse2 headArr  
   | _ -> reverse2 headArr @ reverse tail i  
 reverse arr 6  

Tweet to fsharp

F# Code Snippet Updated

I updated the F# code snippet addon for Visual Studio 2013. I will upload the source code to fsharp.org/use/windows  once the source code is located. I really need to clean up the source code folder. There is no recompile is needed. The root cause for previous addon does not work on VS2013 is because this. The fix is simple, 

1. download the code snippet vsix file
2. rename it to .zip file because it is a zip file
3. find the vsixmanifest file
4. change InstallationTarget to

Tweet to fsharp

Why F# Type Provider?

F# type provider is a very nice feature. I was asked several times why I need type provider? Just because of the intellisense? I believe there should be something else. In the current team, I found people "hate" type, they prefer to use C# object all the times. Now I realize why type is so important and why type can increase code quality.

I want to use a simple approval process as a sample. For my understanding, a type defines the meaning of a area of memory and certain operations which can be executed on this type.

The sample is simple. You can have something to be approved by lead, manager, and director. If a lead approves, it returns a manager type. If manager disapproves, the process will stop and director won't know it. After director's approval, this process stops. The type provider can have three types, director's approve method returns nothing while other type's approve method return higher level type. Lead's approve method returns manager, and manager's approve method returns director.

I'd bet people can say I can use a single type to do the same job. A general class can be used to create three instances. The director instance's approve method can return NULL or any special value to stop the approval process. It can solve this problem provides you know director's approval will stop this process beforehand. A runtime error is not far away if this information is not known beforehand. The type provider uses type to provide the information. After you invoke director's approve method, which returns NULL, user will know immediately that this process is terminated.

I would say in this case, type is a way to move runtime check/error to compile time. The attached is the demo project for this approval process.

Tweet to fsharp

Use F# to Write PowerShell Snapin & Cmdlet

When I was in Minneapolis, I was thinking to use the F# to write PowerShell snapin and cmdlet. I got the feeling that this can speed our development speed.

Because I use Visual Studio 2012 and it generates the .NET 4 binary. So I need to install PowerShell 3.0 in order to use .NET 4.0. You can use $psversiontable to check the CLR runtime version, make sure it is a number equal or greater than 4.

 namespace Log4NetPsSnapIn  
 open System  
 open System.Management.Automation  
 open System.ComponentModel  
 [<RunInstaller(true)>]  
 type Log4NetSnapIn() =  
   inherit PSSnapIn()  
   override this.Name with get() = "aa"  
   override this.Vendor with get() = "bb"  
   override this.Description with get() = "dd"  
 [<Cmdlet(VerbsCommunications.Write, "Hi")>]  
 type WriteHelp() =   
   inherit Cmdlet()  
   override this.ProcessRecord() =   
     base.WriteObject("help");  

After compiling the above code, a DLL is generated. You have to use installutil.exe to add the snapin. The PowerShell snapin has Name = "aa", so you can use Add-PsSnapIn aa to load the DLL. You can also use installutil.exe /u to uninstall the snapin from your system. Make sure you open the cmd window or powershell window with administrator privilege.

• If you are running 64-bit version machine, make sure you use installUtil.exe under C:\Windows\Microsoft.net\Framework64\. 
• if your OS is 32-bit, you can use installUtil.exe under C:\Windows\Microsoft.net\Framework\

I like the way F# write PowerShell snapin. The code is concise and easier to understand.

Tweet to fsharp

Web Service using F#

this is a code to read file from local disk:

make sure it runs in the console application.

 open System  
 open System.IO   
 open System.ServiceModel  
 open System.ServiceModel.Web  
 let siteRoot = @"c:\myCode\"  
 [<ServiceContract>]  
 type MyContract() =  
   [<OperationContract>]  
   [<WebGet(UriTemplate="{file}")>]  
   member this.Get(file:string) : Stream =  
     printfn "Requested : '%s'" file  
     let path = Path.Combine(siteRoot, file)  
     let fileExists = File.Exists(path)  
     if fileExists then  
       WebOperationContext.Current.OutgoingResponse.ContentType <- "text/html"  
       let bytes = File.ReadAllBytes(path)  
       upcast new MemoryStream(bytes)  
     else  
       printfn "cannot find %s" path  
       upcast new MemoryStream()  
 let startAt address =  
   let host = new WebServiceHost(typeof<MyContract>, new Uri(address))  
   host.AddServiceEndpoint(typeof<MyContract>, new WebHttpBinding(), "")  
    |> ignore  
   host.Open()  
   host  
 let server = startAt "http://localhost:8081/"  
 printfn "started service..."  
 ignore <| System.Console.Read()  
 printfn "closing service..."  
 server.Close()  
 printfn "closed"  

Tweet to fsharp

Generated Type Provider and Code Generation

Let me finish the generated type provider and 100% move to Hadoop and big data area. In previous postings (1 and 2), I explained how to write generated type provider. The following are some pain points you might encountered when write your own generated type provider.

I currently use generated type provider to generate DLL. This is my main task. Currently, there is not so many document about generated type provider available, especially how to use F# expression to generate the binary. C# provides TypeBuilder to create types in a dynamic DLL, I use F# type provider to generate DLL.

• Define a field and property.

let providedField = ProvidedField("field", typeof<System.Func<string, string, string, obj, obj>>)  
let providedProperty = ProvidedProperty("Property", typeof<System.Func<string, string, string, obj, obj>>,   
                   GetterCode = (fun [this] -> Expr.FieldGet (this, providedField)),  
                   SetterCode = (fun [this;v] -> Expr.FieldSet(this, providedField, v)))  

• ProvidedField is a FieldInfo, ProvidedMethod is a MethodInfo, so everywhere you can to pass in standard .NET type, you can use Provided types.
• Constructor code needs to be modified to generate the your code. This piece needs to be added to the .fs. For generated code type provider, you do not have to return < @@ baseClass() @@ > in your constructor code.  

         let expr = pcinfo.GetInvokeCodeInternal true parameters  
         let locals = Dictionary<Quotations.Var,LocalBuilder>()  
         let expectedState = ExpectedStackState.Empty  
         emitExpr (ilg, locals, parameterVars) expectedState expr  

• NewDelegate has not been implemented yet. The bypass is to create a module with your function and pass in the function as expression.
• Specify the generated DLL path, where cfg is TypeProviderConfig. You can use any reflector tool to check the generated DLL.

 let providedAssembly = new ProvidedAssembly(System.IO.Path.Combine(cfg.ResolutionFolder, "GeneratedBinary.dll"))  

• Get C# lambda from F# function. 

Very simple, you can just do System.Fun(fun i -> i+1). 

Tweet to fsharp

Generated Type Provider Sample Published on Codeplex

Steffen asked me to provide a generated type provider sample to help understand the type provider API change and generated type provider itself. Changeset 19125 is made minutes ago to FSharp 3.0 Sample pack. The sample shows how to write a generated type provider.

In the solution, there are three projects:

1. GeneratedTypeProvider project is the one generating the type provider using the new API. The generated type provides only one function which return a constant value 1.
2. ConsoleApplication2, which is F# project, references to GeneratedTypeProvider project to expose the generated type from type provider
3. ConsoleApplication1 references to ConsoleApplication2 project to reference type from C# code.

The way I use generated type provider is to generated DLL. I will start several post to help interested user to explore this area more after my sinus infection is getting better.

Tweet to fsharp

Generated Type Provider API Changes

Erased type provider is not a new idea for many F# users, but the problem I am facing is to generate a really DLL which can be consumed by C# project. I use type provider as a code generation tool. If you are thinking about the same thing. Here is how to make your erased type provider to be a generated type provider. The MSDN document does not reflect the recent change in the type provider API's.

• you need to declare the ProvidedAssembly.

let providedAssembly = new ProvidedAssembly(System.IO.Path.ChangeExtension(System.IO.Path.GetTempFileName(), ".dll"))

• For the generated type, for example the regexTy, invoke the following statements (you have to remove the space between < and -)

    do 

        regexTy.IsErased < - false

        regexTy.SuppressRelocation < - false

        providedAssembly.AddTypes([regexTy])

Hopefully this can save you 10 minutes.. :-)

Tweet to fsharp

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

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

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

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