Treating Strings like Lists

We've spent the last month studying some of the intricacies of the different string types in Haskell. For this last article, I wanted to have a little bit of fun and consider how we might apply some of the ideas we learned from "list" functions back in January to these different string types.

The naive way to use these functions would be to transform your "Text" or "ByteString" back into a "String", run the list-based function, and then convert back. But it should hopefully be obvious now that that isn't such a great idea!

But these other string types still kind of seem like lists, so we should want to apply those functions. And because of this the authors for those packages included versions of the most common list based functions specifically geared for these types. For example, Text and ByteStrings have their own versions of functions like "map", "filter" and "fold".

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.Text as T
import qualified Data.ByteString as B

T.map :: (Char -> Char) -> T.Text -> T.Text
T.filter :: (Char -> Bool) -> T.Text -> T.Text
T.foldl :: (a -> Char -> a) -> a -> T.Text -> a

B.map :: (Word8 -> Word8) -> B.ByteString -> B.ByteString
B.filter :: (Word8 -> Bool) -> B.ByteString -> B.ByteString
B.foldl :: (a -> Word8 -> a) -> a -> B.ByteString -> a

Notice how for the ByteString, instead of Char being the underlying value, it's Word8. Unfortunately, this makes it a little harder to do character-specific manipulations, but we can still try!

>> T.filter isLower "Hello World"
"ello orld"
>> B.map (+1) "abcde"
"bcdef"

The numeric property underlying ByteStrings means you can do some interesting mathematical things with them. For example, you can build a simple "Caesar Cypher" like so, if you assume that your input is all lower-case or spaces. The number 97 indicates the offset for the letter 'a' as a Word8:

caesarCypher :: Int -> B.ByteString -> B.ByteString
caesarCypher shift = B.map shiftChar
  where
    shiftChar :: Word8 -> Word8
    shiftChar 32 = 32 -- Space
    shiftChar x = (((x - 97) + shift) `mod` 26) + 97

...

>> caesarCypher "hello there"
"mjqqt ymjwj"

Even more complicated functions like intercalate and transpose can be found in these libraries!

>> let bytestrings = ["One", "Two", "Three", "Four", "Five"] :: [B.ByteString]
>> B.transpose bytestrings
["OTTFF", "nwhoi", "eoruv", "ere", "e"]
>> let texts = ["Hello", "my", "friend"] :: [T.Text]
>> T.intercalate ", " texts
"Hello, my, friend"

So even if your program is using more advanced string types instead of the basic [Char], you can still get all the functional benefits of Haskell's many different ways of manipulating lists of values!

This is the end of our exploration of string types for now. But we'll be back with a new topic for March. So subscribe to our newsletter and keep coming back here if you want to stay up to date with the blog!

Fusion Powered Strings!

In the last few articles, we've gone through the different String types in Haskell, and I've made a few mentions of "efficiency". But what does this mean? It should be a bit more clear with Bytestrings. By using a more compact representation of the data, and operating on a lower level type like Word8, our strings will take up less space in memory, and they'll have more continuity. This makes operations on them more efficient. But what is it, exactly, about Text that makes it more efficient than using String?

One part of the answer to that is the concept of fusion. Throughout the documentation on Data.Text, you'll see the phrase "subject" to fusion. The short explanation is that GHC knows how to "fuse" Text operations together so that they happen more quickly and take less memory. Let's see a quick example of this.

Suppose we want to write a string manipulation function. This will drop the first 6 letters, add the letter 'a' on the beginning, append the word "goodbye" to the end, and then capitalize the whole thing. Here's what that function might look like using String:

transformString :: String -> String
transformString s = map toUpper $ 'a' : (drop 6 s) ++ ", goodbye."

...

>> transformString "Hello Friend"
"AFRIEND, GOODBYE."

In the process of making our final string ("AFRIEND, GOODBYE."), our program will actually make 4 different strings for each of the operations we run.

1. First, it will drop the 6 letters, and allocate space for the string "Friend".
2. Then, it will add the "a" to the front, giving us a new string "aFriend".
3. Next, it will append "goodbye", and we'll have "aFriend, goodbye.".
4. Finally, it will uppercase everything, giving "AFRIEND, GOODBYE.".

Allocating all this memory seems a bit wasteful. After all, the first three strings were just intermediate computations! But Haskell can't modify these values in place, because values are immutable in Haskell!

However, the Text type is specifically designed to work around this. It is written so that when compiled with optimizations, fusion functions can all be combined into a single step. So suppose we write the equivalent function with Text:

{-# LANGUAGE OverloadedStrings #-}
import qualified Data.Text as T

transformString :: T.Text -> T.Text
transformString s = T.map toUpper $ T.append (T.cons 'a' (T.drop 6 s)) ", goodbye."

...

>> transformString (T.pack "Hello Friend")
"AFRIEND, GOODBYE."

If we compile this code with sufficient optimization, it will only allocate memory for the final Text value. There will be no intermediate allocations, because the whole function is "fused"!

Fusion is a tricky subject, but if you're just starting out with Haskell, you don't need to worry too much about it. You should focus on the basics, like getting conversions right between these types. For more tips and tricks that will help you on your Haskell journey, download our free Beginners Checklist. It'll give you some more help and guide you to other resources that will help you learn!

Loading Different Strings

In the last couple of articles we've explored the Text and ByteString types. These provide alternative string representations that are more efficient when compared to the basic "list of characters" definition. But we've also seen that it can be a minor pain to remember all the different ways we can convert back and forth between them. And in fact, not all conversions are actually guaranteed to work the way we would like.

Now let's imagine our program deals with input and output. Now as a beginner, it's easy to think that there are only a couple primary functions for dealing with input and output, and that these only operate on String values:

putStrLn :: String -> IO ()

getLine :: IO String

If your program actually makes use of Text, you might end up (as I have in many of my programs) constantly doing something like T.pack <$> getLine to read the input as a Text, or putStrLn (unpack text) to print it out.

When you're dealing with files, this makes it more likely that you'll mess up lazy vs. strict semantics. You'd have to know that readFile is lazy, and readFile', an alternative, is strict.

readFile :: FilePath -> IO String

readFile' :: FilePath -> IO String

But you don't need to resort to always using the String type! All of our alternative types have their own IO functions. You just have to know which modules to use, and import them in a qualified way!

With Text, there are separate IO modules that offer these options for us:

import qualified Data.Text as T
import qualified Data.Text.IO as TI
import qualified Data.Text.Lazy as TL
Import qualified Data.Text.Lazy.IO as TLI

TI.putStrLn :: T.Text -> IO ()
TI.getLine :: IO T.Text

TLI.putStrLn :: TL.Text -> IO ()
TLI.getLine :: IO TL.Text

The modules also contain functions for reading and writing files as well, all with the appropriate Text types.

With ByteString types, these functions live in the primary module, and they aren't quite as exhaustive. There is putStr, but not putStrLn (I'm not sure why).

import qualified Data.ByteString as B
import qualified Data.ByteString.Lazy as BL

B.putStr :: B.ByteString -> IO ()
B.getLine :: IO B.ByteString

BL.putStr :: BL.ByteString -> IO ()
BL.getLine :: IO BL.ByteString

So, when you're program is using the more sophisticated string types, use the appropriate input and output mechanisms to spare yourself the inefficiencies (both performance-wise and in terms of code clarity) that come with using String as a go-between!

If you've never really written a Haskell program with input and output before, you'll need to have some idea of how Stack works so you can get all the pieces working. Take our free Stack mini-course to learn how everything works, and stay tuned for more tips on Strings and other useful areas of Haskell!

Taking a Byte out of Strings

Earlier this week we learned about the Text type, which is a more efficient alternative to String. But there's one more set of string-y types we need to learn about, and these are "ByteStrings"!

The Text types capture a unicode representation of character data. But ByteString is more low-level, storing its information at the "byte" level. A normal string is a list of the Char type, but the fundamental underlying data structure of the ByteString is a list of Word8 - an 8-bit (1 byte) unsigned integer!

This means that in the normal ByteString library, the pack and unpack functions are reserved for converting back and forth between [Word8] and the ByteString, rather than a raw String:

pack :: [Word8] -> ByteString

unpack :: ByteString -> [Word8]

This can make it seem as though it would be quite difficult to construct ByteStrings.

>> import qualified Data.ByteString as B
>> let b = B.pack [72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33]
>> b
"Hello world!"
>> B.unpack b
[72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33]

There are two ways around this. Once again, we can use the "OverloadedStrings" extension:

>> :set -XOverloadedStrings
>> let b = "Hello world!" :: B.ByteString
>> :t b
b :: B.ByteString

