F# on Algorithms - Find median from two sorted array

Find median from two sorted arrays is another typical questions. Feel dizzy when seeing indexes in the algorithm? I am with you.. :)

In this sample, I want to show how to use Active Pattern to decompose the data. From the code itself, you can easily find the hint of the data. If you see (l, value, r) which is from a sorted list. Most likely, the l, value, and r are in order. Also the Array slicing is a nice syntax feature as well.


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

let c = getMedianFromTwo list0 list1

Tweet to fsharp

F# on Algorithms - merge sort

Not every Saturday is a pleasant sunshine blue sky. Today is one of these Saturdays.

The real driving power for F# is business requirements from the community and the success of F# depends on the success of community. I was hoping these materials can  inspires discussions around F# and eventually increase the adoption of F#. Our team, like me, wants to serve the community better, so please tell me, your code has bug, your code can be more concise, or your code is shit. 

So please, together, we can make it.

open System

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

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]

Tweet to fsharp

F# on Algorithms - Quick sort

For a long time, I heard the F# is good at algorithm and today I decided to start on what can F# do when implement basic algorithms. The first one is the quick sort algorithm. I was shocked when I finished my first task. The code is very clean and easy to understand. If you replace the (<=) with (<), you can actually remove the duplicated elements in the array.

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]

Array.Create and mutable value

F#'s Array.Create take two parameters: one is the int and another is another a value. I got a customer report said the a0, a1, and a2 show the same value. He expected the value should be different.


type MyClass() =
    let mutable a = 3.0

    member this.A
        with get() = a
        and set(v) = a <- v

let b = Array.create 3 (MyClass())

b.[0].A < - 22.
b.[1].A < - 23.
b.[2].A < - 24.

let a0 = b.[0].A
let a1 = b.[1].A
let a2 = b.[2].A

The problem is the MyClass(), it create an instance of MyClass and the b array contains three references (pointers) to a single MyClass instance. I tried record type and it behaves the same.

SelfNote: SilverLight GetRoot

To get the current window, should use Window.GetWindow(currentElement) and then find Visual, not the Application.Current.RootVisual.

private static void SetRootVisual()
{
    if ((_rootVisual == null) && (Application.Current != null))
    {
        _rootVisual = Application.Current.RootVisual as FrameworkElement;
        if (_rootVisual != null)
        {
            _rootVisual.MouseMove += new MouseEventHandler(ToolTipService.OnRootMouseMove);
            _rootVisual.SizeChanged += new SizeChangedEventHandler(ToolTipService.OnRootVisualSizeChanged);
        }
    }
}

Math (Unicode) symbol add-on for F#

During my San Francisco trip, Jack asked the math symbol feature. I decide to give it a try and now the first version is ready. The screenshot is shown below. The add-on can be downloaded from Visual Studio gallery.

This add-on only changes the visual of the string and the source code is untouched. So if you open it in a notepad, the code won't contain any math (Unicode) symbol.

The add-on needs a replace file located under "My Document". The sample file is located here. You can download the file and put it under "My Document".

Please leave your comments. :)

Tweet to fsharp

DGML Type Provider - Explore Designer support for F#

When waiting for the test result for my symbol add-on in the tranquility of Saturday night, I suddenly realized that the DGML file in Visual Studio can be used to design a state machine. My idea is simple. Use DGML represent a state machine and use type provider to generate some code for me. Sort of designer support for F#. Only the color is not perfect, but it is better than nothing.. :-)

I did a library to process any DGML file. The library serves as the base class for the type provider and the type provider can help me generate some code. I made up a prototype and the source code is check in at  F# sample pack. (on Sep 9, 2012 2:17 AM). You can go to "source" and the type provider is under SampleProvider folder.

The DGML file is shown in Visual Studio like:

And the transition code is like:

// set the transition functions
t.SetFunction(t.State0, printObj)
t.SetFunction(t.State1, printObj)
t.SetFunction(t.State2, printObj)
t.SetFunction(t.State3, printObj)
// valid transitions
t.TransitTo_State1()
t.TransitTo_State2()
t.TransitTo_State3()
// invalid transition
t.TransitTo_State2()

Please leave your comments.. :)

Tweet to fsharp