Diving deeper

length1 :: [a] -> Int
length1 l = go l 0
  where go []     acc = acc
        go (x:xs) acc = go xs (acc+1)

main = putStrLn ("length1 [1, 2, 3] = " ++ show (length1 [1,2,3]))

length1 :: [a] -> Int
length1 l = go l 0
where go [] acc     = acc
      go (x:xs) acc = go xs (acc+1)

main = let x = product [1..] in print (length1 [1, x])

data [] a = [] | (:) a [a]
-- or alternatively, a definition you can actually give to GHC:
data List a = Cons a (List a) | Nil

  length1 [1, x]
= length1 1:(x:[])      -- just rewriting for clarity
= 1 + length1 (x:[])    -- 1:(x:[]) satisfies the (x:xs) pattern, so that clause gets chosen
= 1 + 1 + length1 []    -- the very same goes for (x:[])
= 1 + 1 + 0             -- [], however, satisfies the first pattern, that of the empty list
= 2

weirdLength :: [Int] -> Int
weirdLength []                 = 0                  -- nothing surprising here, 
                                                    -- just like before
weirdLength (x:xs) | x < 0     = weirdLength xs     -- negative number, we do not 
                                                    -- account for it
                   | otherwise = 1 + weirdLength xs -- positive number, we add one to the "length of the rest of the list"

main = let x = product [1..] in print (weirdLength [1, x])

  weirdLength [1, x]
= weirdLength 1:(x:[])   -- just rewriting for clarity
= 1 + weirdLength (x:[]) -- 1:(x:[]) satisfies the (x:xs) pattern, and 1 is positive, 
                         -- so we enter the last clause
= 1 + ???                
-- x:[] matches the second pattern (x:xs), but is x negative? 
-- We don't know unless we compute it, which the
-- runtime does... but it will never terminate.

-- Maybe is defined as:
-- data Maybe a = Nothing | Just a

isNothing :: Maybe a -> Bool
isNothing Nothing  = True
isNothing (Just _) = False

main = let x = product [1..] in do 
  print $ isNothing Nothing
  print $ isNothing (Just 4)
  print $ isNothing (Just x)

concatenate :: [a] -> [a] -> [a]
concatenate [] l = l
concatenate (x:xs) l = x : concatenate xs l

mix :: [a] -> [a] -> [a]
mix [] l2 = l2
mix l1 [] = l1
mix (x1:x1s) (x2:x2s) = x1 : x2 : mix x1s x2s

silly :: [Int] -> [a] -> [a]
silly [] _ = []
silly _ [] = []
silly (x:xs) (y:ys) | x == 0    = silly xs ys
                    | otherwise = y : silly xs ys

Laziness in the GHC runtime system

The GHC runtime implements laziness mostly through what it calls thunks. You can picture a thunk as a box containing some expression that hasn’t been evaluated yet. Whenever the actual value of that expression is needed, the runtime will open the thunk and evaluate what’s inside it. That thunk may itself refer to other thunks that haven’t been evaluated yet either, and will thus make the runtime open and evaluate them too. Once the expression is evaluated (if the said expression terminates, that is, yields a value), the runtime system overwrites the thunk, replacing the “pointer” to the expression to evaluate by the actual result. For a deeper and longer explanation about laziness and the (GHC) Haskell heap, see Edward Z. Yang’s great blog post series, which starts here. You can read them after this article, since I try to give an intuition regarding how it works without building on top of it, but you should read them at some point if you care about how GHC executes your code (say, if you care about performance or timely resource management for example).

The thing you have to keep in mind though, is that basically anything creates a thunk in (GHC) Haskell, by default. This is GHC’s implementation of non-strictness, as required in the Haskell report, and gives us lazy evaluation. Consider the following code:

map negate [1,2,3]
-- reminder: this is equivalent to map negate (1:2:3:[])

How is this evaluated?

At the beginning, the whole expression is just a thunk. I will denote the thunks by <thunk: expression-to-be-evaluated> – this is not my invention, I have seen this in a few places already, including in this talk by Trevor Caira at NYC Haskell, which I recommend. So at the beginning, everything is just:

<thunk: map negate <thunk: (1:2:3:[])>>

What does map’s code look like?

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

In our case, we first go in the second clause. So we now have:

<thunk: negate <thunk: 1> : <thunk: map negate <thunk: [2,3]>>

negate x = -x. Then on to:

-<thunk: 1> : <thunk: map negate <thunk: [2,3]>>

and

-1 : <thunk: map negate <thunk: [2,3]>>

We have to evaluate the rest now, in the same way we tackled map negate [1,2,3] at the beginning, except that we have processed one element.