There is also another module called Data.ByteString.Char8. In this module, the pack and unpack functions are used for strings instead of Word8 chunks. Note though, that all characters you use will be truncated to 8 bits, so your results may not be correct, especially if you go far beyond the simple ASCII character set.

>> import qualified Data.ByteString.Char8 as BC
>> let b = BC.pack "Hello World!"
>> b
"Hello world!"
>> :t b
BC.ByteString
>> :t (BC.unpack b)
[Char]

Like Text, there are both strict and lazy versions of ByteString, which you convert using the same way.

>> import qualified Data.ByteString as B
>> import qualified Data.ByteString.Lazy as BL
>> :set -XOverloadedStrings
>> let b1 = "Hello" :: B.ByteString
>> let b2 = "World" :: BL.ByteString
>> let b3 = BL.fromStrict b1
>> let b4 = BL.toStrict b2
>> :t b3
BL.ByteString
>> :t b4
B.ByteString

The last item to make a note of is that we can convert directly between Text and ByteString. This is often desirable because of the transcription errors that can occur using String as a go-between. It also allows strictness or laziness to be maintained, since the following functions live in both Data.Text.Encoding and Data.Text.Lazy.Encoding.

The trick is that we have to have some idea of what encoding we are using. Most often, this is UTF-8. In this case, we can use the following functions:

encodeUtf8 :: Text -> ByteString

decodeUtf8 :: ByteString -> Text

Let's see these sorts of functions in action:

>> import qualified Data.Text as T
>> import qualified Data.ByteString as B
>> import Data.Text.Encoding
>> let t = T.pack "Hello world"
>> let b = encodeUtf8 t
>> b
"Hello world"
>> :t b
B.ByteString
>> let t2 = decodeUtf8 b
>> t2
"Hello world"
>> :t t2
T.Text

Encoding a Text as a ByteString will always succeed. But decoding a ByteString might fail. This is because the raw bytes someone uses might not be a representation of a valid set of characters. So decodeUtf8 can throw errors in special cases. If you're concerned about catching these, you can use one of the following functions:

decodeUtf8' :: ByteString -> Either UnicodeException Text

decodeUtf8With :: OnDecodeError -> ByteString -> Text

Other encodings exist besides UTF-8, but you also need to know if it is "big-endian" or "little-endian", indicating the ordering of the bytes in the underlying representation:

encodeUtf16LE :: Text -> ByteString

decodeUtf32BEWith :: OnDecodeError -> ByteString -> Text

It can be difficult to keep all these conversions straight. But here's the TLDR, with 4 different conversions to remember:

1. String <-> Text - Use Data.Text, with pack and unpack.
2. String <-> ByteString - Use Data.ByteString.Char8, with pack and unpack
3. Text <-> ByteString - Use Data.Text.Encoding with encodeUtf8 and decodeUtf8
4. Strict and Lazy - Use the "Lazy" module (Data.Text.Lazy or Data.ByteString.Lazy) with fromStrict and toStrict.

Like text, bytestring is a separate package, so you'll need to include in your project with either Stack or Cabal (or Nix). To learn how to use the Stack tool, sign up for our free Stack mini-course!

Con-Text-ualizing Strings

In the past couple weeks of string exploration, we've only consider the basic String type, which is just an alias for a list of characters:

type String = [Char]

But it turns out that this representation has quite a few drawbacks. There are other string representations that are more compact and result in more efficient operations, which is paramount when you are parsing a large amount of data.

But since the type system plays such a strong role in Haskell, each of these different string representations must have its own type. Today we'll talk about Text, which is one of these alternatives.

Rather than storing a raw list of the Char type, a Text object stores values as unicode characters. This allows many operations to be much faster.

But perhaps the first and most important thing to learn when you're a beginner is how to convert back and forth between a normal String and Text. This is done with the pack and unpack functions:

import Data.Text (Text, pack, unpack)

pack :: String -> Text

unpack :: Text -> String

Because the underlying representations are a bit different, not every String can be converted into Text in a comprehensible manner. But if you're sticking to the basic ASCII character set, everything will work fine.

>> let s = "ABCD" :: String
>> let t = pack s
>> t
"ABCD"
>> :t t
Text
>> unpack t
"ABCD"
>> :t (unpack t)
[Char]

The Text library has many different functions for manipulating Text objects. For example, append will combine two Text items, and cons will add a character to the front. Many of these overlap with Prelude functions, so it is usually best to import this module in a qualified way.

>> import qualified Data.Text as T
>> let t1 = T.pack "Hello"
>> let t2 = T.pack "World"
>> T.append t1 (T.cons ' ' t2)
"Hello World"

Naturally, Text implements the IsString class we talked about a little while ago. So if you enable OverloadedStrings, you don't actually need to use pack to initialize it! You can just use a string literal.

>> import qualified Data.Text as T
>> :set -XOverloadedStrings
>> let t = "Hello" :: T.Text

Now technically there are two different Text types. So far, we've referred to "strict" Text objects. These must store all of their data in memory at once. However, we can also have "lazy" Text objects. These make use of Haskell's laziness mechanics so that you can stream data without having to store it all at once. All the operations are the same, they just come from the Data.Text.Lazy module instead of Data.Text!

>> import qualified Data.Text.Lazy as TL
>> let t1 = TL.pack "Hello"
>> let t2 = TL.pack "World"
>> TL.append t1 (TL.cons ' ' t2)
"Hello World"

There will often come times where you need to convert back and forth between these. The Lazy module contains functions for doing this.

>> import qualified Data.Text as T
>> import qualified Data.Text.Lazy as TL
>> let t1 = T.pack "Hello"
>> let t2 = TL.pack "World"
>> let t3 = TL.fromStrict t1
>> let t4 = TL.toStrict t2
>> :t t3
TL.Text
>> :t t4
T.Text

Because these types live in the text package, and this package is not included in base, you'll need to know how dependencies work in use it in your projects. To learn more about this, take our free Stack mini-course! You'll learn how to make a project using Stack and add dependencies to it.

When Strings get Word-y

Earlier this week we explored the lines and unlines functions which allow us to split up strings based on where the newline characters are and then glue them back together if we want. But a lot of times the newline is the character you're worried about, it's actually just a normal space! How can we take a string that is a single line and then separate it?

Again, we have very simple functions to turn to: words and unwords:

words :: String -> [String]

unwords :: [String] -> String

These do exactly what you think they do. We can take a string with several words in it and break it up into a list that excludes all whitespace.

>> words "Hello there my friend"
["Hello", "there", "my", "friend"]

And then we can recombine that list into a single string using unwords:

>> unwords ["Hello", "there", "my", "friend"]
"Hello there my friend"

This pattern is actually quite helpful when solving problems of the kind you'll see on Hackerrank. Your input will often have a particular format like, "the first line has 'n' and 'k' which are the number of cases and the case size, and then there are 'n' lines with 'k' elements in them." So this might look like:

5 3
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15

Then words is very useful for splitting each line. For example:

readFirstLine :: IO (Int, Int)
readFirstLine = do
  firstNumbers <- words <$> getLine
  case firstNumbers of
    (n : k : _) -> return (n, k)
    _ -> error "Invalid input!"

As with lines and unlines, these functions aren't inverses, properly speaking. With unwords, the separator will always be a single space character. However, if there are multiple spaces in the original string, words will work in the same way.

>> words "Hello    there    my    friend"
["Hello", "there", "my", "friend"]
>> unwords (words "Hello    there    my     friend")
"Hello there my friend"

In fact, words will separate based on any whitespace characters, including tabs and even newlines!

>> words "Hello \t  there \n my \n\t friend"
["Hello", "there", "my", "friend"]

