Haskell/Building vocabulary

From Wikibooks, open books for an open world
Jump to navigation Jump to search

This chapter will be a bit of an interlude with some advice for studying and using Haskell. We will discuss the importance of acquiring a vocabulary of functions and how this book and other resources can help. First, however, we need to understand function composition.

Function composition[edit | edit source]

Function composition means applying one function to a value and then applying another function to the result. Consider these two functions:

Example: Simple functions

f x = x + 3
square x = x ^ 2

We can compose them in two different ways, depending on which one we apply first:

Prelude> square (f 1)
16
Prelude> square (f 2)
25
Prelude> f (square 1)
4
Prelude> f (square 2)
7

The parentheses around the inner function are necessary; otherwise, the interpreter would think that you were trying to get the value of square f, or f square; and both of those would give type errors.

The composition of two functions results in a function in its own right. If we regularly apply f and then square (or vice-versa), we should generate a new variable name for the resulting combinations:

Example: Composed functions

squareOfF x = square (f x)

fOfSquare x = f (square x)

There is a second, nifty way of writing composed functions. It uses (.), the function composition operator and is as simple as putting a period between the two functions:

Example: Composing functions with (.)

squareOfF x = (square . f) x

fOfSquare x = (f . square) x

Note that functions are still applied from right to left, so that g(f(x)) == (g . f) x. (.) is modeled after the mathematical operator , which works in the same way: .

Incidentally, our function definitions are effectively mathematical equations, so we can take

squareOfF x = (square . f) x

and cancel the x from both sides, leaving:

squareOfF = square . f

We will later learn more about such cases of functions without arguments shown. For now, understand that we can simply substitute our defined variable name for any case of the composed functions.

The need for a vocabulary[edit | edit source]

Haskell makes it simple to write composed functions and to define variables, so we end up with relatively simple, elegant, and expressive code. Of course, to use function composition, we first need to have functions to compose. While functions we write ourselves will always be available, every installation of GHC comes with a vast assortment of libraries (i.e. packaged code), which provide functions for many common tasks. For that reason, effective Haskell programmers need some familiarity with the essential libraries. At the least, you should know how to find useful functions in the libraries when you need them.

Given only the Haskell syntax we will cover through the Recursion chapter, we will, in principle, have enough knowledge to write nearly any list manipulation program we want. However, writing full programs with only these basics would be terribly inefficient because we would end up rewriting large parts of the standard libraries. So, much of our study going forward will involve studying and understanding these valuable tools the Haskell community has already built.

Prelude and the libraries[edit | edit source]

Here are a few basic facts about Haskell libraries:

First and foremost, Prelude is the core library loaded by default into every Haskell program. This ubiquitous library provides a useful set of functions, classes, and types. We refer to Prelude types and functions throughout these introductory chapters.

GHC provides a large set of core libraries having a wide range of tools, but only Prelude loads automatically. The other libraries are modules available for import into your program. Later on, we explain the minutiae of how modules work. For now, just know that your source file needs lines near the top to import any desired modules. For example, to use the function permutations from the module Data.List, add the line import Data.List to the top of your .hs file. Here's a full source file example:

Example: Importing a module in a source file

import Data.List

testPermutations = permutations "abc"

For quick GHCi tests, just enter :m +Data.List at the command line to load that module.

Prelude> :m +Data.List
Prelude Data.List> :t permutations
permutations :: [a] -> [[a]]

One exhibit[edit | edit source]

Before continuing, let us see one (slightly histrionic, we admit) example of what familiarity with a few basic functions from Prelude can bring us.[1] Suppose we need a function which takes a string composed of words separated by spaces and returns that string with the order of the words reversed, so that "Mary had a little lamb" becomes "lamb little a had Mary". We could solve this problem using only the basics we have already covered along with a few insights in the upcoming Recursion chapter. Below is one messy, complicated solution. Don't stare at it for too long!

Example: There be dragons

