open System

// type alias for IEnumerable
type IE = System.Collections.IEnumerable

// define record type
type MyRecord = { X : int; Y : string }

// define DU type
type MyDU =
    | Case1 of string
    | Case2 of int

// define a class
type MyClass() =
    member val MyProperty = 0 with get, set
    member val MyProperty2 = String.Empty with get, set
    override this.ToString() =
        sprintf "(%A, %A)" this.MyProperty this.MyProperty2

type DataSource() =
    let random = Random()

    // define data sequence
    let seq0 = [2; 3; 4; 5; 10; 10; 11; 13; 14; 19]
    let seq1 = seq0 |> Seq.map (fun x -> float x)
    let seq2 = seq0 |> Seq.map (fun x -> bigint x)
    let seqTuple = Seq.zip seq0 (seq0 |> Seq.map (sprintf "%A"))
    let seqRecord = seqTuple |> Seq.map (fun (i, s) -> {X = i; Y = s})
    let seqDU = seqTuple |> Seq.map (fun (i, s) -> Case2(i))
    let seqDU2 = seqTuple |> Seq.map (fun (i, s) -> Case1(s))
    let seqClass = seqTuple |> Seq.map (fun (i, s) -> MyClass(MyProperty = i, MyProperty2
= s))

    // define data list; this list is an F# list type
    let list0 = seq0 |> Seq.toList
    let list2 = seq2 |> Seq.toList
    let listTuple = seqTuple |> Seq.toList
    let listRecord = seqRecord |> Seq.toList
    let listDU = seqDU |> Seq.toList
    let listClass = seqClass |> Seq.toList

    let toString x =
        let seq =
            x
            |> Seq.toList
            |> List.map (fun n -> sprintf "%A" n)
        String.Join(",", seq)

    member this.Seqs : list<IE> =
            [ seq0
              seq1
              seq2
              seqTuple
              seqRecord
              seqDU
              seqDU2
              seqClass ]

    member this.Lists : list<IE> =
            [ list0
              list2
              listTuple
              listRecord
              listDU
              listClass ]

    member this.TestSeq() =
        let seq0 = seq0 |> Seq.sort |> toString
        let seq1 = seq1 |> Seq.sort |> toString
        let seq2= seq2 |> Seq.sort |> toString

        let seqTuple=seqTuple |> Seq.sort |> toString
        let seqRecord=seqRecord |> Seq.sort |> toString
        let seqDU=seqDU |> Seq.sort |> toString
        let seqDU2=seqDU2 |> Seq.sort |> toString
        let r =
            [ seq0
              seq1
              seq2
              seqTuple
              seqRecord
              seqDU
              seqDU2 ]
        r
        |> Array.ofList

    member this.TestList() =
        let list0 =list0 |> Seq.sort  |> toString
        let list2 =list2 |> Seq.sort |> toString
        let listTuple=listTuple|> Seq.sort |> toString
        let listRecord=listRecord|> Seq.sort |> toString
        let listDU=listDU|> Seq.sort |> toString
        let r =
            [ list0
              list2
              listTuple
              listRecord
              listDU ]
        r
        |> Array.ofList

    member this.TestSeqSortBy_Tuple() =
        let r = seqTuple |> Seq.sortBy (fun (i, s) -> i) |> toString
        r

    member this.TestSeqSortBy_Record() =
        let r = seqRecord |> Seq.sortBy (fun n -> n.X) |> toString
        r

    member this.TestSeqSortBy_DU() =
        let r = seqDU |> Seq.sortBy (fun (Case2(n)) -> n) |> toString
        r

    member this.TestSeqSortBy_Class() =
        let r = seqClass |> Seq.sortBy (fun n -> n.MyProperty2) |> toString
        r

Console application code to test the portable library

let data = DataSource()
printfn "test seq"
let join (x:'T array) = System.String.Join("
", x)

[ join (data.TestSeq());
join (data.TestList());
data.TestSeqSortBy_Class();
data.TestSeqSortBy_DU();
data.TestSeqSortBy_Record();
data.TestSeqSortBy_Tuple() ]
|> Seq.iter (printfn "%A")

Execution result from console testing

test seq
"2,3,4,5,10,10,11,13,14,19
2.0,3.0,4.0,5.0,10.0,10.0,11.0,13.0,14.0,19.0
2,3,4,5,10,10,11,13,14,19
(2, "2"),(3, "3"),(4, "4"),(5, "5"),(10, "10"),(10, "10"),(11, "11"),(13, "13"),(14,
"14"),(19,
"19")
{X = 2;
 Y = "2";},{X = 3;
 Y = "3";},{X = 4;
 Y = "4";},{X = 5;
 Y = "5";},{X = 10;
 Y = "10";},{X = 10;
 Y = "10";},{X = 11;
 Y = "11";},{X = 13;
 Y = "13";},{X = 14;
 Y = "14";},{X = 19;
 Y = "19";}
Case2 2,Case2 3,Case2 4,Case2 5,Case2 10,Case2 10,Case2 11,Case2 13,Case2 14,Case2 19
Case1 "10",Case1 "10",Case1 "11",Case1 "13",Case1 "14",Case1 "19",Case1 "2",Case1
"3",Case1
"4",Case1 "5""
"2,3,4,5,10,10,11,13,14,19
2,3,4,5,10,10,11,13,14,19
(2, "2"),(3, "3"),(4, "4"),(5, "5"),(10, "10"),(10, "10"),(11, "11"),(13, "13"),(14,
"14"),(19,
"19")
{X = 2;
 Y = "2";},{X = 3;
 Y = "3";},{X = 4;
 Y = "4";},{X = 5;
 Y = "5";},{X = 10;
 Y = "10";},{X = 10;
 Y = "10";},{X = 11;
 Y = "11";},{X = 13;
 Y = "13";},{X = 14;
 Y = "14";},{X = 19;
 Y = "19";}
Case2 2,Case2 3,Case2 4,Case2 5,Case2 10,Case2 10,Case2 11,Case2 13,Case2 14,Case2 19"
"(10, "10"),(10, "10"),(11, "11"),(13, "13"),(14, "14"),(19, "19"),(2, "2"),(3, "3"),(4,
"4"),(5,
"5")"
"Case2 2,Case2 3,Case2 4,Case2 5,Case2 10,Case2 10,Case2 11,Case2 13,Case2 14,Case2 19"
"{X = 2;
 Y = "2";},{X = 3;
 Y = "3";},{X = 4;
 Y = "4";},{X = 5;
 Y = "5";},{X = 10;
 Y = "10";},{X = 10;
 Y = "10";},{X = 11;
 Y = "11";},{X = 13;
 Y = "13";},{X = 14;
 Y = "14";},{X = 19;
 Y = "19";}"