So it could actually do the same job as lines, but then reversing the process would require unlines rather than `unwords.

Finally, it's interesting to note that unlines and unwords are both really just variations of intercalate, which we learned about last month.

unlines :: [String] -> String
unlines = intercalate "\n"

unwords :: [String] -> String
unwords = intercalate " "

For more tips on string manipulation in Haskell, make sure to come back next week! We'll start exploring the different String types that exist in Haskell! If you're interested in problem solving in Haskell, you should try our free Recursion Workbook! It explains all the ins and outs of recursion and includes 10 different practice problems!

Line 'em Up!

Reading from files and writing to files is a very important job that you'll have to do in a lot of programs. So it's very much worth investing your time in learning functions that will streamline that as much as possible.

Enter lines and unlines. These two functions make it substantially easier for you to deal with the separate lines of a file (or any other string really). Fundamentally, these two functions are inverses of each other. The "lines" function will take a single string, and return a list of strings, while "unlines" will take a list of strings and return a single string.

lines :: String -> [String]

unlines :: [String] -> String

Our friend "lines" takes a string that has newline characters (or carriage returns if you're using Windows) and then break it up by the lines.

>> lines "Hello\nWorld\n!"
["Hello", "World", "!"]

Then "unlines" is able to take that list and turn it back into a single string, where the entries of the list are separated by newlines.

>> unlines ["Hello", "World", "!"]
"Hello\nWorld\n!\n"

One distinction you'll notice is that our final string from "unlines" has an extra newline character. So strictly speaking, these functions aren't total inverses (i.e. unlines . lines /= id). But they still essentially function in this way.

As mentioned above, these functions are extremely handy for file reading and writing. Suppose we are reading a file and want to break it into its input lines. A naive solution would be to produce a Handle and then use iterated calls to hGetLine. But this gets tedious and is also error prone when it comes to our end condition.

readFileLines :: FilePath -> IO [String]
readFileLines fp = do
  handle <- openFile fp ReadMode
  results <- readLinesHelper handle []
  hClose handle
  return results
  where
    readLinesHelper :: Handle -> [String] -> IO [String]
    readLinesHelper handle prevs = do
      isEnd <- hIsEOF handle
      if isEnd
        then return (reverse prevs)
        else do
          nextLine <- hGetLine handle
          readLinesHelper handle (nextLine : prevs)

Boy that's a little messy…

And similarly, if we wanted to write each string in a list to a separate line in the file using hPutStrLn, this is non-trivial.

writeFileLines :: [String] -> FilePath -> IO ()
writeFileLines strings fp = do
  handle <- openFile fp WriteMode
  mapM_ (hPutStrLn handle) strings
  hClose handle

But these both get waaay easier if we think about using lines and unlines. We don't even have to think about the file handle! When reading a file, we just use lines in conjunction with readFile:

readLines :: FilePath -> IO [String]
readLines fp = lines <$> readFile fp

Then similarly, we use unlines with writeFile:

writeFileLines :: [String] -> FilePath -> IO ()
writeFileLines strings fp = writeFile fp (unlines strings)

And thus what were tricky implementations (especially for a beginner) are now made much easier!

Later this week we'll look at another set of functions that help us with this problem of splitting and fusing our strings. In the meantime, make sure to sign up for the Monday Morning Haskell newsletter if you haven't already! If you do, you'll get access to a lot of our great resources for beginning and intermediate Haskellers alike!

Classy Strings

In January we shared many different examples of helpful functions you can use with lists. In Februrary, we'll be focusing on Strings. Of course, Haskell's different string representations all use lists to some extent, so we've already seen several examples of list manipulation being useful with strings. But now we'll look more specifically at the different types that all us to describe string-like data.

Our first useful idea is the IsString class. This can apply to any type that we can derive from a String. The key function is fromString.

class IsString a where
  fromString :: String -> a

Making an instance of this type is easy enough as long as your data makes sense. Suppose we have a simple newtype wrapper for a string.

newtype Person = Person String

Our IsString instance is trivial:

instance IsString Person where
  fromString = Person

But sometimes we might want something a little trickier. Suppose we want to give our person a first AND last name, given only a single string.

data Person = Person
  { firstName :: String
  , lastName :: String
  } deriving (Show)

Now our instance is non-trivial, but still simple if we remember our helpful list functions! We first take all the characters that are "not spaces" to get the first name. Then to get the last name, we drop these characters instead, and then drop all the spaces as well!

instance IsString Person where
  fromString s = Person firstName lastName
    where
      firstName = takeWhile (not . isSpace) s
      lastName = dropWhile isSpace (dropWhile (not . isSpace) s)

We can use this instance in the simple way, applying the fromString function directly:

>> fromString "George Washington" :: Person
Person {firstName = "George", lastName = "Washington"}

But what's more interesting is that if we turn on the "Overloaded Strings" extension, we can use a string literal for this object in our code!

>> :set -XOverloadedStrings
>> let president = "George Washington" :: Person

This compiler extension is extremely useful once we get to other kinds of strings (Text, ByteString, etc.). But, combined with the IsString class, it's a nice little quirk that can make our lives easier in certain circumstances, especially when we are running some kind of parsing program, or pasting in stringified data into our Haskell source when we don't want to bother reformatting it.

We'll be back next Monday with more string tricks! If you want to use tricks like these in a project, you need to learn how to use Stack first. To help with this, sign up for our free Stack mini-course!

To Infinity and Beyond!

We're at the end of January now, so this will be the last article on basic list utilities. For this last set of functions, we'll explore some items that are very helpful when you are using infinite lists in Haskell.

Infinite lists are kind of a cool construct because they only really exist due to Haskell's lazy evaluation mechanisms. Most other languages don't have them because eager evaluation would force you to use an infinite amount of space! But in Haskell, you only need to allocate space for the items in the list that actually get evaluated.

The two most basic functions for creating an infinite list are "repeat" and "cycle". The first makes an infinite number of the same element, while the second allows you to cycle through a specific series of elements.

repeat :: a -> [a]

cycle :: [a] -> [a]

But how exactly are these useful? For example, simply by trying to print them we'll create a mess of output that will make us force quit the program:

>> repeat 3
[3, 3, 3, 3, 3, ...
>> cycle [1, 2, 3, 4]
[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ...

Well one answer is to use take, which we learned about last time. We can "take" a specific number of a single element.

>> take 5 (repeat 3)
[3, 3, 3, 3, 3]

Infinite lists are also great in conjunction with zip, because this "shortens" the result to the size of the finite list. Suppose we want to match up a list with the index modulo 4:

>> let l1 = [5, 3, 1, -4, 6, 20]
>> zip l1 (cycle [0, 1, 2, 3])
[(5, 0), (3, 1) ,(1, 2) ,(-4, 3) ,(6, 0) ,(20, 1)]

One more way to generate an infinite list is to use iterate. This allows us to continually apply a function against a starting value. We start with a, and then the second element will apply the function once as f a, and then the next value will be f (f a), and so on.

iterate :: (a -> a) -> a -> [a]

One use case for this might be to calculate the value of an investment using compound interest. Let's say you start with $10,000 and you get 5% interest every year. How much will you have after 5 years?

>> take 6 (iterate (* 1.05) 10000.0)
[10000.0, 10500.0, 11025.0, 11576.25, 12155.06, 12762.82]

You can also use fairly simple addition functions with iterate. But you should also know that in most cases you can represent such an infinite list with a range!

>> take 5 (iterate (+3) 1)
[1, 4, 7, 10, 13]
>> take 5 [1,4..]
[1, 4, 7, 10, 13]

That's all for our exploration of basic list functions! We'll have a new topic next month, so subscribe to our monthly newsletter to stay on top of what we're studying! You can also sign up by downloading our free Beginners Checklist!

Taking and Dropping

In our first article on list functions, we looked at some boolean functions that allowed for filtering lists based on particular conditions. Of course, filter is the primary function we might use for that. But sometimes, you're only concerned with how long the pattern is at the start of your list. You want to include some of the elements at the start, or else drop them. Today we'll look at variations of "take" and "drop" functions that let you do this.

The most basic versions of these functions allow you to specify the number of elements you're interested. The "take" function takes an integer and your list and produces the first "n" elements, while "drop" will give you the remainder of the list besides these elements:

take :: Int -> [a] -> [a]

drop :: Int -> [a] -> [a]

Getting the 5 smallest numbers in a list is easy when you combine take and sort.

>> let myList = [2, 5, 6, 3, 1, 9, 8, 7, 4]
>> take 5 (sort myList)
[1, 2, 3, 4, 5]
>> drop 5 (sort myList)
[6, 7, 8, 9]

This is simple enough, but sometimes you want to do something a little trickier. You want to take all the elements of the list from the front, but only as long as they satisfy a particular condition. In this case, you want takeWhile and its comrade, dropWhile. Each of these takes a predicate function instead of a number.

takeWhile :: (a -> Bool) -> [a] -> [a]

dropWhile :: (a -> Bool) -> [a] -> [a]

A couple simple use cases might be removing the "odd" numbers from the start of a list, or grabbing only the lowercase letters of a variable name that you've parsed.

>> let isOdd x = x `mod` 2 == 1
>> dropWhile isOdd [5, 7, 9, 2, 1, 3, 4]
[2, 1, 3, 4]
>> takeWhile isLower "variableNameInCamelCase"
"variable"

Now in the Data.List.Extra library, there are some additional variations that allow for taking and dropping from the end:

takeWhileEnd :: (a -> Bool) -> [a] -> [a]

dropWhileEnd :: (a -> Bool) -> [a] -> [a]

We'll cover more of these kinds of "extra" functions later in the year. But these two examples do the same thing as their counterparts, just operating from the end of the list instead of the start.

>> isOdd x = x `mod` 2 == 1
>> takeWhileEnd isOdd [2, 4, 1, 6, 7, 9]
[7, 9]
>> dropWhileEnd isOdd [2, 4, 1, 6, 7, 9]
[2, 4, 1, 6]

We'll soon be moving on from list manipulations to a new topic. To keep up to date, make sure you keep checking this blog every Monday and Thursday, or subscribe to our monthly newsletter! If you're just starting out learning Haskell, subscribing will give you access to our Beginners Checklist which will help you learn the basics and get going!

Math-y List Operations

Earlier this month we explored some functions related to booleans and lists. Today we'll consider a few simple helpers related to lists of numbers.

As in Python, Haskell allows you to easily take the product and sum of a list. These functions are very straightforward:

sum :: (Num a) => [a] -> a

product :: (Num a) => [a] -> a

...

>> sum [1, 2, 3, 4]
10
>> sum [-1, 1]
0
>> product [1, 2, 3, 4]
24
>> product [5, 6, -2]
-60

As with our boolean functions, I originally gave the type signatures in terms of lists, but they actually work for any "Foldable" type. So both the inner and outer type of our input are parameterized.

sum :: (Foldable t, Num a) => t a -> a

product :: (Foldable t, Num a) => t a -> a

...

>> sum $ Set.fromList [1, 2, 3]
6

Both of these functions also work with empty lists, since these operations have an identity to start with.

>> sum []
0
>> product []
1

The same cannot be said for the functions minimum and maximum. These require non-empty lists, or they will throw an error!

minimum :: (Foldable t, Ord a) => t a -> a

maximum :: (Foldable t, Ord a) => t a -> a

...

>> maximum [5, 6, -1, 4]
6
>> minimum [5, 6, -1, 4]
-1
>> maximum []
*** Exception: Prelude.maximum: empty list

And while they can be used with numbers, as above, they can also be used with any orderable type, such as strings.

>> maximum ["hello", "world"]
"world"

Remember what we mentioned a while ago with groupBy and how many functions have another version with By? This applies for our min and max functions. These allow us to provide a custom comparison operation.

maximumBy :: (Foldable t) => (a -> a -> Ordering) -> t a -> a
minimumBy :: (Foldable t) => (a -> a -> Ordering) -> t a -> a

As an example, let's consider that when comparing tuples, the first element is used to sort them. Only if there is a tie to we go to the second element.:

>> maximum [(1, 4), (2, 1), (2, 3)]
(2, 3)

However, we can instead use the second element as the primary comparison like so:

>> let f (x1, x2) (y1, y2) = if x2 == y2 then x1 `compare` y1 else x2 `compare` y2
>> maximumBy f [(1, 4), (2, 1), (2, 3)]
(1, 4)
>> minimumBy f [(1, 4), (2, 1), (2, 3)]
(2, 1)

This approach is also very helpful when you're dealing with more complex types, but you only care about comparing a single field.

As a final note, sort and sortBy follow this same pattern. The first one assumes an ordering property, the second allows you a custom ordering.

sort :: (Ord a) => [a] -> [a]

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

For more tricks like this, keep following the Monday Morning Haskell blog every Monday and Thursday! You can subscribe to get our monthly newsletter as a summary. This will also get you access to subscriber resources like our Beginners Checklist.

Changing and Re-Arranging

Any time I go to a wedding or some kind of family gathering where we take a lot of pictures, it can seem like it goes on for a while. It seems like we have to take a picture with every different combination of people in it. Imagine how much worse it would be if we needed the also get every different ordering (or permutation) of people as well!

Even if it got to that level, it would still be easy to write a Haskell program to handle this problem! There are a couple specific list functions we can use. The "subsequences" function will give us the list of every subsequence of the input list.

subsequences :: [a] -> [[a]]

This would be helpful if all we want to know is the different combinations of people we would get in the pictures.

>> subsequences ["Christina", "Andrew", "Katharine"]
[[], ["Christina"], ["Andrew"], ["Christina", "Andrew"], ["Katharine"], ["Christina", "Katharine"], ["Andrew", "Katharine"], ["Christina", "Andrew", "Katharine"]]

Note a couple things. First, our result includes the empty sequence! Second of all, the order of the names is always the same. Christina is always before Andrew, who is always before Katharine.

Now let's suppose we have a different problem. We want everyone in the picture, but we can order them anyway we want. How would we do that? The answer is with the "permutations" function.

permutations :: [a] -> [[a]]

This will give us every different ordering of our three people.

>> permutations ["Christina", "Andrew", "Katharine"]
[["Christina", "Andrew", "Katharine"], ["Andrew", "Christina", "Katharine"], ["Katharine", "Andrew", "Christina"], ["Andrew", "Katharine", "Christina"], ["Katharine", "Christina", "Andrew"], ["Christina", "Katharine", "Andrew"]]

Be wary though! These functions are mostly useful with small input lists. The number of subsequences of a list grows exponentially. With permutations, it grows with the factorial! By the time you get up to 10, you're already dealing with over 3 million possible permutations!

>> length (subsequences [1, 2, 3, 4])
16
>> length (subsequences [1, 2, 3, 4, 5])
32
>> length (subsequences [1, 2, 3, 4, 5, 6])
64
>> length (permutations [1, 2, 3, 4])
24
>> length (permutations [1, 2, 3, 4, 5])
120
>> length (permutations [1, 2, 3, 4, 5, 6])
720

If such cases are really necessary for you to handle, you might need to take advantage of Haskell's laziness and treat the result similar to an infinite list, as we'll cover later this month.

If you want to keep learning about random interesting functions, you should subscribe to Monday Morning Haskell! You'll get access to all our subscriber resources, including our Beginners Checklist.

Transposing Rows

In our last article we explored how groupBy could allow us to arrange a Matrix (represented as an Array) into its rows.

myArray :: Array (Int, Int) Double)
myArray = listArray ((0, 0), (1, 1)) [1..4]

rows = groupBy (\((a, _), _) ((b, _), _) -> a == b) (assocs myArray)

...

>> rows myArray = [[((0, 0), 1), ((0, 1), 2)], [((1, 0), 3), ((1, 1), 4)]]

But what about a different case? Suppose we were most concerned about grouping the columns together? At first glance, it doesn't seem as though this would be possible using groupBy, since the elements we want aren't actually next to each other in the assocs list.

However, there is another simple list function we can use to complete this process. The transpose function takes a list of lists, which we can think of as a "matrix". Then it transposes the matrix so that the rows are now the columns.

transpose :: [[a]] -> [[a]]

...

>> transpose [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Clearly we could use this function to achieve the result we want with our 2D array!

>> rows = groupBy (\((a, _), _) ((b, _), _) -> a == b) (assocs myArray)
>> transpose (rows myArray)
[[((0, 0), 1), ((1, 0), 3)], [((0, 1), 2), ((1, 1), 4)]]

This function, of course, works even if the input is not a "square" matrix.

>> transpose [[1, 2, 3, 4], [5, 6, 7, 8]]
[[1, 5], [2, 6], [3, 7], [4, 8]]

It even works if it is not rectangular! If some "rows" are shorter than others, than our result is still sound! Essentially, the first row in the result is "every first element of a list". The second row is every "second" element. And so on. Every element in the original list is represented in the final list. Nothing is dropped like you might have in zip.

>> transpose [[1, 2, 3], [4], [5, 6], [], [7, 8, 9, 10]]
[[1, 4, 5, 7], [2, 6, 8], [3, 9], [10]]

Hopefully this is an interesting function that you hadn't thought of using before! If you want to keep seeing tricks like this, subscribe to our monthly newsletter so you can keep up to date with the different tricks we're exploring here. You'll also get access to our subscriber resources!

"Group" Theory

Last time around we saw the function "intercalate". This could take a list of lists, and produces a single list, separated by the list from the first argument. But today, we'll take a look at a couple functions that work in reverse. The "group" functions take something like a flat, single-level list, and turn it into a list of lists.

group :: (Eq a) => [a] -> [[a]]

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

When you use the basic group function, you'll take your list and turn it into a list of lists where each list contains successive elements that are equal.

>> group [1, 2, 2, 3, 4, 4, 4]
[[1], [2, 2], [3], [4, 4, 4]]

This is useful for answering a question like "What is the longest consecutive sequence in my list?" Like any list function, it can be used on strings.

>> group "Hello Jimmy"
["H", "e", "ll", "o", " ", "J", "i", "mm", "y"]

The groupBy function provides more utility. It lets you pass in your own comparison test. For example, here's a rudimentary way to separate a raw CSV string. You "group" all characters that aren't strings, and then filter out the commas.

separateCSV :: String -> [String]
separateCSV s = filter (/= ",") (groupBy (\c1 c2 -> c1 /= ',' && c2 /= ',') s)

...

>> separateCSV "Hello,there,my,friend"
["Hello", "there", "my", "friend"]

Here's another example. Suppose you have an array representing a two-dimensional matrix:

myArray :: Array (Int, Int) Double

The assocs function of the Array library will give you a flat list. But you can make this into a list of lists, where each list is a row:

myArray :: Array (Int, Int) Double)

rows = groupBy (\((a, _), _) ((b, _), _) -> a == b) (assocs myArray)

This is a common pattern you can observe in list functions. There's often a "basic" version of a function, and then a version ending in By that you can augment with a predicate or comparison function so you can use it on more complicated data.

If you enjoyed this article, sign up for our mailing list to our newsletter so that you get access to all our subscriber resources. One example is our Beginners Checklist! This is a useful resource if you're still taking your first steps with Haskell!

In the Middle: Intersperse and Intercalate

This week we continue looking at some useful list-based functions in the Haskell basic libraries. Last time around we looked at boolean functions, this time we'll explore a couple functions to add elements in the middle of our lists.

These functions are intersperse and intercalate:

intersperse :: a -> [a] -> [a]

intercalate :: [a] -> [[a]] -> [a]

Using "intersperse" will place a single item in between every item in your list. For example:

>> intersperse 0 [1, 2, 1]
[1, 0, 2, 0, 1]

This can be used in strings, for example, to space out the letters:

>> intersperse ' ' "Hello"
"H e l l o"

The "intercalate" function is similar but "scaled up". Instead taking a single element and a list of elements as its two inputs, it takes a list and a "list of lists". This is even more flexible when it comes to the use case of separating strings. For example, you can comma separate a series of words:

>> intercalate ", " ["Hello", "my", "friend"]
"Hello, my, friend"

Using intercalate combined with map show can make it very easy to legibly print a series of items if you use commas, spaces, and newlines!

Another use case for intercalate could be if you are constructing a numeric matrix, but you want to add extra columns to pad on the right side. Suppose this is our starting point:

1 2 3 4
5 6 7 8
9 8 7 6
5 4 3 2

But what we want is:

1 2 3 4 0 0 0
5 6 7 8 0 0 0
9 8 7 6 0 0 0
5 4 3 2 0 0 0

Here's how we do this:

>> intercalate [0, 0, 0] [[1, 2, 3, 4], [5, 6, 7, 8], [9, 8, 7, 6], [5, 4, 3, 2]]
[ 1, 2, 3, 4, 0, 0, 0
, 5, 6, 7, 8, 0, 0, 0
, 9, 8, 7, 6, 0, 0, 0
, 5, 4, 3, 2, 0, 0, 0
]

The result ends up as just a single list though, so you can't really compose calls to intercalate. Keep that in mind! Also, unlike the boolean functions from last time, these only work on lists, not any Foldable object.

Make sure you subscribe to our monthly newsletter so you can stay up to date with the topic each month! Subscribing will give you access to all our subscriber resources, including our Beginners Checklist, so don't miss out!

Booleans in Lists

As announced last week, this year we'll be doing short form articles twice a week highlighting useful library functions. The focus area for the month of January is simple list functions. We'll start with some simple functions that interact with booleans.

Like any other language, Haskell has operators for dealing with booleans like "and" and "or":

(&&) :: Bool -> Bool -> Bool

(||) :: Bool -> Bool -> Bool

But these only work with two booleans. If you have a variable-sized list of items, you can't directly apply these operators. In a language like Java, you'd write a for loop to deal with this. Here's how you would take "or" over a whole list.

boolean[] myBools;
result = false;
for (boolean b : myBools) {
  result |= b;
}

In Haskell, you'd write a recursive helper instead. But you get this for free with the and and or functions:

and :: [Bool] -> Bool

or :: [Bool] -> Bool

Here's how it might look in GHCI:

>> and [True, True, True]
True
>> and [True, False, True]
False
>> or [True, False, True]
True
>> or [False, False, False]
False

Most of the time though, you won't just be dealing with booleans. You'll have a list of other objects, and you'll want to ask a question like, "Do these all satisfy some condition?" If you can express that condition with a predicate function, you can check that condition for all items in the list using any and all. The first is like "or", the second is like "and".

any :: (a -> Bool) -> [a] -> Bool

all :: (a -> Bool) -> [a] -> Bool

Here they are in action with numbers:

>> any (\i -> i `mod` 2 == 0) [2, 4, 7, 8]
True
>> all (\i -> i `mod` 2 == 0) [2, 4, 7, 8]
False

These functions are equivalent to mapping the predicate and then using one of our earlier functions:

>> or (map (\i -> i `mod` 2 == 0) [2, 4, 7, 8])
True
>> all (map (\i -> i `mod` 2 == 0) [2, 4, 7, 8])
True

Finally, these functions aren't just for lists. They generalize to any foldable type:

and :: (Foldable t) => t Bool -> Bool

or :: (Foldable t) => t Bool -> Bool

any :: (Foldable t) => (a -> Bool) -> t a -> Bool

all :: (Foldable t) => (a -> Bool) -> t a -> Bool

...

>> and (Set.fromList [True, False])
False

Be sure to subscribe to our newsletter so you can stay up to date with the latest news! Subscribing will give you access to all our subscriber resources, including our Beginners Checklist!

New in ‘22!

Welcome to a new year of Monday Morning Haskell! I wanted to start the year off with a quick overview of my plans for the year. In 2021, I focused a bit less on blog content and quite a bit more on course content, my open source project Haskellings, as well as video and streaming content on our YouTube and Twitch pages.

For 2022 though, I'm renewing my focus on written content! The format will be a little different though. Instead of a lengthier piece once a week, I'm now going to be writing shorter-form articles twice a week, Monday AND Thursday. (So now you get Thursday morning Haskell in addition to Monday morning!)

Each of these articles will zero in on a few specific library functions. These will often be functions I hadn't necessarily known about during my first iterations of learning Haskell. In many cases I started to find some interesting uses as I ventured more into problem-solving on HackerRank over the last few months.

Each month will have a different theme. In January, we'll be exploring helpful list functions that are maybe a bit out of the ordinary.

Video Content

Now, speaking of problem-solving on HackerRank...

I'm going to continue with weekly streams whenever possible on my Twitch page, usually on Monday evenings. These will focus on solving technical problems on sites like HackerRank using Haskell. I want to explore the process of how to improve at these kinds of problems and see how this translates to other areas of my programming.

I plan on taking some of these sessions and making more YouTube videos out of them, but outside of this I probably won't be focusing too much on Haskell video content.

Announcement: Monday Morning Learning

Now in addition to all of this, I'm launching a new companion site, called Monday Morning Learning! Content on this site will go beyond Haskell and explore the general process of how to learn and improve at a new skill. If you enjoy Monday Morning Haskell, there's a good chance that you'll like this content as well!

Programming as a more general skill is definitely one of the focus areas of this site, but I'll also be exploring the learning process for completely different areas like playing games such as Chess and Go, or even becoming a better writer or making music.

This new site will have weekly content in both written and video form. In addition to my Haskell streams, I'll also do separate streams for learning-specific content.

I won't post too much more about Monday Morning Learning on this page, since I want to keep things Haskell-focused over here. But if you want to support these efforts, make sure to subscribe to all our pages!

Sign up for our Monday Morning Haskell newsletter!

Subscribe for notifications on our YouTube Channel!

For Monday Morning Learning, follow us on our newsletter, YouTube Channel, and Twitch page!

Last Day for Haskell Brain!

It's the last Monday of 2021, so of course this will be my last post of the year, which you can also watch on YouTube. This year was definitely a bit different from previous years. I focused a lot more on three things. The first was video content. I started using videos for a lot more of my Monday posts. You can take a look at those on my YouTube channel. And I also started streaming most Monday evenings on Twitch, which you can find right here. I'm on my winter vacation, so I won't be on for a couple weeks though. Next stream will be January 10th!

The second big item was Haskellings. This is now a fairly stable open-source project, so it's available for anyone who wants an interactive tutorial to learn how to write Haskell starting from the ground up!

Haskell Brain

The third focus this year has been on making some new courses for Monday Morning Haskell Academy. The new, smaller courses this year include Making Sense of Monads, as well as Effectful Haskell.

And last but not least of course, there is our newest course, Haskell Brain. Today, Monday the 27th, is the last day to enroll in our Haskell Brain course. This course will teach you the basics of using Haskell and Tensor Flow together so you can write your own machine learning programs totally in Haskell. Machine learning is a super important skill in the world today, and I think it would be so cool if we could prove that it can be done and that there might even be certain advantages to doing it in Haskell. So I hope you'll take this opportunity to learn these skills.

Cheers to 2022!

I have big plans for this upcoming year. Primarily, I'm going to go back to focusing on publishing new content on a regular basis. But there will definitely be some differences in my focus areas and how I present that content. If you're interested to see where Monday Morning Haskell goes from here I encourage you to subscribe to our mailing list, so you can stay up to date with all the latest news. I hope all of you have an excellent end to your year, and I'll see you in 2022!

Learning to Navigate the Maze!

Previously on this series, we explored how we could adapt our very basic "Breadth First Search" game to be an Open AI Gym "Environment". This week, we'll take the final step and learn what it means to make our environment into a "Learning Environment". Instead of prescribing how our agent moves through the maze, we'll let it learn this for itself using reinforcement learning!

I won't go over every line of code in this particular article, but you can take a look at the full code by checking out this GitHub repository! The code we'll be looking at will be focused in the LearningEnvironment module and MazeLearner. If instead of reading about this you'd like to watch the code in action, take a look at this YouTube video!

A Learning API

Let's recall that we had this function that served as our "game loop". That is, it could take any environment and run through the game's iterations until it finished.

gameLoop ::
  (EnvironmentMonad m) => m (Action m) -> m (Observation m, Reward)
gameLoop chooseAction = do
  newAction <- chooseAction
  (newObs, reward, done) <- stepEnv newAction
  if done
    then return (newObs, reward)
    else gameLoop chooseAction

We also had a comparable function for a "Renderable" environment that would render the game state with each iteration.

What would it look like, at a high level, for us to make a "learning" loop? That is, what API functions would we want to be available to cause our game agent to learn and improve from iteration to iteration?

I propose we would want at least three elements. First, the "choose action" function should now be an explicit part of the state, rather than a function parameter. Second, we naturally need a "learn" function that takes the observations and rewards and adjusts whatever state we use for choosing the action.

Finally, we should be able to reduce our "exploration rate". For many learning algorithms, we'll want to allow it a chance to "explore" options at first rather than use its own brain. This prevents it from getting stuck in bad habits early on. But we want to reduce the probability of randomness over time so that it can assert the information it has learned.

We'll also want to add an extra layer to our loop. We want to run many iterations of the game over time, rather than a single iteration. After a certain number of iterations, we'll reduce the exploration rate.

Here's a first pass at what these functions might look like. Notice how they rely on our previous environment functions like current observation, stepEnv and resetEnv.

gameLearningLoop = do
  oldObs <- currentObservation
  newAction <- chooseActionBrain
  (newObs, reward, done) <- stepEnv newAction
  learnEnv oldObs newAction newObs reward 
  if done
    then return reward
    else gameLearningLoop

gameLearningIterations = forM [1..numEpisodes] $ \i -> do
  resetEnv
  when (i `mod` 100 == 99) $ do
    reduceExploration decayRate minEpsilon
  reward <- gameLearningLoop
  return reward
  where
    numEpisodes = 1000
    decayRate = 0.9
    minEpsilon = 0.01

Those parameters at the bottom could be inputs to our function or constants. But we see that this function will accumulate the total reward values for each run of our game.

Making a Class

This idealized function informs some of the pieces we'll need for a "Learning Environment" class. What's clear though is that this class should "wrap" the monad for our environment. In this way, we don't need to modify our exist game's monad just to make it learn a particular way. So the first thing we'll do with this class is use an associated type to assign our environment monad. We'll also want a lift function that will take actions in the environment/game and bring them into the learning monad.

class (Monad m) => LearningEnvironment m where
  type Env m :: * -> *
  liftEnv :: (Env m) a -> m a
  ...

Notice how the "kind" is * -> * because our environment is a monad!

Naturally, we'll also want a "learning state" that is separate from the environment's state. This will store our exploration rate, amoung other things. We'll include functions from getting and setting this state. This is also a good opportunity to include our exploration functions. We should be able to "get" it and then reduce it.

class (Monad m) => LearningEnvironment m where
  type Env m :: * -> *
  liftEnv :: (Env m) a -> m a
  type LearningState m :: *
  getLearningState :: m (LearningState m)
  putLearningState :: (LearningState m) -> m ()
  explorationRate :: m Double
  reduceExploration :: Double -> Double -> m ()
  ...

Finally, we reach our two critical functions, choosing an action and learning. Choosing an action will involve selecting an action corresponding to our environment. This is simple in concept, but the type signature gets a little odd:

class (Monad m) => LearningEnvironment m where
  ...
  chooseActionBrain ::
    (EnvironmentMonad (Env m)) => m (Action (Env m))

We have Env m which is our environment type, and then the Action is associated with that environment, hence Action (Env m). Plus, our environment is constrained by an EnvironmentMonad.

Now finally, the learn function. This takes four parameters

The "starting" observation The action we took based on that observation The "new" observation resulting from that action The reward from taking that action.

Then it will update the learning state, though it will not provide a return value.

class (Monad m) => LearningEnvironment m where
  ...
  learnEnv ::
    (EnvironmentMonad (Env m)) =>
    (Observation (Env m)) ->
    (Action (Env m)) ->
    (Observation (Env m)) ->
    Reward ->
    m ()

These definitions complete our class!

A Basic Implementation

As with the maze game itself, this code only runs if we create an instance for it! So let's start by defining our learning state type. What information do we need to store that will help us select our move and learning appropriately?

For this example, we're going to use a basic form of Q-Learning. In Q-Learning, we have a function that takes an observation and action and produces a score value. So in any given situation, our "move" is to select the action with the highest score. The rewards then let us calibrate how this function operates, gradually assigning higher scores to actions with higher rewards.

In the most basic form of Q-Learning, our function is a table where every combination of observation and action corresponds to a score. This approach doesn't scale to harder games with more options, but it helps illustrate the approach. So our learning state needs an array to represent this "Q-table".

It will also need to store the current exploration rate and a random generator, which will tell us when to make random moves (and which random move to select).

data MazeLearnerState = MazeLearnerState
  { qTable :: A.Array (Word, Word) Double
  , explorationR :: Double
  , randomGenerator :: StdGen
  }

Now our monadic type will be a state over both this "Learner State" and the "Maze Game State".

newtype MazeLearnerM a = MazeLearnerM
  (StateT (MazeLearnerState, MazeGameState) IO a)
  deriving (Functor, Applicative, Monad)

instance (MonadState (MazeLearnerState, MazeGameState)) MazeLearnerM
  ...

Why does it need both? This becomes clear when we start making the instance. To implement liftEnv, we'll "get" the state, and then pass it by "running" the environment.

instance LearningEnvironment MazeLearnerM where
  type (Env MazeLearnerM) = MazeGameM
  liftEnv (MazeGameM action) = do
    (ln, gs) <- get
    (result, gs') <- liftIO $ runStateT action gs 
    put (ln, gs')
    return result

Of course, we'll also assign our learner state and the getter/setter combination.

instance LearningEnvironment MazeLearnerM where
  type (LearningState MazeLearnerM) = MazeLearnerState
  getLearningState = fst <$> get
  putLearningState ln' = do
    (_, gs) <- get
    put (ln', gs)
  ...

The rest of this definition is pretty simple boilerplate, except for choosing the action and learning. So let's see how to implement the Q-Learning approach with these.

Q-Learning

To start, let's assume we have some helper functions. I'll list the type signatures without getting bogged down in the definitions. We need to convert back and forth between an Observation (which is a Location) and its index within our Q-table (a Word).

locationToIndex :: Location -> Grid -> Word

indexToLocation :: Word -> Grid -> Location

We also need a maxScore function. This will take a location/observation index (so a Word) as well as the Q-table, and produce the maximum score we get from that observation, considering all the possible moves.

maxScore ::
  Word -> A.Array (Word, Word) Double -> (Double, (Word, Word))

Now when it comes to selecting an action, we have two main branches. We have to start by "rolling the dice" and determining if this will be a random/exploratory move, or a "brain" move with our Q-table.

chooseActionQTable :: MazeLearnerM Direction
chooseActionQTable = do
  lnSt <- getLearningState
  let (exploreRoll, gen') = randomR (0.0, 1.0) (randomGenerator lnSt)
  if exploreRoll < explorationR lnSt
    then ... -- Explore randomly
    else ... -- Use our Q-table

The random move is a matter of taking a second roll over our 5 action possibilities, updating the learning state with the new generator, and then returning the enum corresponding to the selected number.

chooseActionQTable :: MazeLearnerM Direction
chooseActionQTable = do
  lnSt <- getLearningState
  let (exploreRoll, gen') = randomR (0.0, 1.0) (randomGenerator lnSt)
  if exploreRoll < explorationR lnSt
    then do
      let (actionRoll, gen'') = randomR (0, 4) gen'
      putLearningState $ lnSt { randomGenerator = gen'' }
      return (toEnum actionRoll)
    else ...

Now to use our Q-table, we retrieve our environment, convert our location into an index, get the max score for that index, and again convert that to an enum (replacing the random generator again).

chooseActionQTable :: MazeLearnerM Direction
chooseActionQTable = do
  lnSt <- getLearningState
  let (exploreRoll, gen') = randomR (0.0, 1.0) (randomGenerator lnSt)
  if exploreRoll < explorationR lnSt
    then ...
    else do
      env <- liftEnv get
      let obsIndex = locationToIndex (playerLoc env) (gameGrid env)
      let maxIndex = snd $ snd $ maxScore obsIndex (qTable lnSt)
      putLearningState $ lnSt { randomGenerator = gen' }
      return (toEnum (fromIntegral maxIndex))

To improve this, we could use the set of possible action from our underlying state, rather than hardcoding [0..4].

The Learn Function

Most of the logic for our learning function is straightforward. We retrieve our learning state and the game grid. We determine indices for the input observations and action so we can index into our Q-table.

learnQTable ::
  Location -> Direction -> Location -> Reward -> MazeLearnerM ()
learnQTable loc1 direction loc2 (Reward reward) = do
  lnSt <- getLearningState
  let q = qTable lnSt
  grid <- gameGrid <$> liftEnv get
  let actionIndex = fromIntegral . fromEnum $ direction
      observationIndex1 = locationToIndex loc1 grid
      observationIndex2 = locationToIndex loc2 grid
      ...

For our next steps. First, we get the prediction score value from the Q-table. Then we determine the "target" score value. This is based on the actual reward we got and the best score we can get from our new location. This second piece allows us to "propagate" rewards from the end to more intermediate stages.

We determine a new value to place in the Q-table which comes from this difference, modified by the learning rate. And finally, we place this new value in our Q-table and update the learning state.

learnQTable ::
  Location -> Direction -> Location -> Reward -> MazeLearnerM ()
learnQTable loc1 direction loc2 (Reward reward) = do
  lnSt <- getLearningState
  let q = qTable lnSt
  grid <- gameGrid <$> liftEnv get
  let actionIndex = fromIntegral . fromEnum $ direction
      observationIndex1 = locationToIndex loc1 grid
      observationIndex2 = locationToIndex loc2 grid
      prediction = q A.! (observationIndex1, actionIndex)
      target = reward + gamma * (fst $ maxScore observationIndex2 q)
      newValue = prediction + learningRate * (target - prediction)
      newQ = q A.// [((observationIndex1, actionIndex), newValue)]
  putLearningState $ lnSt { qTable = newQ }
  where
    gamma = 0.96
    learningRate = 0.81

Ads an improvement, we could also make "gamma" and the learning rate part of our state and change them over time.

Evaluating Our Game

So what does it look like to run this? Well our game loop functions from up above will work, but it will help us to also keep track of how many iterations are needed to win AND what the cumulative reward is (rather than just the final reward).

We can now also include the (rather complicated) type signatures and other modifications we need to work with our class.

gameLearningLoop ::
  (LearningEnvironment m, EnvironmentMonad (Env m)) =>
  (Int, Reward) -> m (Int, Reward)
gameLearningLoop (i, oldReward) = do
  oldObs <- liftEnv currentObservation
  newAction <- chooseActionBrain
  (newObs, reward, done) <- liftEnv $ stepEnv newAction
  learnEnv oldObs newObs reward newAction
  let newReward = oldReward + reward
  if done
    then return (i, newReward)
    else gameLearningLoop (i + 1, newReward)

gameLearningIterations ::
  (LearningEnvironment m, EnvironmentMonad (Env m)) =>
  m [(Int, Reward)]
gameLearningIterations = forM [1..numEpisodes] $ \i -> do
  liftEnv resetEnv
  when (i `mod` 100 == 99) $ do
    reduceExploration decayRate minEpsilon
  (count, reward) <- gameLearningLoop (0, Reward 0.0)
  return (count, reward)
  where
    numEpisodes = 1000
    decayRate = 0.9
    minEpsilon = 0.01

And last but not least, a bit of code to run this loop with a starting environment. We'll return the rewards and results from the first 10 runs, as well as the last 10 runs.

runLearningWithBase :: IO ([(Int, Reward)], [(Int, Reward)])
runLearningWithBase = do
  gen <- getStdGen
  let lnSt = MazeLearnerState
               (A.listArray ((0, 0), (15, 4)) (repeat 0.0))
               0.9
               gen
  results <- evalStateT
    (runMazeLearner gameLearningIterations)
     (lnSt, baseEnvironment)
  return $ (take 10 results, (drop (length results - 10)) results)

runMazeLearner ::
  MazeLearnerM a -> StateT (MazeLearnerState, MazeGameState) IO a
runMazeLearner (MazeLearnerM action) = action

Results!

With a few tweaks to our reward system, we can get some good results. First, we'll have a score of 50.0 for reaching the goal. Then a score of -1.0 for making an illegal move, as well as a score of -0.1 for making normal moves, to encourage faster progress.

In our first set of runs, we get values that take a lot longer, often requiring 30-50 moves to reach the goal. One example takes 175 moves!

[
  (46,Reward 30.1),
  (26,Reward 40.2),
  (39,Reward 37.1),
  (45,Reward 31.1),
  (51,Reward 29.6),
  (45,Reward 30.2),
  (175,Reward (-17.0)),
  (59,Reward 26.1),
  (56,Reward 26.4),
  (30,Reward 34.4)
]

Then in the latter set, we can see that single digit results are common (5 is optimal). Scores are much closer to 50, with fewer illegal moves made. Though some will still exist, since the exploration rate in always non-zero.

[
  (6,Reward 48.5),
  (11,Reward 48.0),
  (7,Reward 47.5),
  (5,Reward 49.5),
  (6,Reward 49.4),
  (8,Reward 49.2),
  (13,Reward 46.0),
  (13,Reward 46.0),
  (7,Reward 48.4),
  (10,Reward 48.1)
]

Haskell Brain

A lot of more precise learning algorithms for harder problems will require you to use more advanced tools like TensorFlow. Lucky for you, our Haskell Brain course is now open for enrollment! This course will teach you how to use the Haskell TensorFlow bindings to write simple machine learning programs in Haskell! So if you've always wanted to do this kind of AI-related work in Haskell, but didn't think the language had the tools, now is your chance to learn how to use one of the most important libraries in this field. So sign up today!

Implementation: Creating a Maze Environment

In our last episode we explored the similarities and differences of the "World" idea from Gloss and the "Environment" of Open AI Gym. We designed a Haskell typeclass to capture this idea of an environment that could use associated data types connected for the specific game we're playing.

Now this week we're going to show this class in action. We're going to take our toy example of using BFS to search through a maze and we're going to make an Environment for it! We'll see how all these details fit together and we'll see the game play out in our console!

The code in this article is available on GitHub! For this article, you should focus on the MazeEnvironment module. If you'd like to watch this article as a video instead, take a look at this YouTube video!

There's also a special announcement at the end of this post if you're interested in AI and machine learning, so make sure you read to the end! Let's get started!

Defining Our Types

I may sound like a broken record at this point, but we're going to start by defining some types! First we'll make the State type for our environment, which will be functionally equivalent to our previous World type in Gloss.

data MazeGameState = MazeGameState
  { playerLoc :: Location
  , startLoc :: Location
  , endLoc :: Location
  , gameGrid :: Grid
  }

This state isn't the object of our class though! In order to do that, we have to build a monadic type. So what monad should we use? Naturally, we want to use the State monad to track our "State" type. Seems pretty obvious. We'll also include IO so that we can render our game later.

newtype MazeGameM a = MazeGameM (StateT MazeGameState IO a)
  deriving (Functor, Applicative, Monad)

Let's also define some basic monad instances like MonadState and MonadIO. This will make our life easier when we write our implementation code!

instance (MonadState MazeGameState) MazeGameM where
  get = MazeGameM get
  put env = MazeGameM $ put env

instance MonadIO MazeGameM where
  liftIO action = MazeGameM (lift action)

Instance Types

Now that we've got our monadic type we're ready to start making our instance. First, we want to assign the associated types. Remember these are the Observation type, the Action type, and the "Environment State" type.

When it comes to the observation, the "mutable" data we have in our game state is just the player's location. So we can assign Location as the corresponding type in our class.

For the "action", we have 5 options. We can move in any of the four cardinal directions, or we can make no move. So let's define an enum for that.

data Direction =
  MoveUp |
  MoveLeft |
  MoveDown |
  MoveRight |
  MoveNone
  deriving (Show)

And of course we'll use our state from above for the environment type. So here's what our instance looks like so far:

instance EnvironmentMonad MazeGameM where
  type (Observation MazeGameM) = Location
  type (Action MazeGameM) = Direction
  type (EnvironmentState MazeGameM) = MazeGameState
  ...

Simple Functions

Now we can start filling in the functions and expressions for the instance. To "reset" our environment, we just want to change the player's location to the start:

resetGame :: MazeGameM Location
resetGame = do
  current <- get
  put $ current { playerLoc = startLoc current }
  return (startLoc current)

Running the environment is also rather simple. Give an action in our monad, we'll unwrap its state action, run that with the given environment, and produce the IO action!

instance EnvironmentMonad MazeGameM where
  ...
  resetEnv = resetGame
  runEnv env (MazeGameM action) = evalStateT action env
  ...

After that, getting the "current" observation is as easy as querying for the player's location. And for "possible actions" we'll just return a full list of the enum values. If we wanted to get fancy, we could remove the option of moving into walls or off the board, but we'll need to handle that logic later anyways, so we'll keep this part simple.

instance EnvironmentMonad MazeGameM where
  type (Observation MazeGameM) = Location
  type (Action MazeGameM) = Direction
  type (EnvironmentState MazeGameM) = MazeGameState
  resetEnv = resetGame
  runEnv env (MazeGameM action) = evalStateT action env
  currentObservation = MazeGameM (playerLoc <$> get)
  possibleActions _ = return [MoveUp, MoveLeft, MoveDown, MoveRight, MoveNone]
  ...

Stepping Forward

We just have one field left, but it's the most complicated! We need to determine how to "step" the game based on an action. This will always be the toughest part because this is where all your game logic really happens! Our game is pretty simple though. Let's actually start with a few helpers.

First, let's determine if a space is a valid move in our grid. We just check that it's in bounds and that it is not a wall:

isValidLoc :: Location -> Grid -> Bool
isValidLoc (r, c) grid =
  r >= 0 &&
  c >= 0 &&
  r <= (fst . snd) (A.bounds grid) &&
  c <= (snd . snd) (A.bounds grid) &&
  grid A.! (r, c) == Empty

Now we want two functions that are kind of inverses. We'll use findNextLoc to take a current location and the direction, and give us the next location. Then moveDirection will do the opposite, taking a start and end point and giving us the direction between them.

findNextLoc :: Direction -> Location -> Location
findNextLoc MoveUp (r, c) = (r - 1, c)
findNextLoc MoveLeft (r, c) = (r, c - 1)
findNextLoc MoveDown (r, c) = (r + 1, c)
findNextLoc MoveRight (r, c) = (r, c + 1)
findNextLoc MoveNone (r, c) = (r, c)

moveDirection :: Location -> Location -> Direction
moveDirection (r, c) nextLoc
  | nextLoc == (r - 1, c) = MoveUp
  | nextLoc == (r, c - 1) = MoveLeft
  | nextLoc == (r + 1, c) = MoveDown
  | nextLoc == (r, c + 1) = MoveRight
  | otherwise = MoveNone

Now we're ready to write our step function. Recall that this function will take our game's action, which is a direction that we desire to move. We start by retrieving the game state and the current location.

stepGame :: Direction -> MazeGameM (Location, Reward, Bool)
stepGame direction = do
  current <- get
  let currentLoc = playerLoc current
  ...

Now we can find the next location based on this direction. If it's valid, we'll assign it as our "final" location (if not, we use the previous location). Then we save this in our state with "put".

stepGame :: Direction -> MazeGameM (Location, Reward, Bool)
stepGame direction = do
  current <- get
  let currentLoc = playerLoc current
  let nextLoc = findNextLoc direction currentLoc
  let finalLoc = if isValidLoc nextLoc (gameGrid current)
                   then nextLoc
                   else currentLoc
  put $ current { playerLoc = finalLoc }
  ...

Finally, we must determine our return values! Of course, the final location provides our new observation. If our new location is the final location, we'll provide the user with a "reward" of 1.0 and declare the game to be "done". Otherwise, we give no reward and the game goes on.

stepGame :: Direction -> MazeGameM (Location, Reward, Bool)
stepGame direction = do
  current <- get
  let currentLoc = playerLoc current
  let nextLoc = findNextLoc direction currentLoc
  let finalLoc = if isValidLoc nextLoc (gameGrid current)
                   then nextLoc
                   else currentLoc
  put $ current { playerLoc = finalLoc }
  let done = finalLoc == endLoc current
  let reward = if currentLoc /= finalLoc && done
                  then Reward 1.0
                  else Reward 0.0
  return (finalLoc, reward, done)

Filling this function in for stepEnv then completes our instance definition!

```haskell
instance EnvironmentMonad MazeGameM where
  ...
  stepEnv = stepGame

