Friday, November 30, 2012

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'  
    

Wednesday, November 28, 2012

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  

Wednesday, November 21, 2012

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  

Tuesday, November 20, 2012

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");  
     }  
   }  

Saturday, November 17, 2012

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.. :)

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  

Friday, November 16, 2012

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.



Tuesday, November 13, 2012

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.

Sunday, November 11, 2012

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()  

Saturday, November 10, 2012

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)  
   )  


Friday, November 9, 2012

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. :)


Tuesday, November 6, 2012

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.


Sunday, November 4, 2012

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  

Friday, November 2, 2012

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"