When we are in a process of learning Haskell, we often have trouble performing simple tasks like implementing common algorithms.

Often we get baffled when we navigate though the documentation as it seems to have a steep learning curve. There are lots of reference materials but not a lot of soft tutorials, that explain how to use the libraries or functions.

In this article we are going to show a step by step guide on how to read, practice and understand Haskell documentation pages.

Our aim is to make the hard reference documentation more approachable and readable. Let's get started.

Use case: Data.Array module

Let's take a simple case with the Data.Array module, which provides facilities for handling Immutable non-strict arrays.

Their main documentation page is listed here:

For reference, this documentation maps to the following source code.

Let's read the main description of the module:

Immutable non-strict arrays
Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers. Functions restricted in this way can be implemented efficiently; in particular, a programmer may reasonably expect rapid access to the components. To ensure the possibility of such an implementation, arrays are treated as data, not as general functions.

Since most array functions involve the class Ix, this module is exported from Data.Array so that modules need not import both Data.Array and Data.Ix.

module Data.Ix

There are a lot of terms listed here. Let's go through them one by one.

❓What are non-strict arrays?

Nonstrict arrays are arrays that are not lazy. This is because those arrays need to have a finite domain of values. Traditionally we know that lists in Haskell are lazy. If we want to implement indexable lists though, it turns out that, laziness is unsuitable for those operations.

Often for example when we want to access a range of values from the array, we want to evaluate them in parallel. That means we want immediate access and using laziness here makes things more computational expensive and inefficient.

If you want to read an interesting article about changing from list to array read this.

❓What are indexable arrays?

Indexable arrays are arrays that we can use an integer index to retrieve the nth element of the array.

Example. Get the first element of this array

a = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,5)]

Solution

We use the (!) operator passing the first index 0 to retrieve the first element:

a ! 0
1

Note that the array declares the starting index and the ending index in the first tuple (0,4).

If we were to request an index that is out of bounds we would get an error instead:

 a ! 5
*** Exception: Ix{Integer}.index: Index (5) out of range ((0,4))

❓What are random-access arrays?

Random access means not linear access. It means that we can access every element we want, independently on what other elements we accessed before or intend to access after and ideally in constant time O(1).

Note that we can use the regular Haskell list index function (!!) to retrieve the nth value from the least but that would traverse the whole list stoping at n, so making it an expensive operation with O(n) time complexity.

❓What other information we can infer from the above description?

We can infer that in order for Haskell to provide efficient random access arrays, then we need to treat arrays as data and not as functions. That's why when we import Data.Array we also import Data.Ix which is another class that is used to map a contiguous subrange of values in type onto integers and is used for array indexing.

We can briefly inspect the package documentation here.

Lets continue with the following documentation section:

data Array i e#

The type of immutable non-strict (boxed) arrays with indices in i and elements in e.

Instances
 IArray Array eSource#   
 Functor (Array i)  
Since: base-2.1

 Foldable (Array i) 
Since: base-4.8.0.0

 Ix i => Traversable (Array i)  
Since: base-2.1

 (Ix i, Eq e) => Eq (Array i e) 
Since: base-2.1

 (Ix i, Ord e) => Ord (Array i e)   
Since: base-2.1

 (Ix a, Read a, Read b) => Read (Array a b) 
Since: base-2.1

 (Ix a, Show a, Show b) => Show (Array a b) 
Since: base-2.1

This section here is quite valuable if you intent to use the Array module within certain operations as it describes the supported categories that Array implements.

❓What is instance in Haskell?

An instance is what we normally call Typeclass Instance in Haskell, which is a way to represent types which you can apply relevant typeclass functions.

So when the documentation lists for example that:

Functor (Array i) it means that Array follows or implements the Functor laws so it's essentially a Functor.

❓What is Functor in Haskell?

A Functor is a typeclass that allows a type to be mapped over. This means that we can use the fmap function over the Array elements.

Example. Apply fmap to double the elements on the following array:

a = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,5)]

Solution

The type of fmap for Array is defined as:

fmap :: (a -> b) -> Array i a -> Array i b

This means that it takes a function from type a to b and an Array of type a and returns an Array of type b.

So we have:

fmap (*2) a
array (0,4) [(0,2),(1,4),(2,6),(3,8),(4,10)]

Note: The definition of Functor for Array also implements left applicative (<$) which has a type signature:

(<$) :: a -> Array i b -> Array i a

That reads as: Create a new Array of type a from an Array of type b by replacing all of the values in the the first array by a given value of type a.

For example:

 1 <$ a
array (0,4) [(0,1),(1,1),(2,1),(3,1),(4,1)]

Such operator is useful for quick Array initialisation.

❓What is Traversable and Foldable in Haskell?

Let's describe Foldable first. It's another typeclass in Haskell that allows a container of values to be folded (or reduced) over a single value.

In our example, it means that we can use the foldl or foldr function over the Array elements.

A Traversable type is a kind of Foldable with the extra ability to change the shape of the array while iterating over its elements E.g. we can put new values.

We will understand how to use Foldable and Traversable typeclasses in the following examples.

Example. Calculate the sum of the elements of the following Foldable array:

a = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,5)]

Solution

We need to apply foldr to the Array a with initial value 0 and using the (+) accumulator.

How?

Let's inspect the type of the foldr function:

foldr :: (a -> b -> b) -> b -> Array i a -> b

That reads as: Start with an initial value of type b and an Array of type a and reduce the array into a type b using the folding function (a -> b -> b).

So we have:

foldr (+) 0 a
15

This is the same as:

1+(2+(3+(4+(5+0))))

Example. Convert all the elements of the following Traversable array from ints to strings:

a = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,5)]

Solution

We need to apply mapM to the Array a using the 'show' function to re-build the Array of ints into and Array of strings.

How?

Let's inspect the type of the mapM function:

mapM :: Monad m => (a -> m b) -> Array i a -> m (Array i b)

That reads: Map each element of the Array with type a to a monadic action, evaluate these actions from left to right, and collect the results into a monad that holds an Array of type b.

So we have:

mapM show a
[array (0,4) [(0,'1'),(1,'2'),(2,'3'),(3,'4'),(4,'5')]]

Here the monad is just another list.

❓What is Ord and Eq in Haskell?

The Eq typeclass defines equality (==) and inequality (/=). That means we can use those operators to compare Arrays.

Example. Compare the following arrays a and b for equality

a = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,5)]
b = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,6)]

Solution

a == b
False

That means that a and b are not equal.

The Ord typeclass is used for total ordering comparisons, for example we can use the compare or <= functions to get an Ordering.

Example. Compare the following arrays a and b for Ordering

a = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,5)]
b = array (0,4) [(0,1),(1,2),(2,3),(3,4),(4,6)]

Solution

a `compare` b
LT

Array a comes before b in regards to their default ordering as the last element of a is 5 and the last element of b is 6.

Conclusion and Next Steps

Given the examples above, I hope you have understood in general terms how to read Haskell documentation. It may be rough in the beginning but the more effort you put on, the more it makes sense.