Playing Our Game

Now to play the game, we need to supply a "brain". That is, we need to be able to choose an action based on the game state. First, we retrieve the environment:

chooseMoveMaze :: MazeGameM Direction
chooseMoveMaze = do
  env <- get
  ...

With access to the game's grid and the relevant locations, we can then turn to our trusty Breadth-First-Search function!

chooseMoveMaze :: MazeGameM Direction
chooseMoveMaze = do
  env <- get
  let path = bfsSearch (gameGrid env) (playerLoc env) (endLoc env)
  ...

If there is no path, our direction is "None". Otherwise, we can take the first item from the path, and use moveDirection to calculate the direction we need. And then we're done!

chooseMoveMaze :: MazeGameM Direction
chooseMoveMaze = do
  env <- get
  let path = bfsSearch (gameGrid env) (playerLoc env) (endLoc env)
  case path of
    [] -> return MoveNone
    (move : _) -> return $ moveDirection (playerLoc env) move

Now we can play our game! We'll create a basic environment, and use gameLoop from last week, in conjunction with our brain function!

>> let baseEnv = MazeGameState (0,0) (0, 0) (2, 2) baseGrid
>> runEnv baseEnv (gameLoop chooseMoveMaze)

Rendering Our Game

This is great! We can now play our game...in theory. But in practice, we'd like to be able to see what's going on! So let's make a render function and make our environment renderable! Let's start by defining an ASCII character to correspond with each kind of location in the game.

