Huffman Coding, SICP Exercise 2.69

As a convenience, I defined Incidence as System.Collections.Generic.Dictionary. F#'s Map type
is actually a functor, and each insertion or removal returns a new instance. What I'd really like is something like the FindOrAdd() method available in the C5 dictionary implementations, but I can live without it. Anyway, I intend to fold a sequence of characters into a dictionary, for which purpose I'll first define the function that will do the folding:

> let count (d : Incidence) (c : char) =
-     let n = ref 0
-     // I need a "ref" variable to serve as an "out" parameter.
-     if d.TryGetValue(c, n) then
-         // Assign to a mutable property...
-         d.[c] <- !n + 1 
-     else 
-         d.Add(c, 1) 
-     d;;  
val count : Incidence -> char -> Incidence

I'm getting good at this:

> let d = "Tony Nassar, Software Engineer" |> Seq.fold count (new Incidence());;

val d : Incidence

> d;;
val it : Incidence
= dict
    [('T', 1); ('o', 2); ('n', 3); ('y', 1); (' ', 3); ('N', 1); ('a', 3);
     ('s', 2); ('r', 3); (',', 1); ('S', 1); ('f', 1); ('t', 1); ('w', 1);
     ('e', 3); ('E', 1); ('g', 1); ('i', 1)]
>

I did not know until today that System.String implements IEnumerable! And, fortunately, F#'s type inference lets me pipe that sequence of characters into my count() function. There are two steps that I need to take now: I need to create a sequence sorted by frequency (actually, a mapping from frequency to character, where the frequencies don't have to be unique) and turn it into a tree. This took me a while. Unlike C#, F# only allows mutually recursive type definitions if they're linked with "and." Here I'm declaring HuffmanNode as a "discriminated union," where Leaf and Tree are implemented as tags (you can verify this by using Reflector to examine the compiled DLL), and a leaf consists of the character to be encoded and its frequency (the latter is necessary during the construction of the tree), and a tree (or any non-leaf node) is...well, it's kinda obvious. If this were C, and someone were using a union and a type code, I'd say "Yuck!" But since it's functional programming, and this is a very handy way to build up a tree, it's suddenly cool again.

> type HuffmanNode =
- | Leaf of HuffmanLeaf
- | Tree of HuffmanTree
- and HuffmanLeaf = { Count : int; Char : char }
- and HuffmanTree = { Count : int; Chars : CharSet; Left : HuffmanNode; Right : HuffmanNode };;

type HuffmanNode =
  | Leaf of HuffmanLeaf
  | Tree of HuffmanTree
and HuffmanLeaf = {Count: int;
                   Char: char;}
and HuffmanTree = {Count: int;
                   Chars: CharSet;
                   Left: HuffmanNode;
                   Right: HuffmanNode;}

>

Eight Queens in F#

Man, I'm really going back to school here. The last time I did this problem was when I was learning Prolog. Let's say you're trying to place a queen in the first column. Prolog's select function will pick one of the rows, and create a branch to explore the remaining rows. If row 3 was selected, say, you don't have to write any code to concatenate [1..2] and [4..8], in order to pass that smaller set of unoccupied rows to the next iteration / recursion. Very handy! No loops, no list operations, etc.

> #light;;
> type Position = int * int;;

type Position = int * int

> let safe p q =
-     fst p <> fst q && snd p <> snd q && fst p + snd p <> fst q + snd q && fst p - snd p <> fst q - snd q;;

val safe : int * int -> int * int -> bool

> let all_safe p positions =
-     Seq.for_all (safe p) positions;;

val all_safe : int * int -> #seq -> bool

> all_safe (1, 2) [(1, 2)];;
val it : bool = false
> all_safe (1, 2) [(3, 3)];;
val it : bool = true

> let range = [1..8];;

val range : int list

> range;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8]
> let queens size =
-     let range = [1..size]
-     let rec queens' columns answers =
-         match columns with
-         | [] -> answers
-         | column::tail -> queens' tail [for answer in answers for position in [for row in range -> (column, row)]  when all_safe position answer -> position::answer]
-     queens' range [[]];;

val queens : int -> (int * int) list list

> queens 4;;
val it : (int * int) list list
= [[(4, 3); (3, 1); (2, 4); (1, 2)]; [(4, 2); (3, 4); (2, 1); (1, 3)]]
>

Implemented recursively, it's:

> let queens size =
-     let range = [1..size]
-     let rec queens' columns =
-         match columns with
-         | column::tail -> [for answer in (queens' tail) for position in [for row in range -> (column, row)]  when all_safe position answer -> position::answer]
-         | _ -> [[]]
-     queens' range;;

val queens : int -> (int * int) list list

> queens 4
- ;;
val it : (int * int) list list
= [[(1, 3); (2, 1); (3, 4); (4, 2)]; [(1, 2); (2, 4); (3, 1); (4, 3)]]
>