"(2, "2"),(3, "3"),(4, "4"),(5, "5"),(10, "10"),(10, "10"),(11, "11"),(13, "13"),(14,
"14"),(19,
"19")"

let rec quickSort (data:int list) =
    match data with
    | [] -> []
    | [a] -> [a]
    | head::tail ->
        let l0 =
            tail
            |> List.filter ((<=) head)
        let l1 =
            tail
            |> List.filter ((>) head)
        quickSort(l0) @ [head] @ quickSort(l1)

quickSort [-2; -3; 4; -1; 0; 1; 5; 7; -2]

open System

// merge two list into one list
let rec merge list0 list1 =
    match list0, list1 with
    | [], [] -> []
    | [], list
    | list, [] -> list
    | h0::t0, h1::t1 ->
        if h0 < h1 then
            [h0] @ merge t0 list1
        else
            [h1] @ merge list0 t1

// merge sort algorithm function
let rec mergeSort list =
    match list with
    | [] -> []
    | [a] -> [a]
    | [a; b] -> [ min a b; max a b ]
    | _ ->
        let firstHalf =
            list
            |> Seq.take (list.Length / 2)
            |> Seq.toList
        let secondHalf =
            list
            |> Seq.skip (list.Length / 2)
            |> Seq.toList

        let sortedFirstHalf = mergeSort firstHalf
        let sortedSecondHalf = mergeSort secondHalf

        merge sortedFirstHalf sortedSecondHalf

mergeSort [1;3;9;2;4;7;6;5]

let findElement (list:int list) start target =
    list
    |> Seq.skip start
    |> Seq.tryFind ((=) target)

let find sum (list:int list)  =
    [ for i in [0..list.Length-4] do
        for j in [i + 1..list.Length-3] do
            for k in [j + 1..list.Length-2] do
                let rest = sum - (list.[i] + list.[j] + list.[k])
                let result = findElement list (k+1) rest
                match result with
                | Some n -> yield (list.[i], list.[j], list.[k], n)
                | None -> ()
    ]

find 23 [10; 2; 3; 4; 5; 9; 7; 8]

Execution result

val it : (int * int * int * int) list =
  [(10, 2, 3, 8); (10, 2, 4, 7); (2, 4, 9, 8); (2, 5, 9, 7); (3, 4, 9, 7);
   (3, 5, 7, 8)]

let (|Exhausted|_|) i =
    if i < 0 then
        Some()
    else
        None

let array1 = [| 1; 3; 4; 6; 9; 0; 0; 0; 0; 0; |]
let array2 = [| 2; 3; 5; 8; 10; |]

let rec merge (i, j, k) =
    match i, j with
    | Exhausted, Exhausted
    | _, Exhausted ->
        ()
    | Exhausted, _ ->
        array1.[k] <- array2.[i]
        let i, j, k = i, (j - 1), (k - 1)
        merge (i, j, k)
    | _ ->
        if array1.[i] > array2.[j] then
            array1.[k] <- array1.[i]
            let i, j, k = (i - 1), j, (k - 1)
            merge(i, j, k)
        else
            array1.[k] <- array2.[j]
            let i, j, k = i, (j - 1), (k - 1)
            merge(i, j, k)

merge (4, 4, array1.Length - 1)

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; ]

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

let kadaneCircle data =
    // normal case
    let kadaneValue = kadane data

    // 2nd case
    let sum = Seq.sum data
    let invertMax =
        data
        |> List.map ((*) -1)
        |> kadane

    let ``2ndCase`` = sum + invertMax

    max kadaneValue ``2ndCase``

kadaneCircle [12; -5; 4; -8; -2; 11]

Execution result

val kadane : data:seq<int> -> int
val kadaneCircle : data:int list -> int
val it : int = 23

let findMedian (list0:int list) (list1:int list) =
    let totalCount = list0.Length + list1.Length

    let rec findFunction (list0:int list) list1 count =
        if count > 1 then
            match list0, list1 with
            | [], [] -> failwith "not possible, check empty first"
            | head::tail, [] -> findFunction tail [] (count - 1)
            | [], head::tail -> findFunction [] tail (count - 1)
            | h0::t0, h1::t1 ->
                if h0 < h1 then
                    findFunction t0 list1 (count-1)
                else
                    findFunction list0 t1 (count-1)
        else
            match list0, list1 with
            | [], [] -> failwith "not possible, check empty first"
            | head::tail, []
            | [], head::tail ->
                let pre = head
                let now = tail.Head
                if totalCount % 2 = 0 then
                    (float (pre + now)) / 2.
                else
                    float now
            | h0::t0, h1::t1 ->
                if totalCount % 2 = 0 then
                    (float (h0 + h1)) / 2.
                else
                    float (max h0 h1)

    if list0.IsEmpty && list1.IsEmpty then
        failwith "please input valid data"

    findFunction list0 list1 ((list0.Length + list1.Length) / 2)

findMedian [1] [2; 4; 5; 6; 7; 8; 10]

let getMedian (list:float array) =
    let len = list.Length
    if len % 2 = 0 then
        (list.[len / 2 - 1] + list.[len / 2]) / 2.
    else
        list.[len / 2]

let (|Median|) (list:float array) =
    let median = getMedian list
    let len = list.Length
    if len % 2 = 0 then
        (list.[0..len / 2 - 1], median, list.[len / 2..])
    else
        (list.[0..len / 2], median, list.[len / 2..])