1. Use 'o' for the player's location
2. Use 'x' for walls
3. Use 'F' for the "finish"
4. Use underscore '_' for blank spaces

This is a simple function to write:

charForLoc :: MazeGameState -> Location -> Char
charForLoc env loc = if loc == playerLoc env
  then 'o'
  else if loc == endLoc env
    then 'F'
    else if gameGrid env A.! loc == Wall then 'x' else '_'

Now to render, we just have to divide our Array into its constituent rows. The groupBy function is the easiest way to do this. We use the first element of the tuple index to do the matching.

instance RenderableEnvironment MazeGameM where
  renderEnv = do
    env <- get
    let rows = groupBy
                 (\((a, _), _) ((b, _), _) -> a == b)
                 (A.assocs (gameGrid env))
    ...

Now we just do a nested loop, and print the character for each cell!

instance RenderableEnvironment MazeGameM where
  renderEnv = do
    env <- get
    let rows = groupBy
                 (\((a, _), _) ((b, _), _) -> a == b)
                 (A.assocs (gameGrid env))
    forM_ rows $ \row -> liftIO $ do
      forM_ row $ \(l, _) -> putChar (charForLoc env l)
      putStr "\n"
    liftIO $ putStr "\n"

Now instead of using gameLoop like above, we can use gameRenderLoop!

