Land of… F#

Posted by jcooper on March 4, 2011 None comments

I recently purchased the unique and fun Land of Lisp, which teaches the Common Lisp language and programming philosophy via a mix of wit, funny illustrations and comics, and interesting code examples. Specifically, many of the examples involve building old-school text adventure games (a la Zork), which many of us played and loved growing up.

I like the book, but I have some issues with the Common Lisp language and community (but that’s for another blog post). I decided, therefore, that instead of working through the examples in Common Lisp, I’d use F#, which I’m learning in my spare time. To pass on what I learned in this exercise, I decided to walk through my code here.

(Note that while I’m confident that the code is reasonably idiomatic, I’m by no means an expert F# programmer, so keep that in mind when analyzing my approach.)

To get started, we’ll declare our module and import supplementary libraries. A module in F# is a collection of values and functions. After the module declaration, you can import any libraries you’ll be using with open statements. I’ll just be using .NET’s System namespace, which gives access to common types like Console, which is used for inputting and outputting text to a terminal.

module TextAdventure
 
open System

Next, we’ll define types, which will act as the nouns upon which our verbs (functions) will operate.

type Location = Room | Garden | Attic
type Direction = North | South | East | West | Up | Down

The types Location and Direction are known as “union” or “variant” types–you can read the declaration as “The values Room, Garden, and Attic are Locations. Any given Location will have one of those three values.”

type Thing = { Name: string; Article: string }
type Edge = { Dir: Direction; Portal: string; Loc: Location }

These next two types are records, which are somewhat analogous to structs in C. Things will represent objects in the game world, and Edges (as in the mathematical term “edge” meaning a path that connects two nodes) will represent the pathways between areas in the game. The Thing declaration can be read as “A Thing consists of a Name string and an Article string.” Note how the Edge record contains fields of type Direction and Location, which we just defined above. F# is very strict in how it parses source code, and it does so from top-to-bottom, so you need to declare everything before you use it (that is, putting the definition of the Direction type after the Edge type would result in a compilation error).

type Player(initial: Location, objects: ResizeArray<Thing>) =
  let mutable location = initial
  member this.PickUp obj  =
    objects.Add obj 
  member this.Location 
    with get() = location
    and  set v = location <- v

The Player type is a bit more complicated. It’s actually a class, quite similar to classes in C# and many other OOP languages. In fact, the equivalent definition in C# would look like this:

class Player
{
	private Location location;
	private readonly List<Thing> objects;
	public Player(Location initial, List<Thing> objects)
	{
		location = initial;
		this.objects = objects;
	}
 
	public void PickUp(Thing obj)
	{
		objects.Add(obj);
	}
	public Location Location
	{
		get { return location; }
		set { location = value; }
	}
}

So that should be fairly straightforward; we will be keeping track of the location of the player and his inventory of objects. We now need a type to describe our game world, which will track which objects are where, which areas can be accessed and from where, and what areas look like. The game world will also hold our player via an instance of the aforementioned Player type.

type World() =
    let player = new Player(Room, new ResizeArray<Thing>())
    let mutable objects =
        [Room, [{ Name = "whiskey"; Article = "some" }; { Name = "bucket"; Article = "a" }];
        Garden, [{ Name = "chain"; Article = "a length of" }];
        Attic, []]
        |> Map.ofList
    let locations =
        [Room, "You are in a living room. A wizard is snoring loudly on the couch.";
        Garden, "You are in a beautiful garden. There is a well here.";
        Attic, "You are in an attic. There is a giant welding torch in the corner."]
        |> Map.ofList
    let edges =
        [Room, [{ Dir = West; Portal = "door"; Loc = Garden }; { Dir = Up; Portal = "ladder"; Loc = Attic }];
        Garden, [{ Dir = East; Portal = "door"; Loc = Room }];
        Attic, [{ Dir = Down; Portal = "ladder"; Loc = Room }]]
        |> Map.ofList
    member this.Locations = locations
    member this.Edges = edges
    member this.Player = player
    member this.Objects
      with get() = objects
      and  set v = objects <- v

World is another class. Upon its construction, we set its fields (player, objects, locations, and edges) to their initial values. Note that the latter three fields will be represented using maps, which are collections of key-value pairs (often referred to as dictionaries, hash tables, or associative arrays in other languages). You’ll notice that our locations consist of a wizard’s living room, attic, and garden, and that inside those areas you’ll find kooky things like whiskey, a bucket, and a length of chain.

If you’ve never looked at F# (or ML) code before, it might feel like you’re being bombarded with syntax here. Here’s a crash course:

  • Items separated by commas are tuples, which are rather like lists of set length.
  • The square brackets enclose elements of a linked list. Said elements are delimited inside the brackets with semicolons.
  • The curly braces are used for constructing values of record types, such as the Thing and Edge types we defined above. Note that the fields of a record type are all given values using the key = value syntax. Semicolons delimit one field from another.
  • The weird looking triangle thing is called the forward pipe operator, and it “feeds” the value on its left to the function on its right.

Alright. With our types defined, we are ready to write some functions.

let asOne strs =
    String.Join(" ", strs |> Array.ofSeq)
 
let describePath edge =
    (sprintf "%A" edge.Dir).ToLower() |> sprintf "There is a %s going %s from here." edge.Portal
 
let describePaths edges =
    edges |> Seq.map describePath |> asOne

These are some utility functions for describing and printing our area pathways. The describePath function will, when given an edge, return a string such as “There is a door going west from here.” We fill in terms such as “door” and “west” from the appropriate fields of the edge record. Its brother, describePaths, uses Seq.map to run describePath on every edge it’s given. Then it uses our asOne function to join all those descriptions into one string. (For more about mapping and concatenation, you should of course buy and read Land of Lisp!)

We’ll describe objects in an area similarly: 

let describeObjects objs =
    let describeObj obj = sprintf "You see here %s %s." obj.Article obj.Name
    objs |> Seq.map describeObj |> asOne

Now that we can describe what’s in an area, we’ll write a look function to get a complete description of the area where the player’s at.

let look (world: World) =
    let player = world.Player
    let loc = world.Locations.[player.Location]
    let paths = world.Edges.[player.Location] |> describePaths
    let objs = world.Objects.[player.Location] |> describeObjects
    [loc; paths; objs] |> asOne

In turn, we describe the current area (by indexing into the world‘s Locations map), run describePaths on the area’s edges, and describeObjects on the area’s objects. Then we join it all into one string.

The next important function our game needs to handle is moving around. Our walk function will take care of making sure there’s an edge in the specified direction, and if so, changing the player’s location to the next area.

let walk dir (world: World) =
    let player = world.Player
    let attempt = world.Edges.[player.Location]
                  |> List.filter (fun e -> e.Dir = dir)
    match attempt with
    | [] -> "You can't go that way."
    | edge :: _ -> 
        world.Player.Location <- edge.Loc
        sprintf "You go %A..." dir

We start by filtering the list of an area’s edges by the passed-in direction. The filter function takes a function and a list, and applies the function to each element of the list. It spits out a new list containing only those elements for which that function (also called a predicate) returns true. Using a predicate to filter unwanted values from lists is a staple of functional programming.

Next we see the first instance of pattern matching, a very common F# technique. It’s superficially related to the switch statement in other languages, but it’s much more powerful. It takes an input and a set of rules to test against that input. Here, we check to see if the result of our filter was the empty list []. If so, it means the specified edge wasn’t in the area’s edge list, and is thus an invalid direction. If there was a result, we use that result as the player’s new location. You can read more about pattern matching here.

Now that we can look and move around, one more thing remains: Picking up objects.

let pickUp thing (world: World) =
    let player = world.Player
    let objs = world.Objects.[player.Location]
    let attempt = objs |> List.partition (fun o -> o.Name = thing)
    match attempt with
    | [], _ -> "You cannot get that."
    | thing :: [], things ->
        world.Player.PickUp thing
        world.Objects <- world.Objects.Remove player.Location
        world.Objects <- world.Objects.Add(player.Location, things)
        sprintf "You are now carrying %s %s." thing.Article thing.Name
    | _ -> "I don't know what you mean."

We employ a similar technique here as we did when checking for a valid direction. We want to make sure the object the user is trying to obtain actually exists in the area. For this, we use the partition function, which is just like filter except it returns both the matches and the misses. If the match list is empty, they didn’t specify an actual extant item. if there was, we add it to the player’s inventory (via its PickUp method). We also need to update the items in the area to reflect that item’s absence. Here I elected to do two updates, but you could just as easily use a mutable data structure. Note that I haven’t been sticking to a purely functional style in this program, but neither did the example in Land of Lisp. F# is friendly to both imperative and functional styles.

That’s the meat of our game; the rest is just handling I/O. I’ll put the rest of the code below, which hopefully is pretty self-explanatory. Note especially the use of match expressions.

let getLastWord (phrase: string) =
    let words = phrase.Split ' '
    words.[words.Length - 1]
 
let parsePickUp cmd world =
    let obj = getLastWord cmd
    pickUp obj world |> printfn "%s"
 
let parseWalk (dir: string) world =
    let direction = 
        match dir with
        | d when d.StartsWith "e" -> Some East
        | d when d.StartsWith "n" -> Some North
        | d when d.StartsWith "s" -> Some South
        | d when d.StartsWith "w" -> Some West
        | d when d.StartsWith "u" -> Some Up
        | d when d.StartsWith "d" -> Some Down
        | _ -> None
    match direction with
    | Some d -> walk d world |> printfn "%s"
    | None -> printfn "You can't go that way."
 
let parseMovement cmd world =
    let dir = getLastWord cmd
    parseWalk dir world
 
let rec handleInput world =
    printf "> "
    let input = Console.ReadLine().Trim().ToLower()
    match input with
    | "quit" | "exit" | "leave" -> 
        printfn "Goodbye!" 
        world, true
    | "look" -> world, false
    | "n" | "s" | "e" | "w" | "u" | "d" | "up" | "down" | "north" | "south" | "east" | "west" ->
        parseWalk input world
        world, false
    | cmd when cmd.StartsWith "go "  || cmd.StartsWith "walk"  || cmd.StartsWith "climb"  ->
        parseMovement cmd world
        world, false
    | cmd when cmd.StartsWith "take"  || cmd.StartsWith "get"  || cmd.StartsWith "pick"  ->
        parsePickUp cmd world
        world, false
    | other ->
        printfn "You can't %s here." other
        handleInput world
 
let rec gameLoop world =
    look world |> printfn "%s"
    match handleInput world with
    | _, true -> ()
    | w, _ -> gameLoop w
 
new World() |> gameLoop

As is sometimes the case in F# code, due to how it must be written, it helps to “start with the bottom.” We define a gameLoop function that will prompt the user for input and refresh the description as needed. Note we defined it to be recursive (it can call itself), using let rec. The handleInput function is likewise recursive, and returns two values that gameLoop looks at: the updated value of the game world (containing, for example, the player’s new location after moving) and whether or not the game has finished. As you can see, if the player types any of “quit,” “exit,” or “leave,” we return true for the latter value. When gameLoop sees that, it simply returns () (pronounced “unit”), equivalent to returning in a void function in many languages.

The other actions the player can take are parsed out, and wired back to the functions we defined for them previously. We try to handle a couple different ways of saying the same thing, but of course the list isn’t exhaustive, so the last clause in our match acts as a catch-all.

That’s about all there is to it! Admittedly the gameplay is on the basic side, but it’s easy to see how it could be expanded. (And indeed the later game examples in Land of Lisp are more meaty.)

Incremental Haskell III: Tokyo Drift

Posted by jcooper on November 2, 2009 None comments

Prelude

This is part 3 in a series of articles designed to help those new to Haskell work through the highly-recommended book, Real World Haskell. In them, I try to keep things at a digestible pace and not to presuppose too much. Here are links to the previous articles. I hope you find these helpful, and welcome comments on the Haskell subreddit.

Mo’ problems, mo types

As we mentioned in the previous article, it would be nice to be able to customize our JSON output. Right now, we have a default implementation of printing output that isn’t very flexible, not supporting things like “word wrapping” (soft line breaks).

Certainly, being able to format output text in a flexible manner is not a problem specific to JSON (though that will be our current application of it). Because it’s a new “problem to solve,” we’ll start from the top with a new type. We want to represent a chunk of text that can be formatted.

data FormattedText =

The simplest type of formatting is no formatting at all (just like momma always said).

data FormattedText = Text String

We want the ability to break text over more than one line if it’s too wide. We’ll add a data constructor to our type that represents these line breaks. Then when we go to render the text, when we match this constructor, we can go to the next line.

data FormattedText =  Text String
                    | Linebreak

We also want to support a soft line break, which will be a space character if we aren’t out of space on a line, or a newline otherwise. So we’ll make a WithOptionalBreaks data constructor to represent this.

data FormattedText =  Text String
                    | Linebreak
                    | WithOptionalBreaks FormattedText FormattedText

As you can imagine, a real document (JSON or otherwise) is going to consist of chunks of text combined together. Some chunks will have different formatting than others, but together they make up a whole document of formatted text, which we can call a formatted document. And since a formatted document is just formatted text, if we combine it with more formatted text, we still have a formatted document. I hope that makes sense, even if it does involve some “recursive thinking.” The concept translates very well into Haskell:

data FormattedText =  Text String
                    | Linebreak
                    | WithOptionalBreaks FormattedText FormattedText
                    | FormattedDocument FormattedText FormattedText

That is, we represent a whole document as two chunks of FormattedText, which can include plain Text, Linebreaks, even other FormattedDocuments that are themselves made up of the same thing. If you know anything about data structures, you’ll recognize a tree structure here.

Defining custom operators in Haskell

Almost every language has operators, which give abstract symbols meaning to make certain expressions read more smoothly. Of course, this concept originally comes from mathematics, where being able to tersely express things is important.

Languages with operators tend to at least include ASCII equivalents of the basic arithmetic symbols like + and -. Some language designers decided to “overload” operators, giving them different meanings depending on context. In Java, for example, you concatenate strings thus:

String newString = "hello " + "world";

Most people tend to be in favor of operators; having to write Plus(1, 3) every time you wanted to add 1 and 3 isn’t quite as convenient, and one could argue less readily apparent. Not everyone is in agreement on operator overloading, however, as it can introduce ambiguity when one symbol has more than one meaning.

Haskell programmers are big fans of operators. I’m sure this has a lot to do with the math culture that is quite prevalent in the community and user base. Haskell and its community are quite bold in using abstract concepts in everyday code, and often it makes more sense to define an operator than give an otherwise inadequate name to a function.

The language lets you define your own operators, including precedence. Functions that you name using only non-alphanumeric symbols are automatically considered operators and can be used just like you’d use + or -. Just like functions, operator names need to be unique and there is no overloading allowed (in the traditional sense). That is, you don’t see 1 + 1 on one line and “hello ” + “world” on the next. The (+) function is coded to accept only numeric inputs, and so there wouldn’t be a way to add Strings with (+) without String being numeric.

So what’s that have to do with what we’re doing?

The type we just wrote is perfectly suited to having a custom operator or two to help us out. Right now, if we want to build a document up out of text chunks, we have to do something like this:

FormattedDocument (Text "hi") (FormattedDocument (Text "howdy") (Text "hello"))

We can quickly and easily define an operator that makes the concept of combining text more palatable:

(<++>) :: FormattedText -> FormattedText -> FormattedText
textChunk <++> anotherChunk = FormattedDocument textChunk anotherChunk

Since FormattedText concatenation is conceptually kinda like String concatenation, I chose an operator that looks like (++).

Now we can avoid “parentheses nesting hell”:

Text "Knights " <++> Text "who say" <++> Linebreak <++> Text "ni"

As you can see above, we can add text to other text, and add line breaks where we want. We can use this same approach for our optional line breaks. Let’s make another operator that represents a possible breaking spot in a line:

(</>) :: FormattedText -> FormattedText -> FormattedText
textChunk </> anotherChunk = textChunk <++> softLineBreak <++> anotherChunk

So when we two pieces of text, we join them together with a soft line break–the kind that ends up being a newline if anotherChunk didn’t fit on the current line. Otherwise, it’ll just become a space.

Our WithOptionalBreaks constructor handles these two possibilities (break or just space) for us:

softLineBreak = WithOptionalBreaks (Text " ") (Linebreak)

Back to rendering JSON

Now that we have our type and the ability to combine values of our type, let’s take a look at how we’ll use it to “pretty print” a JSON string value. This isn’t quite as trivial as it sounds because we need to pay attention to characters in the string that need to be escaped with backslashes.

renderJsonString :: String -> FormattedText
renderJsonString string = Text "\"" <++> Text (escapeChars string) <++> Text "\""
    where escapeChars chars = concatMap escapeChar chars
          escapeChar char   = -- ??

We’re breaking the problem into chunks, keeping individual functions small. Our main function, renderJsonString, just surrounds the string in quotation marks, and then calls a helper function escapeChars on the string. escapeChars, in turn, is going to concatMap an escape function over each individual character in the string.

In case you still aren’t used to the map family of functions yet, they’re the ones that pass each element of a provided list to a specified function. A new list is returned containing the results of each function application. In this case, each result is going to be a String (which, don’t forget, is just a [Char]). We only want one String out of our escapeChars function, so we use the concatMap version of map. It just smooshes all the results together, which is great for scenarios like this.

On patterns that need to be matched

In the previous installment, we talked about covering all our bases when pattern matching. If you are matching against a Maybe, it’s a good idea to think about what happens if the value is Nothing as well as if it is Just something. If our input is a list, what if it’s empty?

These are great things to think about to avoid errors. However, Haskell programmers feel very passionate about avoiding redundant code, so it’s okay to avoid special-casing a pattern if we won’t gain anything by it. The escapeChars function above is a good example, as it takes a list. We could have done the following:

escapeChars [] = ""
escapeChars chars = concatMap escapeChar chars

But actually we don’t need to, because concatMap already handles the empty list case for us in the same way! (If the list passed to concatMap is empty, it returns an empty list. In Haskell this looks like:)

concatMap _ [] = []

(Remember, the underscore pattern is used when we don’t care about the value of an argument. In this case, it doesn’t matter what function is passed to concatMap, if the list is empty, it just returns [].)

Escaping special characters

Our escapeChar function will take a character from a string, find out if it needs to be escaped, and if so, return an escaped version. Otherwise it’ll just return the character.

-- ...
          escapeChar char   = case lookup char asciiEscapeTable of
                                Just escaped -> escaped
                                Nothing      -> -- ??

Here, we are pattern matching the result of our check. The check is done with the lookup function, a standard library function which searches a list of key-value pairs for a given key (in our case, the character we’re checking). Since lookup returns Maybe a result, we match against Just (meaning the character was found in the list of characters-needing-escape) and Nothing. For the first case, we grab the escaped string and return it.

Our list of escaped characters, asciiEscapeTable, contains the most common escape sequences. We will build it by feeding a table-creation function two lists: a list of characters that need escaping, and a list of their escaped versions.

asciiEscapeTable :: [(Char, String)]  -- a list of key-value pairs, commonly called an 'association list'
asciiEscapeTable = mysteryTableMakerFunction ['\b','\n','\f','\r','\t','\\','"','/'] ["\\b","\\n","\\f","\\r","\\t","\\\\","\\\"","\\/"]

So far, so good–assuming we can find a function that takes two lists and makes one list of pairs out of them (sequentially pairing one element from the first list with one from the second). If we think about what the type of such a function would be, we come up with:

[a] -> [b] -> [(a, b)]

Remember Hoogle? If we go there and search for a function with that type, it tells us straight away that the function we want is called zip, and it’s in the Prelude so we don’t even need to import it. (In fact, zip is a common functional programming building block.)

asciiEscapeTable = zip ['\b','\n','\f','\r','\t','\\','"','/'] ["\\b","\\n","\\f","\\r","\\t","\\\\","\\\"","\\/"]
But hey, lists of Chars are Strings, you tell us that all the time. And all our escapes are done with backslashes!

Very true. Using those facts, we can write a version that’s easier to type, if we want:

asciiEscapeTable = zipWith addBackslash "\b\n\f\r\t\\\"/" "bnfrt\\\"/"
    where addBackslash input output = (input, ['\\', output])

The zipWith function lets us apply a helper function before it combines the pair into a list element. We use it to simply prepend a backslash to every element of our output list.

And if the lookup returns Nothing?

Unfortunately, we aren’t done yet. We can’t just return the character because it might be a Unicode character that requires escaping, and our nice little escape table earlier was ASCII only. So we need another check to see if this is the case:

-- ...
                                Nothing | needsUnicodeEscape char -> unicodeEscape char
                                        | otherwise               -> [char]
 
needsUnicodeEscape :: Char -> Bool
needsUnicodeEscape char = char < ' ' || char == '\x7f' {-- ASCII 'del' --} || char > '\xff'

So we changed the second pattern in our case statement to be more specific, using guards. Guards allow you to specify further conditions on a pattern match. Our first guard does a check to see if we need to escape the character in a more complex way (using RWH’s choice of escaping all non-printable ASCII characters). The other guard, the otherwise, just returns the character because it means it doesn’t need escaping. (We made a singleton list out of char because the other branches of the statement are returning a String, not just a single Char, and we need to be consistent.)

Now we need to write our unicodeEscape function. To do this, we need to turn the character into a string representing its numeric Unicode value. This means a backslash, a u, and a four-digit hex string. (The JSON standard requires this format.)

unicodeEscape :: Char -> String
unicodeEscape char = "\\u" ++ padWithZeroes (toHex char)
    where padWithZeroes string = -- ??
          toHex char = -- ??

We need to ensure our hex value is four digits, so we’ll pad it with zeroes if necessary. This means finding out the length of our hex, and throwing a 0 in front for each place less than four.

To help us, we’ll use a handy little function called replicate that (as you’d expect) replicates its argument. You specify how many times it should do this.

-- ...
    where padWithZeroes string = replicate (4 - length string) '0' ++ string

In order to convert a character to its hex value, we first need to get a numeric value of the Char. Hoogle can help us if we search for the type signature of such a function (that is, Char -> Int). The result that suits our needs is ord, in Data.Char (it gives the ordinal value of a character). We then need to turn our numeric value into a hex string. The Numeric module provides such a function: showHex. If we import the Numeric and Data.Char modules at the top of our file, we can finish up our toHex function snappily:

-- ...
          toHex char = showHex (ord char) ""

(showHex actually takes another argument after the input number–a String. This has uses, but we won’t bother with it here, so we just feed it an empty string.)

A note on correctness

Though our function is pretty good, Unicode values actually go up higher than the JSON “\uxxxx” syntax allows. The standard describes how to express characters that have values higher than four digits. RWH has already implemented this; look for the astral function in chapter 5. Feel free to incorporate it if you want!

Now to pretty printing!

Now that we have our string rendering, we’re ready to get on to flexible output formatting. We’ll start with a type signature:

printWithWidth :: Int -> FormattedText -> String

The Int parameter will represent the maximum width of a line. Remember our soft line breaks? If one of those occurs in our text, we can use this width information to determine whether or not to begin a new line.

Our implementation will use the different constructors we defined for FormattedText to our advantage: we’ll use them as instructions about how to print.

printWithWidth width formattedText = processText 0 [formattedText]
    where   processText column (textChunk : remainingText) =
                        case textChunk of
                            Text string                     -> string ++ processText (column + length string) remainingText
                            Linebreak                       -> '\n' : processText 0 remainingText
                            FormattedDocument part1 part2   -> processText column (part1 : part2 : remainingText)
                            WithOptionalBreaks noBr withBr  -> nicestFit column (processText column (noBr : remainingText))
                                                                                (processText column (withBr : remainingText))
            processText _ _ = ""

A line-by-line explanation might help.

Right away, we pass column number 0 and a list containing what our function was passed to a helper function. Then we define said helper function, and have it match against every possible sort of FormattedText. The column variable will track our current position in a line. So when processText gets a string of Text, it increments the column variable by the length of the string and emits the string. When it gets a Linebreak, it emits a newline character, and resets the column count because we’re now on a fresh line. In both cases, we recursively continue processing the [formattedText] list.

But that list only has one element, right?

Well yes, at the start. But if we pass in a FormattedDocument (which as you remember, contains other FormattedTexts), we grow our remainingText list by prepending both halves of the document “tree.” This action in and of itself doesn’t move our column position on the line; the recursive call to processText will take care of that later.

The most interesting piece

Remember we made the WithOptionalBreaks constructor to hold the two versions of a soft line break: the space version, and the newline version. The reason we did this will now become clear. What we’re going to do with our nicestFit function is compare the lengths of those two versions of text based on what column position we’re on in the line. If the “no breaks” version would be too long, we’ll emit the version with line breaks.

-- ...
            nicestFit column version1 version2 = if version1 `fitsIn` spaceRemaining
                                                 then version1
                                                 else version2
                        where spaceRemaining = width - (min width column)
 
fitsIn :: String -> Int -> Bool
_              `fitsIn` remainingWidth | remainingWidth < 0 = False
""             `fitsIn` remainingWidth                      = True
('\n':_)       `fitsIn` remainingWidth                      = True
(char : chars) `fitsIn` remainingWidth                      = chars `fitsIn` (remainingWidth - 1)

Hopefully those two functions are pretty straightforward. Hitting our WithOptionalBreaks constructor causes our nicestFit function to test both the versions it contains by seeing if there’s enough space for the “no breaks” version. It does this by testing one character at a time vs. the remaining width on the line. If we get to the end of the string (“”) or a newline, it fits. Otherwise we return False, which means we’ll emit the version with line breaks.

A side note on self-instruction

Though once you are used to it, you’ll be able to instantly figure out what recursive functions like the ones above do, you might becoming from an imperative language background, where recursion is uncommon at best. There’s nothing to be scared of, but I do recommend sitting down and working through all the steps in evaluating a recursive procedure every now and then. It might be helpful to sit down with GHCi and maybe even a pencil and work through a step-by-step evaluation of a call to printWithWidth.