monsterRevWords :: String -> String
monsterRevWords input = rejoinUnreversed (divideReversed input)
    where
    divideReversed s = go1 [] s
        where
        go1 divided [] = divided
        go1 [] (c:cs)
            | testSpace c = go1 [] cs
            | otherwise   = go1 [[]] (c:cs)
        go1 (w:ws) [c]
            | testSpace c = (w:ws)
            | otherwise   = ((c:w):ws)
        go1 (w:ws) (c:c':cs)
            | testSpace c =
                if testSpace c'
                    then go1 (w:ws) (c':cs)
                    else go1 ([c']:w:ws) cs
            | otherwise = go1 ((c:w):ws) (c':cs)
    testSpace c = c == ' '
    rejoinUnreversed [] = []
    rejoinUnreversed [w] = reverseList w
    rejoinUnreversed strings = go2 (' ' : reverseList newFirstWord) (otherWords)
        where
        (newFirstWord : otherWords) = reverseList strings
        go2 rejoined ([]:[]) = rejoined
        go2 rejoined ([]:(w':ws')) = go2 (rejoined) ((' ':w'):ws')
        go2 rejoined ((c:cs):ws) = go2 (c:rejoined) (cs:ws)
    reverseList [] = []
    reverseList w = go3 [] w
        where
        go3 rev [] = rev
        go3 rev (c:cs) = go3 (c:rev) cs

There are too many problems with this thing; so let us consider just three of them:

  • To see whether monsterRevWords does what you expect, you could either take our word for it, test it exhaustively on all sorts of possible inputs, or attempt to understand it and get an awful headache (please don't).
  • Furthermore, if we write a function this ugly and have to fix a bug or slightly modify it later on,[2] we are set for an awful time.
  • Finally, we have at least one easy-to-spot potential problem: if you have another glance at the definition, about halfway down there is a testSpace helper function which checks if a character is a space or not. The test, however, only includes the common space character (that is, ' '), and no other whitespace characters (tabs, newlines, etc.).[3]

We can do much better than the junk above if we use the following Prelude functions:

  • words, which reliably breaks down a string in whitespace delimited words, returning a list of strings;
  • reverse, which reverses a list (incidentally, that is exactly what the reverseList above does); and
  • unwords, which does the opposite of words;

then function composition means our problem is instantly solved.

Example: revWords done the Haskell way

revWords :: String -> String
revWords input = (unwords . reverse . words) input

That's short, simple, readable and (since Prelude is reliable) bug-free.[4] So, any time some program you are writing begins to look like monsterRevWords, look around and reach for your toolbox — the libraries.

This book's use of the libraries[edit | edit source]

After the stern warnings above, you might expect us to continue diving deep into the standard libraries. However, the Beginner's Track is meant to cover Haskell functionality in a conceptual, readable, and reasonably compact manner. A systematic study of the libraries would not help us, but we will introduce functions from the libraries as appropriate to each concept we cover.

  • In the Elementary Haskell section, several of the exercises (mainly, among those about list processing) involve writing equivalent definitions for Prelude functions. For each of these exercises you do, one more function will be added to your repertoire.
  • Every now and then we will introduce more library functions; maybe within an example, or just with a mention in passing. Whenever we do so, take a minute to test the function and do some experiments. Remember to extend that habitual curiosity about types we mentioned in Type basics to the functions themselves.
  • While the first few chapters are quite tightly-knit, later parts of the book are more independent. Haskell in Practice includes chapters on the Hierarchical libraries, and most of their content can be understood soon after having completed Elementary Haskell.
  • As we reach the later parts of the Beginner's track, the concepts we will discuss (monads in particular) will naturally lead to exploration of important parts of the core libraries.

Other resources[edit | edit source]

  • First and foremost, all modules have basic documentation. You may not be ready to read that directly yet, but we'll get there. You can read the Prelude specification on-line as well as the documentation of the libraries bundled with GHC, with nice navigation and source code just one click away.
  • Hoogle is a great way to search through the documentation, beginner friendly. It covers a large set of libraries. You can search by function name (say, length) or by type ("function from lists to Int", which you'd write [a]->Int). This second type of search helps you find very specific functions and prevents reinventing the wheel.
  • Beyond the libraries included with GHC, there is a large ecosystem of libraries, made available through Hackage and installable with a tool called cabal. The Hackage site has documentation for its libraries. We will not venture outside of the core libraries in the Beginner's Track, but you should certainly use Hackage once you begin your own projects.
  • When appropriate, we will give pointers to other useful learning resources, especially when we move towards intermediate and advanced topics.

Notes

  1. The example here is inspired by the Simple Unix tools demo in the HaskellWiki.
  2. Co-author's note: "Later on? I wrote that half an hour ago, and I'm not totally sure about how it works already..."
  3. A reliable way of checking whether a character is whitespace is with the isSpace function, which is in the module Data.Char.
  4. In case you are wondering, many other functions from Prelude or Data.List could help to make monsterRevWords somewhat saner — to name a few: (++), concat, groupBy, intersperse — but no use of those would compare to the one-liner above.