let rec getMedianFromTwo (list0:float array) (list1:float array) =
    match list0, list1 with
    | [||], [||] -> 0.
    | [|a|], [|b|] -> (a + b) / 2.
    | [|a0; a1|], [|b0; b1|] -> ((max a0 b0) + (min a1 b1)) / 2.
    | Median(l0, m0, r0), Median(l1, m1, r1) ->
        if m0 = m1 then
            m0
        elif m0 < m1 then
            getMedianFromTwo r0 l1
        else //m0 > m1
            getMedianFromTwo l0 r1

let list0 = [|1.; 4.; 7.; 8.; 9.; 10.|]
let list1 = [|2.; 4.; 6.; 7.; 9.; 10.|]

let c = getMedianFromTwo list0 list1

type CompareResult =
    | Higher
    | Lower
    | Middle

let compare = function
    | low,current,_ when current <= low -> Lower
    | _, current,high when current >= high -> Higher
    | _ -> Middle

let dutchFlag (list: _ array) (low, high) =
    let swap (i,j) =
        let temp = list.[i]
        list.[i] <- list.[j]
        list.[j] <- temp

    let mutable i = 0
    let mutable lowPointer = 0
    let mutable highPointer = list.Length - 1

    while i<highPointer do
        let value = low, list.[i], high
        match compare value with
        | Lower ->
            swap (lowPointer, i)
            lowPointer <- lowPointer + 1
            i <- i + 1
        | Higher ->
            swap (highPointer, i)
            highPointer <- highPointer - 1
        | Middle ->
            i <- i + 1

let arr = [| 1; 9; 8; 2; 4; 3; 6; 7; 5; 0; |]
dutchFlag arr (3, 7)

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

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

        maxLength <- max maxLength DP.[i]

    maxLength

findMax()

type NodeType = int

// DU definition for a tree structure
type Tree =
    | Node of NodeType * Tree list

let createTree() =
    Node(1, [ Node(2, [Node(4, []);
                       Node(5, [])
                      ]);
              Node(3, [Node(6, []);
                       Node(7, [Node(9,[])]);
                       Node(8, [])
                      ])
            ])

let rec preOrder visit tree =
    match tree with
        | Node(value, children) ->
            visit value
            children
            |> Seq.iter (preOrder visit)

let rec postOrder visit tree =
    match tree with
        | Node(value, children) ->
            children
            |> Seq.iter (postOrder visit)
            visit value

let mutable result = []
let sum v =
    result <- result @ [v]
preOrder sum (createTree())

result <- []
postOrder sum (createTree())

Execution result for pre-order

val it : NodeType list = [4; 5; 2; 6; 9; 7; 8; 3; 1]

Execution result for post-order

val it : NodeType list = [1; 2; 4; 5; 3; 6; 7; 9; 8]

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(1, Node(2, Node(4, Nil, Nil),
                    Node(5,  Nil, Nil)),
              Node(3, Node(6, Nil, Nil),
                    Node(7, Node(9, Nil, Nil),
                            Node(8, Nil, Nil))
            ))

let rec inOrder visit tree =
    match tree with
        | Nil -> ()
        | Node(v, left, right) ->
            inOrder visit left
            visit v
            inOrder visit right

let mutable result = []
let sum v =
    result <- result @ [v]

inOrder sum (createBinaryTree())

Execution result for in-order traversal

val it : NodeType list = [4; 2; 5; 1; 6; 3; 9; 7; 8]

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(1, Node(2, Node(4, Nil, Nil),
                    Node(5,
                            Node(6, Nil, Nil),
                            Node(7, Nil, Nil))),
            Node(3,
                    Nil,
                    Node(8,
                            Nil,
                            Node(9, Nil, Nil)))
        )

let mutable queue : BinaryTree list = []
let enqueue x = queue <- [x] @ queue
let dequeue() =
    let result = Seq.last queue
    queue <-
        queue
        |> Seq.take (queue.Length - 1)
        |> Seq.toList
    result
let queueEmpty() = queue.Length = 0

let mutable result = []
let visit v = result <- result @ [v]

let layerTree tree =
    enqueue tree
    while not <| queueEmpty() do
        let tree = dequeue()
        match tree with
        | Nil -> ()
        | Node(v, left, right) ->
            visit v
            enqueue left
            enqueue right

layerTree (createBinaryTree())

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(6, Node(4, Node(2,
                            Node(1, Nil, Nil),
                            Node(3, Nil, Nil)),
                    Node(5,  Nil, Nil)),
            Node(7,
                    Nil,
                    Node(9, Nil, Nil))
        )

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(6, Node(4, Node(2,
                            Node(1, Nil, Nil),
                            Node(3, Nil, Nil)),
                    Node(5,  Nil, Nil)),
            Node(7,
                    Nil,
                    Node(9, Nil, Nil))
        )

let rec checkInOrder value list =
    match list with
    | [] -> true
    | head::tail ->
        if value<head then
            checkInOrder head tail
        else
            false

let rec inOrder visit tree =
    match tree with
        | Nil -> ()
        | Node(v, left, right) ->
            inOrder visit left
            visit v
            inOrder visit right

let mutable result = []
let sum v =
    result <- result @ [v]

inOrder sum (createBinaryTree())

checkInOrder System.Int32.MinValue result

type NodeType = { mutable X: int }

type Tree =
    | Node of NodeType * Tree list

let mutable stack : Tree list = []

let createTree() =
    Node({X=1}, [ Node({X = 2}, [Node({X = 4}, []);
                               Node({X = 5}, [])
                      ]);
                    Node({X = 3}, [Node({X = 6}, []);
                       Node({X = 7}, [Node({X = 9},[])]);
                       Node({X = 8}, [])
                      ])
            ])

let push x =
    stack <- [x] @ stack
let pop () =
    match stack with
    | [] -> None
    | head::tail ->
        stack <- tail
        Some head
let isEmpty() = Seq.isEmpty stack

let tagAsDelete (x:NodeType) = x.X <- 0

let deleteTree tree =
    push tree
    while not <| isEmpty() do
        let node : Tree option = pop()
        match node with
        | None -> ()
        | Some(Tree.Node(v, list)) ->
             list |> Seq.iter push
             tagAsDelete v

let tree = createTree()
deleteTree tree

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let getLeftPart inorder head =
    inorder
    |> Seq.takeWhile(fun n -> n <> head)
    |> Seq.toList