>> let baseEnv = MazeGameState (0,0) (0, 0) (2, 2) baseGrid
>> runEnv baseEnv (gameRenderLoop chooseMoveMaze)
...

It will display the game at each stage so we can see our player moving along!

o___
_xx_
_xF_
____

_o__
_xx_
_xF_
____

__o_
_xx_
_xF_
____

___o
_xx_
_xF_
____

____
_xxo
_xF_
____

____
_xx_
_xFo
____

____
_xx_
_xo_
____

Special Announcement!

Now the only thing cooler than making a game with a working AI is having that AI learn for itself what to do! Next time, we'll modify our environment so it can use machine learning to improve an agent's behavior over time! We'll use a simple reinforcement learning approach to help our player navigate this simple maze.

If you've made it this far, you deserve to hear our special announcement, which is very much related to this idea of machine learning. One of the most important technologies when it comes to machine learning these days is TensorFlow. But as with Open Gym AI, most of the support for TensorFlow is in Python, not Haskell.

But a Haskell library does exist for TensorFlow! And today I am releasing a new course called Haskell Brain that will help you learn how to use this library. It goes over the basics of getting setup with Haskell and TensorFlow on your machine, as well as all the conceptual and syntactic ideas you need to get started writing your code. So if combining machine learning and Haskell sounds like a thrilling idea to you, then head to our course page now!