Programming in F#

Posted By: Jingyi on July 27, 2010

F# became a first class citizen in Visual Studio 2010. What is F#? F# is a multiparadigm programming language built on .NET, which supports functional programming, object-oriented programming and imperative programming (F# allows you to modify the contents of memory). F# is also statically typed but has type inference built in it. Most of time, the programmers don’t need to explicitly put the type annotation for the variables/identifiers since the compiler will automatically figure it out. For example, let a = 1 is a valid expression. However, the real story will be let (a : int) = 1. Because the compiler can figure out the type of a is int, the programmer doesn’t need put the type when he introduces the value a.

A while ago, I found a problem on the MIT website. Here is the problem: You are given an arithmetic expression containing N real numbers and N - 1 operators, each either + or *. Your goal is to perform the operations in an order that maximizes the value of the expression. That is, insert N - 1 pairs of parentheses into the expression so that its value is maximized.

For example, 1) For the expression 6 * 3 + 2 * 5, the optimal ordering is to add the middle numbers first, then perform the multiplications: ((6 * (3 + 2)) * 5) = 150. 2) For the expression 0.1 * 0.1 + 0.1, the optimal ordering is to perform the multiplication first, then the addition: ((0.1 * 0.1) + 0.1) = 0.11. 3) For the expression (-3) * 3 + 3, the optimal ordering is ((-3) * 3) + 3) = -6.

The problem itself is clear. The solution is not very trivial. I decided to write a program to do it. Since by then I was reading some F# tutorials/materials, I decided to use F#. I had written some small F# programs just for testing out the language features. It is a good chance to apply the learning.

Here is the code for this problem. There are 3 files select.fs, interpreter.fs and Program.fs (Program.fs is the main test program). I don’t have a good algorithm to solve it. I just did what was described in the problem description. Find all the possible positions and put parentheses in these positions to form tokenized stream. Then I wrote an interpreter (in interpreter.fs file) to evaluate these possible expression and find the maximum value for these evaluated expressions. It is not terribly difficult but it did take some time to do it. It took me about 4 hours to write the code and another 3 hours to debug it. It is very hard to make the stack work properly for the interpreter. To be honest, I am not sure the program really solves the problem. The limited tests show it is right. I hope somebody else can come up with something so that we can compare the result. It was a pleasant experience to use F# to solve this problem. My next hope will be using F# to write a lisp interpreter. However, that may take forever.

(* file select.fs *)

module Select
 