let getRightPart inorder head =
    inorder
    |> Seq.skipWhile(fun n -> n <> head)
    |> Seq.skip 1
    |> Seq.toList

let getPreOrderLeftPart preorder inorderLeft =
    let len = inorderLeft |> Seq.length
    preorder
    |> Seq.skip 1
    |> Seq.take len
    |> Seq.toList

let getPreOrderRightPart preorder inorderLeft =
    let len = inorderLeft |> Seq.length
    preorder
    |> Seq.skip 1
    |> Seq.skip len
    |> Seq.toList

let rec buildTree inorder preorder =
    match preorder with
    | [] -> Nil
    | head::tail ->
        let inorderLeft = getLeftPart inorder head
        let inorderRight = getRightPart inorder head
        let preorderLeft = getPreOrderLeftPart preorder inorderLeft
        let preorderRight = getPreOrderRightPart preorder inorderLeft
        Node(head,
             buildTree inorderLeft preorderLeft,
             buildTree inorderRight preorderRight)

buildTree [1; 2; 3; 4; 5; 6; 7; 9] [6; 4; 2; 1; 3; 5; 7; 9]

Execution result

BinaryTree =
  Node
    (6,Node (4,Node (2,Node (1,Nil,Nil),Node (3,Nil,Nil)),Node (5,Nil,Nil)),
     Node (7,Nil,Node (9,Nil,Nil)))

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

Execution result

val it : BinaryTree =
  Node
    (10,Node (5,Node (1,Nil,Nil),Node (7,Nil,Nil)),
     Node (40,Nil,Node (50,Nil,Nil)))

let (|Diff|_|) (a, b) =
    if (a * b < 0) || (a * b = 0 && a + b < 0) then Some true
    else None

let checkOneChild (preorder : int list) =

    seq {
        for i=0 to preorder.Length - 2 do
            let a = preorder.[i]-preorder.[i + 1];
            let b = preorder.[i]-preorder.[preorder.Length - 1];
            yield (a, b)
    }
    |> Seq.forall (fun (a, b) -> match a, b with
                                 | Diff _ -> false
                                 | _ -> true)

let list = [20; 10; 11; 13; 12;]

checkOneChild list

C# version

bool checkOneChild(int[] preorder)
    {
        for (int i = 0; i < preorder.Length - 2; i++)
        {
            int a = preorder[i] - preorder[i + 1];
            int b = preorder[i] - preorder[preorder.Length - 1];
            if ( (a * b < 0) || (a * b == 0 && a + b < 0) )
            {
                return false;
            }
        }

        return true;
    }

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let bst1 = Node(10,
                Node(7,
                    Node(5, Nil, Nil),
                    Node(9, Nil, Nil)),
                Node(12,
                    Node(11, Nil, Nil),
                    Nil))

let bst2 = Node(10,
                Node(7,
                    Node(4, Nil, Nil),
                    Node(9, Nil, Nil)),
                Node(12,
                    Node(11, Nil, Nil),
                    Nil))

let result = System.Collections.Generic.List<NodeType>()

let rec findCommon (tree0, tree1) =
    match tree0, tree1 with
    | Nil, Nil
    | Nil, _
    | _, Nil -> ()
    | Node(v0, l0, r0), Node(v1, l1, r1) ->
        if v0 = v1 then
            result.Add(v0)
            findCommon(l0, l1)
            findCommon(r0, r1)
        elif v0 < v1 then
            findCommon(tree0, l1)
        else //v0 > v1
            findCommon(l0, tree1)

findCommon (bst1, bst2)

result |> Array.ofSeq

Execution result

[| 10; 7; 9; 12; 11 |]

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(1, Node(2, Node(4, Nil, Nil),
                    Node(5,
                            Node(6, Nil, Nil),
                            Node(7, Nil, Nil))),
            Node(3,
                    Nil,
                    Node(8,
                            Nil,
                            Node(9, Nil, Nil)))
        )

let rec treeHeight tree =
    match tree with
    | Nil -> 0
    | Node(v, left, right) ->
        let leftHeight = treeHeight left
        let rightHeight = treeHeight right
        (max leftHeight rightHeight) + 1

let rec treeDiameter tree =
    match tree with
    | Nil -> 0
    | Node(v, left, right) ->
        let leftHeight = treeHeight left
        let rightHeight = treeHeight right
        let leftDiameter = treeDiameter left
        let rightDiameter = treeDiameter right
        max (leftHeight + rightHeight + 1)
            (max leftDiameter rightDiameter)

treeDiameter (createBinaryTree())

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(1, Node(2, Node(4, Nil, Nil),
                    Node(5,
                            Node(6, Nil, Nil),
                            Node(7, Nil, Nil))),
            Node(3,
                    Nil,
                    Node(8,
                            Nil,
                            Node(9, Nil, Nil)))
        )

let findLCA (node0, node1) root =
    let rec commonAncestor (node0, node1) root =
        match root with
        | Nil -> None
        | Node(v, left, right) ->
            match left, right with
            | Nil, Nil -> None
            | Node(v, _, _), _ when v = node0 || v = node1 -> Some root
            | _, Node(v, _, _) when v = node0 || v = node1 -> Some root
            | _ ->
                let l = left |> commonAncestor (node0, node1)
                let r = right |> commonAncestor (node0, node1)
                match l, r with
                | None, None -> None
                | Some(_), Some(_) -> Some root
                | Some(_) as n, None -> n
                | None, (Some(_) as n) -> n

    match root with
    | Nil -> None
    | Node(v, left, right) when v=node0 || v=node1 -> Some root
    | Node(v, left, right) -> commonAncestor (node0, node1) root

let tree = createBinaryTree()
type ResultRecord = { Nodes : NodeType*NodeType; Ancestor : NodeType }
let output r pair =
    match r with
    | Some(Node(v, _, _)) -> { Nodes = pair; Ancestor = v }
    | _ -> { Nodes = pair; Ancestor = -1 }

let pairsToFindAncestor = [
    (2, 3)
    (1, 8)
    (1, 2)
    (3, 8)
    (8, 7)
    (4, 6)
    (4, 7) ]

let r =
    pairsToFindAncestor
    |> List.map (fun pair -> pair, (tree |> findLCA pair))
    |> List.map (fun (pair, result) -> pair |> output result)

