Programming in F#
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(* file interpreter.fs *)
) = 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]
(* the drive file, test program, Program.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
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,
- Include Requirements & Contribution Sub Types
- User Case Story from Hope Community Church
- Group Search Categories and More
- Account Creation
- Single Sign On Functionality Exposed
- API Communication Value Changes
- API Enhancement: Create and Edit Groups!
- API Enhancement: Requirements Exposed
- Resource Versioning
- Enter Visitor Data via Your Church Website
- Fellowship One & Planning Center Online
- API Libraries and Sample Code
- Building a custom login for your church website using the API
- Roll Foward!
- The Agile Triangle
- Conversation Paralysis
- Picture this, image updates & creates through the REST API
- A REST API double shot : Groups and Events realms
- Increasing Software Delivery by 500%
- Quick people API realm update
- Introducing the new REST API giving realm
- Raising the bar…
- Building a Deployment Pipeline
- The World of Dev Craft
- Running Tests in Parallel with Selenium
- Abstracting Your Code to Remove Duplication
- Documentation in an Agile Environment
- Drowning in Debt
- Intro to Ruby on Rails
- API Strategy & Roadmap
- Staging/Sandbox Environment is Back up!
- Downtime in Sandbox/Staging Environment
- Android & OAuth
- F1 API Static Library with Objective-c
- Programming in F#
- NoSQL: HuMONGOus Benefits (Part 2)
- Our Scrum Team Structure
- SaaS & BI - The History & Future
- Getting Started with Android
- NoSQL: Leaving Schema Behind (Part 1)
- Your Feedback…and a $25 Gift Card!
- A Scrum Ceremony? Is this a wedding or something?
- Variables in PHP
- Data Exchange API Fixes
- F1 Check-in on the iPad
- Be the first to get the news & tips!
- An Introduction to PHP
- Working with Pop Up Windows in Selenium
- List Comprehension
- Source Control: A Time Machine For Your Source Code
- Developer Conference…Lower Price, Same Great Content!
- The Quality Assurance Team
- How does Fellowship Technologies manage complex projects?
- Developer Conference coming in May!
- Sandbox Refresh Complete
- Sandbox Refresh This Week
- Updates coming to the REST API
- Sandbox Environment Down Time
- F1Touch :: Fellowship One On The Go
- Under the Hood
- Sandbox Refresh Complete
- Sandbox Refresh Tomorrow (Oct. 2nd)
- Fellowship One Developer Forums
- Ten Commandments of API Consumption
- REST API Enhancements / Fixes deployed to Sandbox and Production 09.09.09
- Data Exchange URL cut-over complete
- Important Data Exchange URL changes
- Ron Nom Nom
- How to get started using the REST API