# F# | Word Search Kata Summary

Recently I decided to start learning F#. In this blog post I will try to desribe my journey with a first bigger kata made by me. It was supposed to be a small and simple kata, but I ended up with a much bigger and more complex code than I was expecting. The whole exercise took me about 20 hours, distibuted over about two weeks. Repository with code can be found on my GitHub, here.

At the beginning I’d like to thank Bizmonger (Scott Nimrod) for helping me with this exercise. Without him I wouldn’t be able to do this whole thing. And here’s a link to his twitter, drop him a follow, he’s a really helpful guy :)

The kata I was doing is called `Word search` and you can find it on exercim

Here’s a description of this kata:

``````Introduction
In word search puzzles you get a square of letters and have to find specific words in them.

For example:

jefblpepre
camdcimgtc
oivokprjsm
pbwasqroua
rixilelhrs
wolcqlirpc
screeaumgr
alxhpburyi
jalaycalmp
clojurermt

There are several programming languages hidden in the above square.

Words can be hidden in all kinds of directions: left-to-right, right-to-left, vertical and diagonal.

Given a puzzle and a list of words return the location of the first and last letter of each word.
``````

# Example test cases provided by kata

It should find a word left to right, right to left, words in up - down axis and also diagonal words in every direction.

``````[<Fact>]
let ``Should locate one word written left to right`` () =
let grid = ["clojurermt"]
let wordsToSearchFor = ["clojure"]
let expected = [("clojure", Some ((1, 1), (7, 1)))] |> Map.ofList
search grid wordsToSearchFor |> should equal expected
``````

An example of more complex test would be this one:

``````[<Fact>]
let ``Should fail to locate a word that is not in the puzzle`` () =
let grid =
[ "jefblpepre";
"camdcimgtc";
"oivokprjsm";
"pbwasqroua";
"rixilelhrs";
"wolcqlirpc";
"screeaumgr";
"alxhpburyi";
"jalaycalmp";
"clojurermt" ]
let wordsToSearchFor = ["clojure"; "elixir"; "ecmascript"; "rust"; "java"; "lua"; "lisp"; "ruby"; "haskell"]
let expected =
[ ("clojure", Some ((1, 10), (7, 10)));
("elixir", Some ((6, 5), (1, 5)));
("ecmascript", Some ((10, 1), (10, 10)));
("rust", Some ((9, 5), (9, 2)));
("java", Some ((1, 1), (4, 4)));
("lua", Some ((8, 9), (6, 7)));
("lisp", Some ((3, 6), (6, 3)));
("ruby", Some ((8, 6), (5, 9)));
("haskell", Option<((int * int) * (int * int))>.None) ]
|> Map.ofList
search grid wordsToSearchFor |> should equal expected
``````

In my solution, I went off-the-track a little bit. At some point I decided to stop trying to fit into this tests and the domain created by this kata, and I started to treat this requirements as a loose direction in which I should go. The dirrerences between final solution and kata requirements is a slightly different contract (I’m capable of searching only a single word), and instead of returning a position of a given word, I’m just returning a true / false whether the word has been found or not. All differences are I’d say not-that-hard to change so that all the kata requirements would be fulfilled, but I haven’t decided to try to do this as for now.

# Overview of my solution

The solution consists of three projects:

• Interpreter
• That’s where the whole logic is
• Specification
• I have my domain types in here, both tests and interpreter depend on specification
• Tests
• A project for tests

### Types

I’ve created some simple and complex types to help myself with implementation (more on this in DDD paragraph). Some of them are:

• `Word (string)` - a word I’m looking for
• `SingleLine (string)` - a single line within grid (may be horizontal / vertical / diagonal line, converted into a string type)
• `Grid (SingleLine list)` - a list of single lines (horizontal lines in this case)
• `Index (int)` - an index (horizontal or vertical) within grid
• `Coordinate (Index; Index)` - a coordinate within grid
• `FirstLetter (char)` - a first letter of a word I’m looking for. Used as a part of my algorithm.
• `Coordinates (Coordinate list)` - a set of coordinates, used to keep position of letters found at the grid. If within grid there is more than one FirstLetter, I get more than one Coordinate

### Algorithm

The whole idea of this solution was pretty simple:

• Get a Word’s FirstLetter
• Find all accurences of FirstLetter within grid.
• Using a recurring function, find all chars between FirstLetter’s position and adge of the grid. Do it in all directions, and persist this characters as SingleLines
• Since I’ve got SingleLine for every direction, starting with FirstLetter, I just need to take this list and apply a `List.Contains` to determine whether there is a Word in a grid or not.

My modules:

• `WordSearch`: top - level module. It has main `find` function, and it also does logic of finding Word within SingleLines
• `Straight` and `Diagonal`: given a `Grid` and `FirstLetter`, it returns a list of `SingleLine` in a given directions (straight or diagonal)
• `LineGetter` and `Coordinates`: modules shared between `Straight` and `Diagonal`, with functions used to find first letter of Word and transforming this `Coordinate` into list of `SingleLine` in every direction
• `Converters`: helper module, doing convertions between my types

# DDD

### Wrapping simple types into domain types

In F# it is possible to warp a simple type into my custom domain type, which in my case, for example chages a simple `string`, which by itself represents only a set of characters, into a `Word`, which is exactly the same type as `string`, but represents the word I’m looking for. Also, there’s another custom type, called `SingleLine`, which in also of type `string`, but it represents a single line within a grid. Using this technique, the compiler helps me by checking if the function expecting a `Word` gets exactly the same type I’m expecting, since if it recieves a `SingleLine`, which under the hood is the same simple type `string`, just with some ‘alias’ on top of it, the code will not compile. This way I cannot acidentally pass wrong type into my function.

### Creating complex types

F# is capable of not only wraping simple types, but is also great at aggregating this simple types into a more complex types.

``````type Submission =
{
Grid : Grid
Word : Word
}
``````

The type `Submission` consists of:

• `type Grid = SingleLine list`
• `type SingleLine = string`
• `type Word = string`

What it means is that `Grid` is a `List of string` and `Word` is a `string`, but since it’s type - safe, I’m unable to put a `SingleLine` into `Word` field just by mistake, it just won’t compile. The same way, I’m unable to put a `Word` into a `Grid`.

The above type is called a `record`, but there are more cool complex types. In this project I used also `discriminated union`.

Discriminate union:

``````type Directions =
| Diagonal of DiagonalDirections list
| Straight of StraightDirections list
``````

Types used in discriminated union:

``````type DiagonalDirections =
{
NE : SingleLine
NW : SingleLine
SE : SingleLine
SW : SingleLine
}

type StraightDirections =
{
Up : SingleLine
Down : SingleLine
Left : SingleLine
Right : SingleLine
}
``````

What it means is that I’ve got a type called `Directions`, which contains either `DiagonalDirections list` or `StraightDirections list`. I’m using `Directions` as a type returned by a `GetLine` function, which can be used in two contexts - straight and diagonal. This way I can return a type, which has different meaning in a different context.

# TDD

### Using TDD to incrementally build the application

I’ve started from the hardest task - getting diagonal single lines. The idea behind it was that if I was able to convert letters from a grid placed diagonal into a single string or a list of strings, then getting a ‘straight’ (up / down / left / right) lines should be a piece of cake. It later appeared to be true (partially), from the point of view of my algorithm. Getting diagonal lines was the hardest thing, and having it done I was able to take a ‘ready-to-go’ solution and almost immediately (with minor changes) apply it to getting straight lines.

I started with a simplest of the hardest case - given a word which was starting in top left corner of a grid, I wanted to return a single line that goes in bottom right direction. That was my basline, on top of which I built up the rest of the algorithm.

First, I started with implementing a failing test:

``````[<Fact>]
let ``Given a grid and a word, it should return diagonal bottom right starting with words first letter``() =

let grid = [ "abc"
"def"
"ghi" ]
let word = { FirstLetter = 'a' ; Remaining = ['x' ; 'y'] }

let submission : FirstLetterSubmission =
{ Grid = grid
Word = word }

let expected =
[ { SE = "aei" } ]

// Act & Assert
submission
|> Diagonal.singleLines
|> should equal expected
``````

As soon as I has this test passing, I added another test - the one checking if the function `singleLines` works properly for a different index than (0, 0). It turned out that it doesn’t work properly, but fortunatelly I had a test proving me that it’s wrong, and it turned green as soon as I fixed this problem. After adding line one more test for this single - direction case, I added to `expected` variable more cases - so it checked for single lines going in all directions.

``````let expected =
[ { NW = "a"
NE = "a"
SW = "a"
SE = "aei" } ]
``````

As soon as this test was passing, I was able to use a similar approach to a vertical and horizontal `singleLines` function. Starting small, I incremetally made tests pass, as I was building up my solution.

After I had all tests confiming that both diagonal and straight single lines are being fetched correctly, I added an end-to-end test, which returned true or false, depending on whether the word I was looking for was present at the grid or not.

After I made this test pass, I added some more tests for happy path (find diagonal word, given it exists in a grid, find horizaontal work given it exists in a grid) and at the end I added a test for a sad path (find a word given it does not exist). Fortunaltelly, the last 3 tests were green from the beginning.

And as a last thing, a test coverage of the whole solution. I’m pretty satisfied with this coverage (it’s really high, but it’s because this is a simple and small project), and also this tests saved me some work, by just failing after doing some changes, so i could fix them immiediately.

# Surprises of F#