Execution result

[{Nodes = (2, 3); Ancestor = 1;};
 {Nodes = (1, 8); Ancestor = 1;};
 {Nodes = (1, 2); Ancestor = 1;};
 {Nodes = (3, 8); Ancestor = 1;};
 {Nodes = (8, 7); Ancestor = 1;};
 {Nodes = (4, 6); Ancestor = 2;};
 {Nodes = (4, 7); Ancestor = 2;}]

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(20, Node(8, Node(5, Nil, Nil),

                     Node(12,
                            Node(11, Nil, Nil),
                            Node(15, Nil, Nil))),
            Node(30,
                    Node(21, Nil, Nil),
                    Node(32, Nil, Nil))
        )

let tree = createBinaryTree()

let rec findLCAInBST (n0, n1) root =
    match root with
    | Nil -> None
    | Node(v, left, right) ->
        if v >= n0 && v <= n1 then
            Some v
        elif v > n0 && v > n1 then
            findLCAInBST (n0, n1) left
        else
            findLCAInBST (n0, n1) right

tree |> findLCAInBST (3, 15)

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(32, Node(9, Node(4, Nil, Nil),
                    Node(5,  Nil, Nil)),
            Node(23, Node(6, Nil, Nil),
                    Node(17, Node(10, Nil, Nil),
                            Node(7, Nil, Nil))
            ))
let rec checkTree root =
    match root with
    | Nil -> true, None
    | Node(v, left, right) ->
        let leftResult, leftSum = checkTree left
        let rightResult, rightSum = checkTree right
        match leftSum, rightSum with
        | None, None -> true, Some v
        | _ ->
            let leftS = match leftSum with Some(n) -> n | None -> 0
            let rightS = match rightSum with Some(n) -> n | None -> 0
            let result = leftResult && rightResult && (leftS + rightS = v)
            result, Some v

createBinaryTree() |> checkTree |> fst

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let createBinaryTree() =
    Node(1, Node(2, Node(4, Nil, Nil),
                        Node(5,
                            Node(6, Nil, Nil),
                            Node(7, Nil, Nil))),
            Node(3,
                    Nil,
                    Node(8,
                            Nil,
                            Node(9, Nil, Nil)))
        )

let mutable result = []
let add x =
    result <- result @ [x]

let rec visitLeaf root =
    match root with
    | Nil -> ()
    | Node(v, Nil, Nil) -> add v
    | Node(v, left, right) ->
        visitLeaf left
        visitLeaf right

let rec visitLeftBoundary root =
    match root with
    | Nil -> ()
    | Node(v, Nil, Nil) -> ()
    | Node(v, Nil, right) ->
        add v
        visitLeftBoundary right
    | Node(v, left, _) ->
        add v
        visitLeftBoundary left

let rec visitRightBoundary root =
    match root with
    | Nil -> ()
    | Node(v, Nil, Nil) -> ()
    | Node(v, left, Nil) ->
        visitRightBoundary left
        add v
    | Node(v, _, right) ->
        visitRightBoundary right
        add v

let getBoundary root =
    match root with
    | Nil -> ()
    | Node(v, left, right) ->
        add v
        visitLeftBoundary left
        visitLeaf left
        visitLeaf right
        visitRightBoundary right

let tree = createBinaryTree()

getBoundary tree

Execution result

> result;;
val it : NodeType list = [1; 2; 4; 6; 7; 9; 8; 3;]

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

getSub str

let getPalindrome (str:string) =
    let rec isStringPalindrome (str:string) =
        if str.Length = 0 || str.Length = 1 then true
        else
            let start, ``end`` = 0, str.Length-1
            if str.[start] = str.[``end``] then isStringPalindrome(str.[start+1..``end`` -
1])
            else false
    let mutable result = System.String.Empty

    for i = 0 to str.Length - 1 do
        let subStr = str.[i..str.Length - 2]
        for explore = i + 1 to str.Length - 1 do
            let strToCheck = str.[i..explore]
            if isStringPalindrome(strToCheck) then
                result <- if result.Length > strToCheck.Length then result else strToCheck

    sprintf "%s" result

getPalindrome "abab"
getPalindrome "sambabmiv"
getPalindrome "aa"
getPalindrome "aaa"
getPalindrome "yabadabadoo"

Execution result

bab
mbabm
aa
aaa
abadaba

open System

let rec permute (str:string) =
    let chList =
        str
        |> List.ofSeq
    match chList with
    | [] -> []
    | [ch] -> [ string ch ]
    | head::tail ->
        let ch = head
        let tail = String.Join("", tail)
        let subStringList = permute tail
        [ for (subString:string) in subStringList do
            for i = 0 to subString.Length do
                let resultString = subString.Insert(i, string ch)
                yield resultString]

permute "abcd"

Execution result from FSI

val it : string list =
  ["abcd"; "bacd"; "bcad"; "bcda"; "acbd"; "cabd"; "cbad"; "cbda"; "acdb";
   "cadb"; "cdab"; "cdba"; "abdc"; "badc"; "bdac"; "bdca"; "adbc"; "dabc";
   "dbac"; "dbca"; "adcb"; "dacb"; "dcab"; "dcba"]

open System

let (| AllEmpty | Str0NotEmpty | Str1NotEmpty | Both |) (str0, str1) =
    let b0 = String.IsNullOrEmpty(str0)
    let b1 = String.IsNullOrEmpty(str1)
    match b0, b1 with
    | true, true -> AllEmpty
    | false, true -> Str0NotEmpty
    | true, false -> Str1NotEmpty
    | false, false -> Both

let mutable result = []
let add x =
    result <- result @ [x]

let interLeaving str0 str1 =
    let rec interLeavingStrs str0 str1 current =
        match str0, str1 with
        | AllEmpty _ -> ()
        | Str1NotEmpty -> add (current+str1)
        | Str0NotEmpty -> add (current+str0)
        | Both ->
            interLeavingStrs (str0.Substring(1)) str1 (current + string str0.[0])
            interLeavingStrs str0 (str1.Substring(1)) (current + string str1.[0])

    interLeavingStrs str0 str1 ""

interLeaving "ab" "cd"

Execution result in FSI

