Learn how to associate every character on the word grid with a set of coordinates such as (2, 3) pointing at its position by row and column. You can accomplish this by learning more about Haskell's list type, including how to work with infinite lists, repeat values, iterate them with the List monad and list comprehensions, and join lists together with zip.
- [Instructor] In this section we're going to look at polishing the word game. We're going to be making the game complete, and by doing that we're going to start by adding coordinates to the grid, we're going to look at working with infinite lists in more detail than we have done so far. We're going to create another recursive function, we'll be looking at modeling the game, so we're going to use Haskell's powerful data types and see how to apply that to a piece of extended code. We'll make the game playable, and that means finally dealing with the IO Monad, and we will add random letters to the grid, turning it into the proper jumble that we normally see.
In this video we're going to add grid coordinates, and to do that we'll explore infinite lists. So we're going to explore the features and the functions to deal with infinite lists, in particular we'll look at list comprehensions and we'll look at various functions such as repeat, and we will look at the zip function which will allow us to do various things, combining rows and columns of a list, and also working over two-dimensional grids.
So as you can see, a coordinate locates a cell in a two-dimension space with the first value in this case, implying the row and the second value in the tuple being the column, and you can see that very clearly here, that the row is zero all along the top, and as you go down the grid it increments by one. Similarly for columns the column number is zero all along the left-hand side, and increments as you move towards the right of the grid, and we're going to be looking at adding that kind of grid to our code.
Because we're going to be doing a fairly extended parenthesis where we look at some features and functions that we haven't dealt with before, I'm not going to be working within my normal source labor.hs file, so I've created a stub file here called test.hs which will be in the Git repository so you can follow along. As you can see at the top of this I've simply defined a sample grid of coordinates, now we're going to be looking at generating that programmatically throughout this section, but just to start off with, here's a sample of it.
Because we're not including our own code, we do want to have a word grid to play with, and I've simply copied the one from data.hs, and here we have a function which I've named og, simply this means outputGrid, and this will show every line in the grid and then output it in a similar way to our previous function. The reason it's named og is I'm going to be typing it out many times throughout this tutorial, and so it makes sense to give it a very short name for convenience.
So if we open our test.hs we can see that we have a grid, and this is a demonstration of the og function, and if we output the coordinates, we can see that every line is a list of tuples of integers. So let's have a look at how we might generate those. So here is a list range expression, and you can see that this gives us the numbers from nought to seven. By giving two numbers at the beginning of the expression, we can actually skip over a range of values.
But Haskell also allows us to provide an infinite list by missing out the maximum value, and obviously this would take an infinite length of time to compute and to display, I've pressed Control + C to escape out of that list. So this might seem to be less than useful because we can't actually process it without spending an infinite amount of time, but if we only use the earlier values, for example we can run head against it and we could tail the list and get the first value of the new head produced by that, and so on.
Now obviously these expressions are slightly awkward, so Haskell provides us with a whole variety of functions. For example we can index into the list using the double exclamation-mark operator, and we can also take a finite number of values from the beginning of an infinite list, and if that's not powerful enough, we can run a function called takeWhile, which returns values while a condition is true.
Now functions that we've seen like map, we can run those against an infinite list as well, and you can see here that all of the resulting values were in fact multiples of two, it's clearer to see if we take a finite selection of those, and of course we can run all of the functions like takeWhile and so on against an infinite list. In this test.hs file I've defined a function called div2 which checks if a value is divisible by two, that is if the modulus after division by two is zero.
So for example, div2 of 10 is true, 10 is divisible by two, whereas nine is false, as nine is an odd number. So we can also filter a list, this is very similar to map in that we give it a predicate, but the predicate needs to return a Boolean, as does div2, so we can filter by div2 and again, we can give an infinite list, and you can see here that all of these values are in fact multiples of two, and of course we can turn that into a finite list by taking a finite number of values.
Now there are other ways of dealing with lists, and one very powerful one is the list monad, and we can use the do notation that we've previously seen while writing tests. Now in the do notation we can take values from a list using the left-pointing arrow operator, so here I'm assigning to the variable i from a list from zero to nine, and the return keyword means to return a value in the specific monad, so in this case return it back into the list monad, and I'm returning the value i times two, and when we reload we can see that the mapped value is the same as if we'd called map times two on that same list.
And of course, the list monad can also be used in an infinite way, and here you can see that there are at least 100 values available from it, and we can also write filter in exactly the same fashion. Again, we can iterate over a range, and we can now use what we call a guard clause, and what that clause will do is take a Boolean expression that tests the list, and let's have a look at its type. So first of all we need to import it, and now we can see that its type takes in a Boolean expression and returns an empty list in type f, and you can see the full IO, it may or may not raise an error, but in the case of list it will either return a list of one value, or a list of no values, and for Maybe it could return a Just value or a Nothing value.
So let's import Control.Monad, and we can see that in the case of list, returning that empty list in fact filtered the values from the expression. And finally we can combine the concepts of mapping and filtering within a single function. So although this is very powerful notation, it isn't especially compact, and Haskell gives us another option which is list comprehensions.
These are written in a very mathematical notation, we write it using square brackets, we have our returned value at the left, a pipe character, and then we have our left-pointing arrow expression, and we can add our guards with a comma after the list that we're iterating over. So let's have a look at our coordinates grid. As you can see the row number stays the same along the row, and the column number remains the same within a column of the grid.
If we wanted to use Haskell's list functions to generate a grid, we also need to look at repeating values in a grid. As you can see the repeat function will return an infinite list of a single value. There's also a cycle function which allows us to pass in a list, and each value of that list will be repeated over and over, and of course that doesn't mean that cycling over a list of a single element is essentially the same as the repeat function.
If we map repeat over a list, let's make that finite to make it more easily displayable here, we can see that we get a list with ones on the first row, twos on the second, threes on the third, and so you can see that this is very similar to the list of row numbers that we need for our grid. Now let's have a look at the zip function.
As you can see this takes a list of a certain type, a, another list of perhaps a different type, b, and it will return a list of tuples of type a and b, so that means for example that we could zip a list of numbers from one to 10, and a list of letters from a to j, and zip will return a list of tuples of one and a, two and b, three and c, and so on.
Now I wrote a to j because j is the 10th letter, but in fact if we provided a later letter, z, we would get the same list because zip stops processing the list once any one of the lists is exhausted. So we could use an infinite list on one side, if we had an infinite list on both sides then of course zip will carry on processing values as long as it can, but it does show that we can work with an infinite zipped list, again, by using functions such as take.
So if we look at coords, how would you generate that list of coordinates? One very common way might be to use the list looping construct as we saw with this list monad notation. So we might create a new variable coords2, and we would iterate over row from nought to seven, col, again from nought to seven, and we might return the row and the column as a tuple, and let's see what that looks like as a first attempt.
So there's coords, and you can see that it has each row within a list, and coords2 in fact has exactly the same numbers, so you can see there nought, seven followed by one, zero, however they're not nested in a new list. So let's try nesting our loop by adding a new do...
And that still hasn't quite worked, so if you remember that return wraps a value in the list monad, what we need to do here is to return the entire content of the inner do expression within the list monad, i.e. by wrapping it within a list, and now we have an outer list which contains repeated iterations of the inner list on every row.
And of course we can rewrite expressions in the list monad as a list comprehension. So we know that we want to return a tuple of row and column, and that we iterate the column over the numbers nought to seven, and the row over the numbers nought to seven, but of course this expression suffers from exactly the same problem that we had with our first attempt with the list monad notation, so again we need to wrap the inner statement in a nested list comprehension.
I'm not going to use list comprehension syntax for much of this tutorial, but I hope that this introduction has been interesting. You will definitely see this notation in Haskell code that you read. Now I hinted before that we could actually use zip to generate a grid, so let's look at how we might do that. We can see that our columns are the list nought to infinity repeated over and over again, and similarly rows are essentially mapping over the list nought to infinity with the repeat function.
We can consider that using an infinite list of columns and an infinite list of rows might be very convenient in order to express a grid of arbitrary width and height, but it is going to be harder for us to demonstrate in this tutorial where we want to be looking at the values, using, for example, our og function in the GHCI interpreter. So let's create a new function that specializes repeat by taking eight values.
So this is a composition, it will run repeat and it will take eight values from the result. So now we can define versions of our rows and cols that work over the list from nought to seven and use our repeat8 function. So obviously you can see there that rows and cols are infinite lists, but if we display the value of rows8, and we can use og to nicely format that, and we can see, again, that the value increments as we work our way down the grid, and similarly cols8, the values increment to the right of the grid, and what we want to do now is to combine those two grids, and of course we've already seen a function that can combine these grids.
So if we run zip against that value in rows and that value in cols, we get a list of tuples of exactly the sort that we're looking for, but that's only over a single row. So how might we do that for arbitrary rows, 'cause we might think that we want to zip our rows with our columns, but the problem here is that zip has done exactly what we asked it to, it's taken the first row of rows and the first row of cols, and so on throughout the whole grid.
So really what we'd want is a function that did the same, but instead of combining with a comma, then zipped those two rows together. So let's have a look at how we combine values into a tuple. There is in fact a function, the comma operator which takes two arguments and combines them both with a comma in a new two-value tuple, and zipWith is a more general version of zip, and we can see here that if we call zipWith with the comma operator and then our two lists, that that does exactly the same as zip.
So you can think of zip as being essentially zipWith comma. So what we want to do now is to instead call zipWith with a function that combines the row from rows and the row from cols, and of course we know exactly what that function is, it is zip, and here we can see that zipWith zip has allowed us to combine a grid of rows and a grid of columns into a grid of tuples of rows and columns, and that's such a useful function that we can extract it into a function called zipOverGrid.
So now if we have a look at our word grid, what we really want to do now is to associate every character on the word grid with its coordinates, and we can see that zipOverGrid takes a grid of a and a grid of type b, and it returns a new grid of the tuple type a, b. So if we ran zipOverGrid with our coordinates grid and our word grid, then as you can see we get exactly what we were looking for, a list of tuples, each of which tuple contains a further tuple of coordinates and a character.
And you can see here that we have some of the words that we had defined. We have the programming language CSHARP, and here you can see from bottom to top I-S-P, which is the last part of the programming language LISP. Now where did the L go, and of course if you look at grid, this is a 12 by 15 grid whereas coordinates is an eight by eight grid, and of course in the way that zip will stop processing once any one list is exhausted, zipOverGrid will give up once any axis of the grid is exhausted.
So of course we could now make our coordinates grid larger by increasing this number here, but we know we already have an infinitely large set of columns and rows, so we can easily now define a new version of infinite coords grid and we can use our zipOverGrid function over that, and now we can call zipOverGrid on our infinite coordinates grid and the grid of words, and you can see that this gives us the full 12 by 15 grid.
In the next video we'll look at fleshing out the grid model. We're going to incorporate our new zipOverGrid function and create some new cell and grid data types.
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Discovering Haskell with GHCI
- Haskell datatypes and functions
- Using higher order functions for data manipulation and code reuse
- Editing Haskell source code
- Creating a project with Stack
- Writing and conducting tests