exception OperandNumberException of string
 
 
let choose2 (l : seq<_>) =    (* seq<_> could be written as 'a seq *)
    [ for i = 0 to Seq.length l - 1 do
        for j = i + 1 to Seq.length l - 1 do
            yield [Seq.nth i l; Seq.nth j l] ]
 
let choose2_tuple (l : 'a seq) =
    [ for i = 0 to Seq.length l - 1 do
        for j = i + 1 to Seq.length l - 1 do
            yield Seq.nth i l, Seq.nth j l ]
 
let rec select n (l : 'a seq) =
 
    let merge elem l = 
        [ for e in l -> elem :: e ]
 
    let rec choose n (l : 'a seq) =
        if n = 1 then
            [for elem in l -> [elem]]
        elif n = 2 then
            choose2 l
        else
            match Seq.toList l with
            [] -> []
            |hd::tl -> 
                let current = choose (n - 1) tl |> merge hd
                let rest = choose n tl
                current @ rest
    
    choose n l
 
      
let indexer (l : 'a seq) =
    [ for i = 0 to Seq.length l - 1 do
        for j = i + 1 to Seq.length l - 1 do
            yield Seq.nth i l, Seq.nth j l ]
 
let good_pair pair = 
    let first = fst pair
    let first_beg = fst first
    let first_end = snd first
 
    let second = snd pair
    let second_beg = fst second
    let second_end = snd second
 
    first_beg >= second_beg && first_end <= second_end || 
    first_beg <= second_beg && first_end >= second_end || 
    first_beg > second_end || 
    second_beg > first_end
 
    
let predicate (l : (int * int) list) =           (* l could be written as 'a list *)
    let pair = choose2_tuple l
    pair |> Seq.forall (fun x -> good_pair x)
 
    
let rec group n ret (l :int seq) =
    let group_n n (l : int seq) =
        let candidate = indexer l |> select n
        candidate |> List.filter predicate
 
    if n = 1 || n = 2 then
        let r = group_n n l
        List.append r ret
    else
        let r = group_n n l
        let c = List.append r ret
        group (n - 1) c l
    
 
let tokenize (str : string) =     
    str.Split([|' '|], System.StringSplitOptions.RemoveEmptyEntries) |> List.ofArray 
            
 
let map shift_n (l : (int * int) seq) =
    let shift k = k * 2
 
    let open_p = l |> Seq.groupBy (fun p -> fst p)
                   |> Seq.map (fun (k, v) -> (shift k, String.replicate (Seq.length v ) Interpret.open_paren))
 
    let close_p = l |> Seq.groupBy (fun p -> snd p)
                    |> Seq.map (fun (k, v) -> (shift k, String.replicate (Seq.length v) Interpret.close_paren))
 
    Seq.append open_p close_p |> Map.ofSeq
 
let put_paren (tokens : string list) (m : Map) =
    let mutable ret = []
 
    for i = 0 to List.length tokens - 1 do
        let v = Map.tryFind i m
        match v with
        |None -> ret <- (List.nth tokens i) :: ret
        |Some x ->
            if x.StartsWith(Interpret.open_paren) then
                let arr = Array.create (x.Length) Interpret.open_paren
                ret <- List.append (List.ofArray arr) ret
                ret <- (List.nth tokens i) :: ret
            else
                ret <- (List.nth tokens i) :: ret
                let arr2 = Array.create x.Length Interpret.close_paren
                ret <- List.append (List.ofArray arr2) ret
    List.rev ret
 
let compute input =
    let tokens = tokenize input
    let n = (System.Math.Ceiling(float tokens.Length / 2.0) |> int) - 1
    if n = 0 then
        OperandNumberException("at least one operator is required") |> raise
 
    let idx = [|0..n|]
    let ms = idx |> group n []
    let maps = [for elm in ms -> map (n - 1) elm]
    let results = [for m in maps -> put_paren tokens m]
 
    results |> Seq.map (fun x -> (new Interpret.Interpreter(x)).interpret)
 
let max input = 
    compute input |> Seq.max
 
 (* the to_string function is for debug/display purpose, it will display all the expression with parenthese in right places *)

let to_string input =
 
    let put_paren_in_string (tokens : string list) (m : Map) = 
        let buf = new System.Text.StringBuilder()
    
        for i = 0 to List.length tokens - 1 do
            let v = Map.tryFind i m
 
            match v with
            |None -> buf.Append(List.nth tokens i) |> ignore
            |Some x -> 
                if x.StartsWith (Interpret.open_paren) then
                    buf.Append(x).Append(List.nth tokens i) |> ignore
                else
                    buf.Append(List.nth tokens i).Append(x) |> ignore
 
        buf.ToString()
 
    let tokens = tokenize input
    let n = (System.Math.Ceiling(float tokens.Length / 2.0) |> int) - 1
    let idx = [|0..n|]
    let ms = idx |> group n []
    let maps = [for elm in ms -> map (n - 1) elm]
    [for m in maps -> put_paren_in_string tokens m]

(* file interpreter.fs *)

module Interpret
 
let open_paren = "("
let close_paren = ")"
let plus = "+"
let times = "*"

type Interpreter(tokens : string seq) =
 
    let pos = ref 0
 
    member this.move = 
        pos := !pos + 1
 
    member private this.is_done = 
        !pos >= Seq.length tokens
 
    member this.next =
        let cur = Seq.nth !pos tokens
        this.move
        cur
 
    member this.is_symbol token = 
        token = times || token = plus || token = open_paren || token = close_paren
 
    member this.subexpr = 
        let balanced = ref 0
        let mutable ret = []
        let mutable cur = this.next
        while !balanced <> 0 || cur <> close_paren do
            if cur = open_paren then
                balanced := !balanced + 1
            if cur = close_paren then
                balanced := !balanced - 1
 
            ret <- cur :: ret
            cur <- this.next
 
        List.rev ret
 
    member this.interpret = 
        let sk = new System.Collections.Generic.Stack()
 
        while not this.is_done do
            let mutable cur = this.next
            if cur = open_paren then
                let sub = this.subexpr
                let result = (new Interpreter(sub)).evulate_expr sub
                if sk.Count = 0 || sk.Peek() <> times then
                    sk.Push(result.ToString()) |> ignore
                else 
                    this.do_multiply sk result |> ignore                    
            elif not (this.is_symbol cur) then
                if sk.Count = 0 || sk.Peek() <> times then
                    sk.Push(cur) |> ignore
                else
                    this.do_multiply sk (float cur) |> ignore
            else
                sk.Push(cur)
 
        this.do_sum(sk)
 
            
    member this.do_sum (sk : System.Collections.Generic.Stack) =
        let mutable sum = 0.0
        while sk.Count <> 0 do
            let elem = sk.Pop() 
            if not (this.is_symbol elem) then
                sum <- sum + (float elem)
        sum
 
    member this.do_multiply (sk : System.Collections.Generic.Stack) operand = 
        sk.Pop() |> ignore
        let operand1 = sk.Pop() |> float
        sk.Push((operand1 * operand).ToString()) |> ignore
 
    member this.evulate_expr (tokens : string seq) =
        let i = new Interpreter(tokens)
        i.interpret

(* the drive file, test program, Program.fs *)

open System
 
let main() = 
    let a = "6 * 3 + 2 * 5"
    let v = Select.max a
 
    Console.WriteLine(v) |> ignore
 
    let a = "0.1 * 0.1 + 0.1"
    let v = Select.max a
    Console.WriteLine(v) |> ignore
 
    let a = "-3 * 3 + 3"
    let v = Select.max a
    Console.WriteLine(v) |> ignore
    
    Console.ReadKey() |> ignore
 
do main()

Jingyi Wang is a developer for Fellowship Technologies. He has been with Fellowship Tech since August of 2005. He is passionate about improving himself and is always striving to write better code than the day before.

Posted In: News