> result;;
val it : string list = ["abcd"; "acbd"; "acdb"; "cabd"; "cadb"; "cdab"]

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
        match pos, cnd with
        | _ when w.[pos - 1] = w.[cnd] ->
            cnd <- cnd + 1
            t.[pos] <- cnd
            pos <- pos + 1
        | _ when cnd > 0 ->
            cnd <- t.[cnd]
        | _ ->
            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"

DFS code in the Portable Class Library project

type NodeStack = System.Collections.Generic.Stack<Node>
type VisitedList = System.Collections.Generic.List<Node>

let stack = NodeStack()
let visited = VisitedList()

let visit node =
    visited.Add(node)

let (| Visited | _ |) node =
    if visited.Contains(node) then
        Some node
    else
        None

let dfsGraph graph (start:Node)=
    stack.Push(start)
    visited.Clear()

    while stack.Count <> 0 do
        let currentNode = stack.Pop()
        match currentNode with
        | Visited(_) -> ()
        | _ ->
            visit currentNode
            let nodes =
                currentNode.OutgoingEdges
                |> Seq.map (fun edge -> edge.ToNode)
                |> Seq.distinctBy (fun node -> node.ID)
                |> Seq.toList
            nodes
            |> Seq.iter (fun node -> stack.Push node)

Invoker code

let g = DGMLGraph.DGMLReader(new
System.IO.StreamReader(@"C:MyCodeConsoleApplication1Graph1.dgml"))
let (Some startNode) = g.Graph.FindNode("1")
DGMLGraph.dfsGraph g startNode
printfn "%A" (Seq.toList <| DGMLGraph.visited)

type NodeQueue = System.Collections.Generic.Queue<Node>
type VisitedList = System.Collections.Generic.List<Node>

let queue = NodeQueue()
let visited = VisitedList()

let visit node =
    visited.Add node

let (| Visited | _ |) node =
    if visited.Contains node then
        Some node
    else
        None

let dfsGraph graph (start:Node)=
    queue.Enqueue start
    visited.Clear()

    while queue.Count <> 0 do
        let currentNode = queue.Dequeue()
        match currentNode with
        | Visited(_) -> ()
        | _ ->
            visit currentNode
            let nodes =
                currentNode.OutgoingEdges
                |> Seq.map (fun edge -> edge.ToNode)
                |> Seq.distinctBy (fun node -> node.ID)
                |> Seq.toList
            nodes
            |> Seq.iter (fun node -> queue.Enqueue node)

type Location = { X : int; Y : int }
type Path = Location list

let graph = [
        [1;1;1;1;0]
        [0;1;0;1;0]
        [0;1;0;1;1]
        [0;1;1;1;0]
        [0;1;0;1;0]
            ]

let getNeighbors (point:Location) =
    let getLeft (point:Location) =
        if point.X = 0 then None
        else Some { X = point.X - 1; Y = point.Y }
    let getTop (point:Location) =
        if point.Y = 0 then None
        else Some { X = point.X; Y = point.Y - 1 }
    let getRight (point:Location) =
        if point.X = 4 then None
        else Some { X = point.X + 1; Y = point.Y }
    let getBottom (point:Location) =
        if point.Y=4 then None
        else Some { X = point.X; Y = point.Y + 1 }
    let result =
        [getLeft point;
         getTop point;
         getRight point;
         getBottom point]
    result
    |> List.filter (fun n -> match n with Some _ -> true | None -> false )
    |> List.map (fun (Some n) -> n)
    |> List.filter (fun n -> graph.[n.Y].[n.X] <> 0)

let rec findAllPath (startPoint:Location) (endPoint:Location) (path:Path)=
    if startPoint = endPoint then
        [ path ]
    else
        let neighbours =
            getNeighbors startPoint
            |> List.filter (fun n -> path |> List.exists (fun x -> x=n) |> not)
        [ for n in neighbours do
            for path in findAllPath n endPoint (path@[n]) do
                if path.Length > 0 then
                    yield path
                else
                    () ]
let start = { X = 0; Y = 0 }
let endPoint = { X = 4; Y = 2 }

let path = [start]
let c = findAllPath start endPoint path

type Location = { X : int; Y : int }

[<System.Diagnostics.DebuggerDisplay("({Location.X},{Location.Y})")>]
type Node() as this =
    member val IsBlock = false with get, set
    member val PreviousNode = this with get, set
    member val Location = {X = 0; Y = 0} with get, set
    member val H = 0 with get, set
    member val MoveCost = 1000 with get, set
    member this.TotalCost = this.MoveCost + this.H

type Path = Location list
let graph = [
        [1;1;1;1;1;1;1]
        [1;1;1;0;1;1;1]
        [1;1;1;0;1;1;1]
        [1;1;1;0;1;1;1]
        [1;1;1;0;1;1;1]
        [1;1;1;1;1;1;1]
        [1;1;1;1;1;1;1]
            ]

let nodeGraph =
    graph
    |> List.mapi (fun y row ->
                    row
                    |> List.mapi (fun x n ->
                        let loc = {X = x; Y = y}
                        Node(IsBlock= (if n = 1 then false else true),
                             Location = loc))
                )

let rightMax = 6

let getNeighbors (point:Location) =
    let getLeft (point:Location) =
        if point.X = 0 then None
        else Some { X = point.X - 1; Y = point.Y }
    let getTop (point:Location) =
        if point.Y = 0 then None
        else Some { X = point.X; Y = point.Y - 1 }
    let getRight (point:Location) =
        if point.X = rightMax then None
        else Some { X = point.X + 1; Y = point.Y }
    let getBottom (point:Location) =
        if point.Y=rightMax then None
        else Some { X = point.X; Y = point.Y + 1 }
    let getLeftTop (point:Location) =
        if point.X = 0 || point.Y = 0 then None
        else Some { X = point.X - 1; Y= point.Y - 1 }
    let getRightTop (point:Location) =
        if point.X = rightMax || point.Y = 0 then None
        else Some { X = point.X + 1; Y=point.Y - 1 }
    let getRightBottom (point:Location) =
        if point.X = rightMax || point.Y = rightMax then None
        else Some { X = point.X + 1; Y = point.Y + 1 }
    let getLeftBottom (point:Location) =
        if point.X = 0 || point.Y = rightMax then None
        else Some { X = point.X - 1; Y=point.Y + 1 }
    let result =
        [(10, getLeft point); (10, getTop point); (10, getRight point); (10, getBottom
point);
         (14, getLeftTop point); (14, getRightTop point); (14, getRightBottom point);
         (14, getLeftBottom point);
        ]
    let result =
        result
        |> List.filter (fun (cost, n) -> match n with Some _ -> true | None -> false )
        |> List.map (fun (cost, (Some n)) -> cost,n)
        |> List.filter (fun (cost, n) -> nodeGraph.[n.Y].[n.X].IsBlock |> not)
        |> List.map (fun (cost, n) -> cost, nodeGraph.[n.Y].[n.X])
    result