I’m working as a C# developer. In this chapter I’ll try to describe things which was unexpected for me, or not-that-easy to adapt by my brain.

### Unable to reference code that is above

This one is pretty obvious, but it surprised me a lot. In C#, folders and files are sorted alphabetically

In F#, folders and files are sorted in the way you organize them. You can move them up and down as you wish, and they will stay where you dropped them. It was kinda strange at first, but after a while it totally made sense, since in F# it’s impossible to reference anything from above.

### Program.fs has to be at the end of the whole solution

I was struggling with this one way to much. I realised right now (writing this words it just ‘clicked’) why it is required to have `Program.fs` at the end of solution - it’s related to the previous point - an entry point of a F# solution, witch is `Program.fs`, needs to have an access to all the code it’s using. So naturally, it has to be the last file.

### F# coding conventions

It wasn’t much of a purprise, but I’m still struggling with this one. I still tend to mix `PascalCase` (used in type names) with `camelCase` (used in function names. But this is my day-to-day struggle, since I also tend to mix things up in C#, in which I already shouldn’t do such mistakes ;)

### Type inference

Really hard understand, really helpful as soon as I figured it out. There are written type names above every function (this little gray letters), it’s a concept called ‘type inference’.

At first it seemed like a black magic to me. Only after some time it started to make sense. The compiler can be privided with a signature it should apply for a given function (like in first screenshot), or can determine types by itself (return value in second screenshot). It can be thought of as a function signature.The first part represents parameters, and the last type is a type returned by function. In the above example, we can see that a function named `getSingle` takes a tuple as a parameter [`*` symbol represents that it’s a tuple]. The tuple is made of given types:

• Grid
• Coordinate
• a function taking `Coordinate` as a parameter and returning `Coordinate` and returns a variable of type `string`.

This above function is a bit simpler, it takes a parameter of a type `FirstLetterSubmission` and returns a list of `Coordinate` type. As you can see, there is no implicitly defined type returned by this function, but compiler managed to figure it out by itself.

It is also useful when I’d like to create a new function. Instead of writing the whole function signature, I could just write a function and use it. Compiler will help me with determinig function signature via type inference. This made some things easier, to start with function of an empty signature and just check if types are correct or not.

### Type as interface

If F# there’s an interesting concept of interface - it’s done by creating a `type` with a signature of a function, which represents the transformation that function makes. In other words, it’s a function signature, written in the same way as type inference.

In here I’ve got a type `GetDirections`, which defines a signature of a function implementing it. Then there’s a `getDirections` function, which implements `GetDirections` type, so it transfroms a `Submission` type into an option of `Directions`:

``````type GetDirections = Submission -> Directions option
``````
``````let getDirections : GetDirections = (...)
``````

Later, the `GetDirections` type is used in a `GetLine` fuction, as a parameter. It means, that I can pass a function fulfilling the signature of a `GetDirections` type into `GetLine` function to change the behaviour of `GetLine` function.

``````type GetLine = GetDirections -> Submission -> Directions option
``````

Final usage of `GetLine` function is presented below. I’ve got a `directions` function, which fulfills the `GetLine` type, and then is used in `getLinesInAllDirections`. It’s used in two places: `|> directions Diagonal.getDirections` and `|> directions Straight.getDirections`, so I’m using directions function with two different behaviors injected (it’s a strategy patter). It’s capable of getting both diagonal and straight directions, depending on a function it gets.

``````let directions : GetLine =
fun fn submission ->
fn submission

let getLinesInAllDirections (submission : Submission) =
{ Lines =
submission
|> directions Diagonal.getDirections
|> function
| Some x -> Converters.directionsIntoSingleLinesList x
| None -> []
|> List.append (
submission
|> directions Straight.getDirections
|> function
| Some x -> Converters.directionsIntoSingleLinesList x
| None -> [])}
``````

### Using pipe operator where it is possible

F# heavily depends on pipe operator `|>`. This operator passes a value from a previous function or variable into another function. This below is a code from one of my tests. In first version passes a `submission` parameter to a function `find` from a module `WordSearch` in a ‘regular’ way, in the second version it passes the same parameter using a pipe operator. I’ve got an impression that the second way of doing this is more ‘correct’, or maybe should I call it ‘more functional’?

``````WordSearch.find submission
|> should equal expected
``````
``````submission
|> WordSearch.find
|> should equal expected
``````

Also, as a side note, module name can be omitted. If only there’s no names conflict, I could go with code like this:

``````submission
|> find
|> should equal expected
``````

### Using modules as syntax

This thing was also quite new to me - module name at function call is an optional thing. It can be used when it improves readability, but also can be omitted when it feels redundant and not adding an value to the code.

``````submission
|> Diagonal.singleLines
|> should equal expected
``````

In the above example, the `Diagonal` part is totally optional and can be omitted.

Written on April 26, 2020