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.)

1 #light

2

3 open System

4

5 type operator =

6 | Add

7 | Subtract

8 | Multiply

9 | Divide

10

11 type token =

12 | Number of int

13 | OpenParen

14 | CloseParen

15 | Operator of operator

16

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

39

40 | [] -> []

41 | n :: _ -> failwith ("Parse error - invalid character detected: " + n.ToString())

42 tk (Seq.to_list i)

43

44 let evalTokens input =

45 let pop2 (stack:'a list) = (stack.Head, stack.Tail.Head, stack.Tail.Tail)

46

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"

54

55 let rec eval_rec input numstack (opstack:token list) =

56 match input with

57 | Number n :: tail -> eval_rec tail (n::numstack) opstack

58

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)

64 else

65 eval_rec tail numstack (Operator op::opstack)

66

67 | OpenParen :: tail -> eval_rec tail numstack (OpenParen::opstack)

68

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"

78

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"

87

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.