let mutable openList : Node list = []
let mutable closedList : Node list = []

let addOpenList node =
    openList <- openList @ [node]

let addClosedList node =
    closedList <- closedList @ [node]

let closedListContain (endPoint:Node) =
    closedList
    |> Seq.exists (fun n -> n.Location = endPoint.Location)

let openListContain (node:Node) =
    openList
    |> Seq.exists (fun n -> n.Location = node.Location)

let ``a*`` start (endPoint:Node) =
    addOpenList start
    nodeGraph
    |> List.iter (fun list ->
                    list
                    |> List.iter (fun n ->
                                    n.H <- 10 * (abs (n.Location.X - endPoint.Location.X)
                                           + abs (n.Location.Y - endPoint.Location.Y))))
    while not <| closedListContain endPoint && openList.Length > 0 do
        let currentNode::tail = openList |> List.sortBy (fun n -> n.TotalCost)
        openList <- tail
        addClosedList currentNode

        let neighbours:(int*Node) list =
                getNeighbors currentNode.Location
                |> List.filter (fun (_, node) -> node |> closedListContain |> not)
        for cost, node in neighbours do
            if node.MoveCost > currentNode.MoveCost + cost then
                node.PreviousNode <- currentNode
                node.MoveCost <- currentNode.MoveCost + cost
            if not <| openListContain node then
                addOpenList node

let start = nodeGraph.[0].[0]
start.MoveCost <- 0
let endPoint = nodeGraph.[2].[5]

``a*`` start endPoint

module DGMLGraph

open System

type Graph() =
    let mutable nodes = []
    let mutable edges = []

    member this.Nodes with get() = nodes
    member this.Edges with get() = edges
    member this.CreateNode (id) =
        match this.FindNode (id) with
        | Some (n) -> None
        | None ->
            let node = Node(this, ID = id)
            nodes <- nodes @ [ node ]
            Some node
    member this.CreateEdgeFromNode(from:Node, ``to``:Node, id) =
        match this.FindEdge id with
        | Some (edge) -> None
        | None ->
        let edge = Edge(this, from, ``to``, ID = id)
        from.AddOutgoingEdge (edge)
        ``to``.AddIncomingEdge (edge)
        edges <- edges @ [edge]
        Some edge
    member this.CreateEdgeFromID(from, ``to``, id) =
        let fromNode = this.FindNode (from)
        let toNode = this.FindNode (``to``)
        match fromNode, toNode with
        | Some(n0), Some(n1) -> this.CreateEdgeFromNode(n0, n1, id)
        | _ -> None
    member this.FindNode (id) =
        (nodes:Node list) |> Seq.tryFind(fun n -> n.ID = id)
    member this.FindEdge (id ) =
        (edges:Edge list) |> Seq.tryFind(fun edge -> edge.ID = id)
    member this.RemoveEdge(edge:Edge) =
        (edge.FromNode:Node).RemoveOutgoingEdge (edge)
        (edge.ToNode:Node).RemoveIncomingEdge (edge)
        edges <- edges |> List.filter (fun n -> n<>edge)
    member this.RemoveNode(node:Node) =
        node.OutgoingEdges @ node.IncomingEdges |> List.iter this.RemoveEdge
        nodes <- nodes |> List.filter (fun n -> n<>node)

and Node(g) =
    let mutable incomingEdges = []
    let mutable outgoingEdges = []
    member val ID = Unchecked.defaultof<_> with get, set
    member val Data = Unchecked.defaultof<_> with get, set
    member this.IncomingEdges with get() = incomingEdges
    member this.OutgoingEdges with get() = outgoingEdges
    member this.AddIncomingEdge(edge:Edge) =
        if edge.ToNode = this then
        incomingEdges <- incomingEdges |> List.append [edge]
    member this.AddOutgoingEdge(edge:Edge) =
        if edge.FromNode = this then
        outgoingEdges <- outgoingEdges |> List.append [edge]
    member this.RemoveIncomingEdge(edge:Edge) =
        incomingEdges <- incomingEdges |> List.filter (fun n -> n <> edge)
    member this.RemoveOutgoingEdge(edge:Edge) =
        outgoingEdges <- outgoingEdges |> List.filter (fun n -> n <> edge)
    override this.ToString() =
        sprintf "Node(%A)" this.ID

and Edge(g, from:Node, ``to``:Node) =
    member val ID = Unchecked.defaultof<_> with get, set
    member val Data = Unchecked.defaultof<_> with get, set
    member this.FromNode with get() = from
    member this.ToNode with get() = ``to``
    override this.ToString() =
        sprintf "Edge(%A, %A -> %A)" this.ID this.FromNode this.ToNode

open System.IO
open System.Xml.Linq

type DGMLReader(textReader:TextReader) =
    let doc = XDocument.Load(textReader:TextReader)
    let graph = Graph()
    do
        let nodes = doc.Descendants() |> Seq.filter (fun n -> n.Name.LocalName = "Node")
        let graphNodes =
                nodes
                |> Seq.map (fun node ->
                        let (Some graphNode) =
                            graph.CreateNode(node.Attribute(XName.Get("Id")).Value)
                        graphNode.Data <- System.Int32.MaxValue)
                |> Seq.toList
        let edges = doc.Descendants() |> Seq.filter (fun n -> n.Name.LocalName = "Link")
        edges
        |> Seq.iteri (fun i edge->
                let fromNode = edge.Attribute(XName.Get("Source")).Value
                let toNode = edge.Attribute(XName.Get("Target")).Value
                let (Some graphEdge) = graph.CreateEdgeFromID(fromNode, toNode, i)
                graphEdge.Data <- Convert.ToInt32 ( edge.Attribute(XName.Get("Label")).Value )
                ())
    member this.Graph with get() = graph