-- we evaluate [2,3] to WHNF just to figure out we enter the second clause of map
-1 : <thunk: negate <thunk: 2>> : <thunk: map negate <thunk: [3]>>
-- we evaluate negate as with 1
-1 : -<thunk: 2> : <thunk: map negate <thunk: [3]>>
-1 : -2 : <thunk map negate <thunk: [3]>>
-1 : -2 : <thunk: negate <thunk: 3>> : <thunk: map negate <thunk: []>>
-1 : -2 -<thunk: 3> : <thunk: map negate <thunk: []>>
-1 : -2 : -3 : <thunk: map negate <thunk: []>>
-1 : -2 : -3 : [] -- we encountered -> first clause of map

Now consider take 6 . map (+1) $ [1..10]. The map will of course be evaluated in the same way. However, lazy evaluation will make the runtime enter the take call first. Let’s suppose take is defined in the following way.

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

Then we will just run the third clause and evaluate x+1 until n falls down from 6 to 0. The important thing to remember here is that evaluation starts in the outermost expression.

Laziness happens at each “level”, meaning you can evaluate what constructor was used (Just or Nothing, for example), then force the evaluation of what constructor was used for the data stored inside the Just, and so on. Getting top performance from your Haskell code generally means tailoring the evaluation of your data to the specific way it’s exploited in your case. If you read a lot of data from a file and process, say, each line separately, not reading the whole file at once in memory is a good idea. A good implementation would read the data and produce a list of lines “on-demand”. Then the function processing each line would take that list as an argument and consume it as it is being produced, doing the processing with O(1) space usage.

Bang Patterns

