One of the little tasks I typically force upon myself is a simple infix expression evaluator. For the uninitiated, 'infix notation' is the form of notation we humans commonly write our mathematical expression in - that is, the form "a + b * c" etc. Here's a wiki!
Anywho - I decided today was the time for F# to get its own infix evaluator...
Feel free to laugh. I'm laughing at myself, actually - way down inside, in the tiny places, where I harbor my self-loathing and self-doubt, down where I quietly plot my own demise... *ahem*
It took me about 7 hours today to write a total of 95 lines of code. That's ~13 lines of code an hour. Horrible, horrible. Though I'm really not beating myself up as badly as you might think - it took me as long to write this evaluator in VB.NET when I was learning that language (though not nearly as long in C# due to the syntax being the only difference between the languages). I'm just not used to thinking recursively. Sure, I've done recursion in C#, VB.NET, etc., but I've never really used it to replace what would otherwise be imperative-style constructs before. I've only used it when something *had* to be recursive. Also I wanted to adhere to the pure functional programming dogma - zero side effects. This code does indeed adhere to this self-imposed mandate.
Before I post the code, I want to stress that this is *not* optimal code. I know a little about tail recursion, etc., but I *clearly* didn't use it here. I don't even know if I *can* use it here. Also I'm not terribly knowledgeable about the various Seq and List functions that are available, so I probably flubbed them up as well. I don't really care - this works, and I'm proud of it. This is my first major attempt at writing something of any facility in a functional programming language. Also I'd like to mention that I am *very* open to suggestions. If I did something really, truly stupid in here, please call me on it. This is a learning exercise, and I'd like to learn as much as I can from it - part of that is peer review.
So, without further ado, here it is. (Apologies for the different theme - I'm doing this at home and haven't gotten around to installing the darker theme yet.)
3 open System
5 type operator =
6 | Add
7 | Subtract
8 | Multiply
9 | Divide
11 type token =
12 | Number of int
13 | OpenParen
14 | CloseParen
15 | Operator of operator
17 let tokenize i =
18 let rec tk s =
19 match s with
20 | ' ' :: tail -> tk tail
21 | '(' :: tail -> OpenParen :: tk tail
22 | ')' :: tail -> CloseParen :: tk tail
23 | '+' :: tail -> Operator Add :: tk tail
24 | '-' :: tail -> Operator Subtract :: tk tail
25 | '*' :: tail -> Operator Multiply :: tk tail
26 | '/' :: tail -> Operator Divide :: tk tail
27 | n :: tail when Char.IsNumber(n) ->
28 let rec intListToValue (i:int list) acc c =
29 match i with
30 |  -> acc
31 | n :: tail -> intListToValue tail (acc + (n * int (10.0 ** float c))) (c + 1)
32 let rec tc (i:int list) (n:char) (s:char list) =
33 let value = Int32.Parse(string n)
34 match s with
35 | n :: tail when Char.IsNumber(n) -> tc (value::i) n tail
36 | x :: tail -> (Number (intListToValue i value 1)) :: tk (x :: tail)
37 |  -> [Number (intListToValue i value 1)]
38 tc  n tail
40 |  -> 
41 | n :: _ -> failwith ("Parse error - invalid character detected: " + n.ToString())
42 tk (Seq.to_list i)
44 let evalTokens input =
45 let pop2 (stack:'a list) = (stack.Head, stack.Tail.Head, stack.Tail.Tail)
47 let eval a b op =
48 match op with
49 | Operator Add -> b + a
50 | Operator Subtract -> b - a
51 | Operator Multiply -> b * a
52 | Operator Divide -> b / a
53 | _ -> failwith "error parsing input"
55 let rec eval_rec input numstack (opstack:token list) =
56 match input with
57 | Number n :: tail -> eval_rec tail (n::numstack) opstack
59 | Operator op :: tail ->
60 if opstack.Length <> 0 && opstack.Head > (Operator op) then
61 let firstNum, secondNum, numstackRem = pop2 numstack
62 let e = eval firstNum secondNum opstack.Head
63 eval_rec tail (e::numstackRem) (Operator op::opstack.Tail)
65 eval_rec tail numstack (Operator op::opstack)
67 | OpenParen :: tail -> eval_rec tail numstack (OpenParen::opstack)
69 | CloseParen :: tail ->
70 match opstack with
71 | Operator op :: opsTail ->
72 let firstNum, secondNum, numstackRem = pop2 numstack
73 let e = eval firstNum secondNum (Operator op)
74 eval_rec input (e::numstackRem) opsTail
75 | OpenParen :: _ ->
76 eval_rec tail numstack opstack.Tail
77 | _ -> failwith "error parsing input"
79 |  ->
80 match opstack with
81 | Operator op :: tail ->
82 let firstNum, secondNum, numstackRem = pop2 numstack
83 let e = eval firstNum secondNum (Operator op)
84 eval_rec  (e::numstackRem) tail
85 |  -> numstack.Head
86 | _ -> failwith "error parsing input"
88 eval_rec input  
You call this like so: evaluate "((1 + 2) * 3) / 3" -- this would, of course, evaluate to 3, as expected - it understands and follows the correct order of operations, and respects parenthesis correctly as expected. It doesn't yet handle floats, but I might get around to that at some point. It'll complicate the parsing, but that's not really that big of a deal. The way I'm handling it is weird anyway...
Well there you have it. My first real F# program of any value at all. Despite taking me 7 hours, I'm rather proud of this. It's taught me a great deal, especially that I need to be patient with myself while trying to learn to think in functions. Also, staying pure and functional can be *hard*, especially coming from an imperative / mutable state world. I should also note that my first C# implementation included around 4 times the number of lines of code...
All told, I really enjoyed my dive into F#. My advice to anyone looking into it as a real programming language (and not as a toy) would be to keep an open mind and give it a fair shot.