The Last Pickle

Patterns in F# are kind of like switch statements in C#, but much more powerful. For my first experiment with them I decided to see if I could find a word in a sentence. This is definitely the wrong way to go about solving this problem, calling String.Contains() would be easier. But I am still very much learning the language and this is the first step in investigating whether patterns would be of use solving another problem I have in mind.

So with that in mind lets get started in F# interactive mode and the #light syntax.

My first draft was not pretty, but it worked and got my head into the game. The algorithm involves examining the elements of a list one by one and comparing the value to the value of a variable.

#light;

> let sentence = "there is a red dog";;
val sentence : string

> let tokens = sentence |> String.split [' '];;
val tokens : string list

> tokens;;
val it : string list = ["there"; "is"; "a"; "red"; "dog"]

> let find = "red";;
val find : string

> let rec search tokens find= 
 match tokens with
 | [] -> "no match"
 | h::t when h = find -> "match"
 | h::t -> search t find;;

val search : 'a list -> 'a -> string

First I defined and initialized the value sentence with the string I wanted to search, letting the compiler correctly infer the type to be string. The value of sentence was then passed as the last argument to the String.split function using the pipeline operator (|>). The first argument passed was a list containing the delimiters to split the string on, in this case just the space character. The result of calling split is another list containing the words split from the sentence; executing tokens;; in the interactive session returns the value.

The value to search for was stored in the variable ‘find’. I’m trying to avoid calling variables ‘variables’ as by default they are immutable in F# and so cannot be changed. So I tend to think of them more like values with a name, but this seems to make things a little confusing at times.

Then I defined the function search using the rec modifier to instruct the compiler to allow recursive calls. The function takes two parameters, the first is the list to search and the second is the value to search for. The match statement has three patterns, one of which makes a (tail) recursive call to continue processing the list of words. Recursion was probably not the best construct to use but I wanted to see how it works in F#. The three patterns are evaluated in order and work as follows.

1. Match on an empty list, execute the expression to return the string “no match”
2. Match on a list with at least one element, bind the head of the list to h and the remainder of the list to t. If the value of h is equivalent to the value of ‘find’ execute the expression to return the string “match”
3. Match on a list with at least one element, bind the head of the list to h and the remainder of the list to t. Make a recursive call to search and pass the tail (t) of the list.

Some simple tests showed to function to be working as expected.

> search tokens find;;
val it : string = "match"

> let find = "blue";;
val find : string

> search tokens find;;
val it : string = "no match"

Function Values

That worked as a first draft but it was not very nice, so I set about it with my refactoring stick.

The first thing I did was to modify the search function to return a boolean. I did not have to explicitly say it returned a boolean value, just change the string return values to the boolean constants and the compiler worked it out. Otherwise the search function itself was fine.

> let rec search tokens find = 
 match tokens with
 | [] -> false 
 | h::t when h = find -> true
 | h::t -> search t find;;
val search : 'a list -> 'a -> bool

As well as inferring the return type the compiler was also able to automatically generalize the function. There was nothing in the search function that required the value of find or the list of tokens to be a strings. So the compiler created a function that accepts a list of a generic type (”‘a list”), a single value of the same generic type (”‘a”) and returns a boolean value (bool).

Next I used partial function application / currying to create a function that accepts a string sentence to search in and returns an anonymous function. The code in the wordSearch function to split the sentence is only executed once, and only when the anonymous function is executed. At the moment I don’t understand the language enough to explain why, but the key element to achieving this result is the anonymous function requiring a parameter to be passed.

> let wordSearch s = 
 let tokens = String.split [' '] s
 fun (word: string) -> search tokens word;;
val wordSearch : string -> (string -> bool)

> let s = wordSearch "there is a red dog";;
val s : (string -> bool)

> s "red";;
val it : bool = true

> s "blue";;
val it : bool = false

Next I hope to modify the function to search the list of tokens for any element from a list.