One very easy way is to use a strictness annotation for function arguments, through ! (pronounced bang). It requires a GHC extension (not a dangerous one, don’t worry), called BangPatterns. You may enable it by giving GHC/GHCi the -XBangPatterns argument, or by writing {-# LANGUAGE BangPatterns #-} at the very top of your file (preferred method). Here is our sum function, fixed.

{-# LANGUAGE BangPatterns #-}

sum :: Num a => [a] -> a
sum xs = go xs 0
  where go []     !acc = acc
        go (x:xs) !acc = go xs (acc + x)

Notice the two !’s right before acc. What’s happening is that these bangs ask that whenever one of these patterns is matched, the runtime should force the evaluation of the second argument, acc, before computing the RHS. However, it doesn’t evaluate to normal form but “only” to weak head normal form, whatever the type of the argument is. It is however enough for accumulators like numbers. But if we had written sum !xs instead of sum xs, it would only force the evaluation of the first cons-constructor ((:)) of the list, seeing unevaluated-head : unevaluated-tail-of-the-list. The same goes for values of type Maybe Int where it would evaluate whether the value is Nothing or Just unevaluated-content. And now, sum’s behavior:

  sum [1..5]
= go [1..5] 0  -- sum's definition
= go [2..5] 1  -- go's second clause, addition not piling up because 'acc' is evaluated
= go [3..5] 3  -- same
= go [4,5]  6  -- same
= go [5]    10 -- same
= go []     15 -- same
= 15           -- go's first clause

Hah, much better! That’s about all there is to the bang pattern though. It comes in very handy when you don’t want a lot of thunks to pile up on arguments that have “simple types”, i.e where weak head normal form also is normal form, or where just forcing the constructor is really what you want and is enough, but the former is a much common criterion. For your custom data types or more complex structures, there’s something similar but much more appropriate.

Strict fields in data types

Somehow dual to the need for strictness in accumulators mentionned above, sometimes we also want to evaluate values before we put them as some field in a data type. Imagine you’re doing a bunch of matrix/vector operations. As a matter of fact, that’s precisely what I had to do when I implemented the backpropagation learning algorithm in my neural networks library. We do not want for the operations to pile up before being evaluated there! That would mean that thousands and thousands of arithmetic operations would have to be performed pretty much in one shot at the end to compute the new matrices, the output of the neural network on all input vectors and what not. That’s just something we can’t decently work with. So we somehow have to force the evaluation of all our matrix and vector coefficients right away, but throwing a lot of bangs at our code will be cumbersome, inelegant and we would have that feeling that there must be a better way to do it. Well, we would be right! And, to be honest, we will be throwing a bunch of !’s at our code there too, but differently.

Keeping our matrix example, but simplifying it a bit, we will write a 2x2 matrix data type that will be strict in all its fields. No language extension needed this time though!

data Matrix2 a = M2 !a !a !a !a -- the four coefficients of our 2x2 matrix
-- here the coefficients can be of an arbitrary type, but this would
-- work too, only restricting us to Double coefficients:
data Matrix2 = M2 !Double !Double !Double !Double

That’s it! I will let you check that the fields indeed get evaluated when we create a value of type Matrix2 by creating a matrix whose coefficients are all equal to product [1..].

data Matrix2 = M2 !Double !Double !Double !Double deriving Show

main = do
  print (M2 1 2 3 4)
  -- this won't terminate
  let x = product [1..] in print (M2 x x x x)

You can see that here, all fields are marked with a !, but you can specify some strict fields and some non-strict ones, by just putting a ! right before the fields you want to be strict.

data Pair a b = Pair !a b

data Text = Empty
          | Chunk {-# UNPACK #-} !T.Text Text

{-# UNPACK #-} and unboxed strict fields

Unpacking strict fields in data types is one of the key techniques for writing efficient Haskell code. But before introducing it, let’s state the problem it solves.

Like in many programming languages, by default, GHC’s runtime doesn’t just store raw machine values. In particular, we have seen that laziness is implemented by storing a pointer to an unevaluated expression until the actual result is required, at which point we evaluate the expression and replace the pointer to the expression by the result. That requires some overhead on almost every single value you create.

On the contrary, an unboxed value is represented in memory by… just the value itself directly, no indirection is necessary, no pointer to a heap value (thus disabling any laziness).

For example, Int is the type of boxed ints. On the other hand, Int# is the type of unboxed ints, represented by a raw machine int, like you have them in C. The same goes for Double#, Float#, Addr# (that’s just void*), etc. They all end with #, and some of the standard Haskell types are built on top of these unboxed types. One important note: these types cannot be defined in Haskell; they are somehow hardcoded in the compiler. The interested reader can head to GHC.Prim’s documentation to learn more about them and how they are generated by GHC.

So we happen to have access to the raw, low-level operations through this GHC.Prim module. For example, the addition for Int# defined there will most likely compile down to just a single assembly addition instruction.

But what does this have to do with unpacking? Well, remember the matrices from earlier? What if I wanted to store my 4 Doubles right in the matrix, instead of having 4 pointers to dereference? That’s basically storing 4 values of type Double#. Well, that’s precisely what the {-# UNPACK #-} pragma lets us do in the following code. Note that an unpacked field necessarily has to be strict, so GHC will reject an {-# UNPACK #-} pragma sitting right before a non-strict field.

data Mat2 = M2 {-# UNPACK #-} !Double
               {-# UNPACK #-} !Double
               {-# UNPACK #-} !Double
               {-# UNPACK #-} !Double

This is equivalent to:

data Mat2 = M2 Double#
               Double#
               Double#
               Double#

Note: you can’t directly use Int#, Double#, etc in your code unless you switch on the MagicHash language extension (either by passing -XMagicHash to GHC, or by writing {-# LANGUAGE MagicHash #-} at the top of your haskell module.

Another note: if you pass GHC the -funbox-strict-fields option (or write {-# OPTIONS_GHC -funbox-strict-fields #-} at the top of your module), it will try to unbox all the fields you have marked as strict (with a !), silently failing for those it can’t unbox. If you mark a non-unpackable field with an {-# UNPACK #-} pragma, it will however warn you that it couldn’t unpack it.

One last thing about {-# UNPACK #-}. When can we apply it? That’s quite simple: the type you want to unpack inside the bigger one must have a single constructor (e.g, not data Maybe a = Nothing | Just a, which has two constructors Nothing and Just), must not be a type variable (e.g data Foo a = Foo {-# UNPACK #-} !a won’t work, GHC must know what a is) and must be marked strict (data Foo = Foo {-# UNPACK #-} Int won’t work but data Foo = Foo {-# UNPACK #-} !Int will).

data StrictIntPair = SIP {-# UNPACK #-} !Int 
                         {-# UNPACK #-} !Int

data TwoSIPs = TwoSIPs {-# UNPACK #-} !StrictIntPair 
                       {-# UNPACK #-} !StrictIntPair

f :: TwoSIPs -> TwoSIPs
f (TwoSIPs (SIP a b) (SIP c d)) = TwoSIPs (SIP x x) (SIP x x)
  where x = a+b+c+d

data TwoSIPs = TwoSIPs Int# Int# Int# Int#

f :: TwoSIPs -> TwoSIPs
f =
  \ (ds :: TwoSIPs) ->
    case ds of _ { TwoSIPs rb rb1 rb2 rb3 ->
    let {
      a :: Int#
      a = +# (+# (+# rb rb1) rb2) rb3 } in
    TwoSIPs a a a a
    }

Other ways to force the evaluation

There are some other ways to control the evaluation of your data. For example, if you ever need to evaluate a value before passing it to some function, maybe you’re just after ($!), which is function application (just like ($)), but evaluating the argument to WHNF before passing it to the function.

I have deliberately not mentionned seq in this article, because it seems to be a consensus that throwing seqs around in our code isn’t good practice: using strict (optionally unboxed) fields and bang patterns appears to cover pretty much all cases. However, most of these techniques rely on seq, which is just a primop (like the operations on unboxed types, it’s not definable in Haskell, thus baked into the GHC runtime system) and its action is to evaluate its first argument to WHNF and return the second argument. This sounds innocent but it can lead to broken guarantees about our code, when used badly, as you can read here.