type Path = System.Collections.Generic.List<Node>
let openList = Path()
let closedList = Path()

open System.Collections.Generic
open System.Linq

let getNeighbors (currentNode:Node) =
    currentNode.OutgoingEdges
    |> List.map (fun edge -> edge.ToNode)
    |> List.filter (fun node -> not <| closedList.Contains(node))

let getCost (node:Node, currentNode:Node) =
    let (Some edge) =
        currentNode.OutgoingEdges
        |> List.tryFind (fun edge -> edge.ToNode = node)
    edge.Data

let ``Dijkstra's algorithm`` startPoint =
    openList.Add (startPoint)
    startPoint.Data <- 0
    while openList.Count > 0 do
         let currentNode = openList |> Seq.minBy (fun n -> n.Data)
         let neighbors : Node list = getNeighbors currentNode
         neighbors
         |> List.iter (fun node ->
                 let distance = getCost (node, currentNode)
                 node.Data <- min (currentNode.Data + distance) node.Data)
         openList.AddRange (neighbors)
         ignore <| openList.Remove (currentNode)
         closedList.Add (currentNode)

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

    getCombinationFunction list elementNeeded []

getCombination [1; 2; 3; 4] 3

Execution result

val getCombination : list:int list -> elementNeeded:int -> int list list
val it : int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 4]; [2; 3; 4]]

let letters =
    [
    '0', ['0']
    '1', ['1']
    '2', ['2'; 'A'; 'B'; 'C']
    '3', ['3'; 'D'; 'E'; 'F']
    '4', ['4'; 'G'; 'H'; 'I']
    '5', ['5'; 'J'; 'K'; 'L']
    '6', ['6'; 'M'; 'N'; 'O']
    '7', ['7'; 'P'; 'Q'; 'R'; 'S']
    '8', ['8'; 'T'; 'U'; 'V']
    '9', ['9'; 'W'; 'X'; 'Y'; 'Z']
    ]
    |> Map.ofList

let mutable currentState = ('0', -1)
let mutable result = System.Collections.Generic.List<_>()

let output() =
    let char, times = currentState
    if times >=0 then
        let l = letters.[char]
        let len = l.Length
        let c = l.[times%len]
        result.Add(c)
    else
        ()

let getInput (chs:char seq) =
    chs
    |> Seq.iter (fun ch ->
                    let char, times = currentState
                    if ch=char then
                        currentState <- (ch, times+1)
                    else
                        output()
                        currentState <- (ch, 0))

    output()

    result |> Seq.toList

getInput "12224444444210"

open System

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

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

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

let rand = System.Random()

let (|InReservoirRange|_|) i resultSize =
   if i < resultSize then
     Some()
   else
     None

type ResultList<'a> = System.Collections.Generic.List<'a>
let result = ResultList<_>()

let reservoirSampling data resultSize =
   let (|InReservoirRange|_|) i = (|InReservoirRange|_|) i resultSize
   data
   |> Seq.iteri (fun index n ->
           match index with
           | InReservoirRange->
             result.Add(n)
           | _ ->
             let newIndex = rand.Next(index)
             match newIndex with
             | InReservoirRange ->
               result.[newIndex] <- n
             | _ -> ())

let seq = seq { for i = 0 to 100 do yield i }
reservoirSampling seq 5

let (|Vertical|_|) ((x1, y1), (x2, y2)) = if x1 = x2 then Some() else None
let assertFunction a b = if a <> b then failwith "fail test"

let checkIntersect (p0, p1, p2, p3) =
    let x1, y1 = p0
    let x2, y2 = p1
    let x3, y3 = p2
    let x4, y4 = p3

    match (p0, p1), (p2, p3) with
    | Vertical, Vertical -> x1 = x3
    | Vertical, _ ->
        let delta (x, y) = (y3 - y4) / (x3 - x4) * (x - x3) + y3 - y
        (x1 - x3) * (x1 - x4) <= 0 &&
        delta (x2, y2) * delta (x1, y1) <= 0

    | _, Vertical
    | _ ->
        let delta (x, y) = (y1 - y2) / (x1 - x2) * (x - x1) + y1 - y
        (x3 - x1) * (x3 - x2) <= 0 &&
        delta (x3, y3) * delta (x4, y4) <= 0

// one line is a normal line from (0, 0) to (5, 5)
assertFunction true <| checkIntersect ( (0, 0), (5, 5), (0, 5), (5, 0) )
assertFunction false <| checkIntersect ( (0, 0), (5, 5), (0, 5), (1, 4) )
assertFunction false <| checkIntersect ( (0, 0), (5, 5), (5, 0), (4, 1) )
assertFunction true <| checkIntersect ( (0, 0), (5, 5), (1, 0), (1, 5) )
assertFunction false <| checkIntersect ( (0, 0), (5, 5), (4, 0), (4, 2) )
assertFunction true <| checkIntersect ( (0, 0), (5, 5), (4, 0), (4, 5) )
assertFunction false <| checkIntersect ( (0, 0), (5, 5), (0, 4), (1, 4) )
assertFunction true <| checkIntersect ( (0, 0), (5, 5), (0, 4), (5, 4) )
assertFunction false <| checkIntersect ( (0, 0), (5, 5), (5, 4), (5, 4) )
assertFunction true <| checkIntersect ( (0, 0), (5, 5), (5, 5), (5, 5) )

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]

Execution result

val it : (int * int * int) list =
  [(10, 21, 22); (10, 100, 101); (21, 100, 101); (22, 100, 101);
   (100, 101, 200); (101, 200, 300)]

namespace FSharp.NN

open System
open System.Collections.Generic

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

// neuron in the neural network
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

// layer in the neural network
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())

// neural network
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.BackPropagation(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 n ->
                                     let weight = n.Input.[hiddenNode].Weight
                                     (n.Error * weight) * sigmoidDerivative(hiddenNode.
Output))

    member this.BackPropagation(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