In Haskell mythology, laziness is one of the Sirens: you can’t but be lured in by its raciness in the heat of learning Haskell; you are then inevitably wrecked by it as your imperative sensibilites take hold; and a year or so later you sit down to describe your adventure in a Homerian epic. Laziness doesn’t deserve this level of aggrandizing but it’s good fun talking about it to a functional programming initiate.

In this post, I’m going to look at one of the canonical lazy structures in Haskell: the humble List `[a]`

. I’m going to consider a simple pattern one might encounter with lists and then improve it – not by adding strictness but by employing an even more lazy structure: the difference list `DList a`

.

```
> module Main
> (
> main
> ) where
>
> import Data.Monoid
> import Control.Monad (foldM)
> import Data.Foldable
> import Data.DList hiding (map,replicate)
> import Criterion.Main
```

The function of interest is the finite cartesian product of lists

For our purposes, rather than return a list of tuples, we’ll fold the tuple using a binary operator as follows, which we evaluate to weak-head normal form.

```
> list_cartesian :: (a -> a -> a) -> a -> [[a]] -> [a]
> list_cartesian f s = loop
> where loop (xs:xss) = xs >>= \x ->
> loop xss >>= \y ->
> return $! f x y
> loop [] = return s
```

And it works as expected

```
ghci> list_cartesian (*) (1::Int) [[3,4],[2],[1,2]]
[6,12,8,16]
```

As with anything in Haskell, the temptation to generalize is immense. So, here is a more general version – the list is replaced by a Monad.

```
> cartesian :: Monad m => (a -> a -> a) -> a -> [m a] -> m a
> cartesian f s = loop
> where loop (xs:xss) = xs >>= \x ->
> loop xss >>= \y ->
> return $! f x y
> loop [] = return s
```

As an example, consider evaluation under the `Maybe`

monad

```
ghci> cartesian (*) (1::Int) [Just 20,Nothing,Just 10]
Nothing
ghci> cartesian (*) (1::Int) [Just 20,Just 3,Just 10]
Just 600
```

We can also evaluate the list example using a difference list

```
ghci> cartesian (*) (1::Int) (map fromList [[3,4],[2],[1,2]])
fromList [6,12,8,16]
```

Consider the following specialized functions to compute the sum of the cartesian products using a regular list and a difference list.

```
> cart_list :: [[Double]] -> Double
> cart_list = foldl' (+) 0 . cartesian (*) 1
>
> cart_dlist :: [DList Double] -> Double
> cart_dlist = foldl' (+) 0 . cartesian (*) 1
```

## Benchmark

Should we expect any difference in performance? Well, first off, here are the relevant function definitions

```
(>>=) :: [a] -> (a -> [b]) -> [b]
m >>= k = foldr ((++) . k) [] m
```

On the other hand, a difference list and its concatenation function `append`

is defined as

```
newtype DList a = DL { unDL :: [a] -> [a] }
fromList :: [a] -> DList a
fromList = DL . (++)
toList :: DList a -> [a]
toList = ($[]) . unDL
append :: DList a -> DList a -> DList a
append xs ys = DL (unDL xs . unDL ys)
m >>= k = foldr (append . k) empty m
```

Structurally, the bind functions seem the same in both cases. But, now for some quick benchmarking code.`

```
> main = defaultMain
> [
> bcompare
> [
> bench "list" $ whnf cart_list one
> , bench "dlist" $ whnf cart_dlist (map fromList one)
> ]
> , bcompare
> [
> bench "list" $ whnf cart_list two
> , bench "dlist" $ whnf cart_dlist (map fromList two)
> ]
> ]
> where one = [[1..1000],[1..10],[1..100]]
> two = replicate 6 [1..10]
```

The results show that dlist performs better and the performance gap increases as the we cartesian product a greater number of lists or with a greater number of elements in each list. Furthermore, the memory consumption in dlist and list seems to be the same for this application.

**TODO:** I’m not exactly sure why yet.

```
warming up
estimating clock resolution...
mean is 4.362846 us (160001 iterations)
found 1891 outliers among 159999 samples (1.2%)
1362 (0.9%) high severe
estimating cost of a clock call...
mean is 1.253718 us (35 iterations)
found 2 outliers among 35 samples (5.7%)
2 (5.7%) high mild
benchmarking list
collecting 100 samples, 1 iterations each, in estimated 5.593204 s
mean: 55.25133 ms, lb 55.21188 ms, ub 55.30506 ms, ci 0.950
std dev: 233.8865 us, lb 184.6386 us, ub 297.9634 us, ci 0.950
benchmarking dlist
mean: 39.95902 ms, lb 39.93537 ms, ub 39.98984 ms, ci 0.950
std dev: 137.4931 us, lb 110.2501 us, ub 189.0927 us, ci 0.950
benchmarking list
collecting 100 samples, 1 iterations each, in estimated 17.37580 s
mean: 180.6279 ms, lb 180.2802 ms, ub 181.0926 ms, ci 0.950
std dev: 2.041791 ms, lb 1.446918 ms, ub 2.850368 ms, ci 0.950
benchmarking dlist
collecting 100 samples, 1 iterations each, in estimated 13.90359 s
mean: 151.4917 ms, lb 151.0659 ms, ub 152.0473 ms, ci 0.950
std dev: 2.468668 ms, lb 2.020109 ms, ub 3.235238 ms, ci 0.950
found 3 outliers among 100 samples (3.0%)
2 (2.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 9.412%
variance is slightly inflated by outliers
```