Seth Juarez

During a recent assignment, I found the need to create a quick word lookup from an ordered dictionary file. I post the following:

   1: #light

   2: open System

   3: open System.IO

   4:  

   5: let rec line (s : StreamReader) (sawEol : bool) (acc : string) = 

   6:     match (char.ConvertFromUtf32(s.BaseStream.ReadByte())) with

   7:     | "\n" when (not sawEol) -> line s true ""

   8:     | "\n" when sawEol ->  acc

   9:     | str -> line s sawEol (acc + str)   

  10:  

  11: let rec binarySearch (s : StreamReader) (target : string) 

  12:                      (low : System.Int64) (high : System.Int64) =

  13:     let mid = Int64.shift_right (low + high) 1 in

  14:     let pos = s.BaseStream.Seek(mid, SeekOrigin.Begin) in 

  15:     let cur = (line s false "") in

  16:     printf "Current: %s\n" cur;

  17:     if (high < low) then

  18:         Int64.zero

  19:     elif (String.CompareOrdinal(cur, target) > 0) then

  20:         binarySearch s target low (mid - Int64.one)

  21:     elif (String.CompareOrdinal(cur, target) < 0) then

  22:         binarySearch s target (mid + Int64.one) high

  23:     else

  24:         mid

  25:  

  26: let isValidWordFromFile (filename: string) (word : string) =

  27:     let fileInfo = new FileInfo(filename) in

  28:     let size = fileInfo.Length in

  29:     use stream = fileInfo.OpenText() in

  30:     let res = (binarySearch stream word Int64.zero size) in

  31:     not (res = Int64.zero)

  32:  

  33: let output = isValidWordFromFile "dictionary.txt" "entropies";;

  34: printf "Found: %s\n" (any_to_string output);;

  35: Console.ReadKey();;

Let me describe what is happening. I have found that as I learn to write stuff functionally, I tend to do things from a top down approach but write it bottom up.  The isValidWordFromFile function simply gets everything set up. Note the use keyword in 

   1: use stream = fileInfo.OpenText() in

This is similar in nature to the using statement in C#: It ensures that the stream is disposed of after use. The two functions of interest are the binarySearch and line functions. The rec keyword makes both functions recursive in F#. The binarySearch function in essence keeps "halving" the dictionary file by seeing if the word is either a match, too "large" or too "small". If it is too large, it resumes the "halving" process but on the lower half of the file. If it is too small, it resumes the "halving" process on the upper half of the file.

When I originally started, I attempted to use the Stream.BaseStream.Seek method in conjunction with the Stream.ReadLine() in the binarySearch function. This was not functioning correctly. After calling Seek on the BaseStream, the current file position was set correctly. Calling Seek thereafter yielded no results. In comes the line method. I like this method because it truly shows the power of a functional language. It in essence takes a stream and spits out a complete line. Since it is possible that the file Position is in the middle of a line, it is important to actually retrieve the next complete line. The acc variable is an accumulator for each byte that is going to be the eventual string. The sawEol variable simply tells the function whether or not it saw an end of line character. The match construct takes the byte at the current position and sort of does a C# switch on it. I say sort of because this match construct is a lot more powerful than a simple switch. The first case is when it sees a "\n" AND has not seen an end of line character yet. This means that it is not yet time to start accumulating characters. If we see a "\n" AND have seen an end of line already, that means we have completely read an entire line. This essentially ends the recursion. If it is some other character, add it to the accumulator variable and keep going.

In summary, I am extremely impressed with the functional programming paradigm. It seems simpler when I'm finished with something useful. The problem I have been encountering is wrapping my imperative mind functionally.