# Programming in F#

Posted By: Jingyi

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, No one has commented yet. Be the first!
Commenting is not available in this channel entry.