In GHC, from the operational point of view, the type `Int`

does not
indicate a bit pattern somewhere in memory that represents an integer.
What it indicates is *either* an integer bit pattern *or* a “thunk” (a
delayed computation) which can be “forced” (run). When and if the
computation terminates the thunk will be overwritten with the integer
bit pattern that it produced.

Thus the GHC type system provides less fine-grained information than we might naively expect, especially if we are used to the strict point of view. Often the ability to invisibly interchange thunks and values is a blessing. In fact it is one of Haskell’s great blessings. However, it is well known that it can also be a curse. Here’s an example:

```
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ z [] = z
foldl f z (b:bs) = foldl f (f z b) bs
```

The application of `f`

to `z`

and `b`

does not result in an evaluated
`a`

. Instead it results in a thunk representing the function call.
If the input list is of length `n`

we make `n`

recursive calls and
build up a thunk whose size is proportional to `n`

. This leaks space.

The way to avoid a space leak is to explicitly force the `a`

we have
created with a call to `seq`

before each recursive call.

```
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' _ z [] = z
foldl' f z (b:bs) = a `seq` foldl f a bs
where a = f z b
```

This way the `a`

remains completely evaluated at each stage.

This is a reasonable solution, but as Haskellers we are used to our
types specifying very fine-grained information about the operation of
our program. We want our types to specify when `IO`

actions can
occur, so why not ask for our types to specify when evaluation of
thunks takes place?

Unfortunately this isn’t straightforward to come by. For example, we might try

```
data Strict a = Strict !a
foldl :: (a -> b -> a) -> Strict a -> [b] -> a
foldl _ (Strict z) [] = z
foldl f (Strict z) (b:bs) = foldl f (Strict (f z b)) bs
```

But this is no good. After all, a `Strict a`

doesn’t represent a
strict `a`

but rather a *thunk* returning a strict `a`

! So we build
up a chain of thunks nonetheless. In fact there is no difference in
terms of laziness between `a`

and our attempted `Strict a`

. Both of
them are just thunks that can be forced to return an `a`

.

However, there is a trick that allows us to represent strictness in
types. The trick is to indicate strictness in the *argument* to a
function rather than its return type. I learned this from a post of
Stefan Holdermans to the Haskell-Cafe mailing
list.

```
{-# LANGUAGE TypeOperators #-}
data a :-> b = Strict (a -> b)
-- Strict constructor will be hidden
-- Specifying the precedence of :-> merely for neater syntax
infixr 0 :->
strictly :: (a -> b) -> a :-> b
strictly f = Strict (\a -> a `seq` f a)
(!) :: (a :-> b) -> a -> b
Strict f ! a = f a
```

Then we can write a recursive `foldl`

which is guaranteed to be space
leak free because it has the right type.

```
foldl' :: (a -> b -> a) -> a :-> [b] -> a
foldl' f = strictly (\z xs -> case xs of
[] -> z
y:ys -> foldl' f !(f z y) $ ys)
```

The value whose type is on the left hand side of a `:->`

is guaranteed
to be evaluated strictly, i.e. forced before the result can start to
be consumed.

What do we do if we want to define functions which are polymorphic
over strictness type? For example the standard definition of `const`

doesn’t touch its `b`

argument when its return value is evaluated.

```
const :: a -> b -> a
const a b = a
```

On the other hand we can define another version which does

```
const' :: a -> b -> a
const' a b = b `seq` a
```

How do we implement both of these with one definition? Well, we can introduce
a class to capture the general concept with instances for `(->)`

and
`(:->)`

. (The need for the notation `arrow`

instead of something
symbolic is a syntactic annoyance. I’m not sure how to get round it.)

```
class FunctionLike arrow where
(?) :: (a `arrow` b) -> a -> b
functionLike :: (a -> b) -> (a `arrow` b)
instance FunctionLike (->) where
(?) = id
functionLike = id
instance FunctionLike (:->) where
(?) = (!)
functionLike = strictly
```

Then we can define polymorphic `const`

as

```
constPolymorphic :: FunctionLike arrow => a -> b `arrow` a
constPolymorphic a = functionLike (\_ -> a)
```

and use it to directly derive the two specialisations that we want.

```
const :: a -> b -> a
const = constPolymorphic
const' :: a -> b :-> a
const' = constPolymorphic
```

If we were so inclined we could use `FunctionLike`

to define the leaky
and leak free versions of `foldl`

at the same time!

```
foldlPolymorphic :: FunctionLike arrow =>
(a -> b -> a) -> a `arrow` ([b] -> a)
foldlPolymorphic f = functionLike (\z xs -> case xs of
[] -> z
y:ys -> foldl' f ?(f z y))
```

The operator `?`

should be interpreted as function application which
is polymorphic over strictness.

Even more amazingly, gelisam on Haskell Reddit showed me how to make
data types that are strictness
polymorphic!
The key observation is that the only difference between the usual,
lazy `data Foo a = Foo a`

and the strict `data Foo a = Foo !a`

is that
the function which constructs `Foo`

s is lazy in its argument for the
former, and strict in its argument for the latter.

If we want to be polymorphic over strict and lazy lists, for example, we can define

```
data List (arrow :: * -> * -> *) a = Nil | Cons a (List arrow a)
-- The List constructor will have to be hidden, although pattern
-- matching on it would be OK. arrow is a phantom type which we
-- use as a strictness indicator.
-- We expose this polymorphic cons instead
cons :: FunctionLike arrow =>
a `arrow` (List arrow a `arrow` List arrow a)
cons = functionLike (\x -> functionLike (\y -> Cons x y))
```

(Again I apologise for the syntax. Hopefully someone knowledgeable can tell me what to do about that.)

A `List (->) a`

is a lazy list of `a`

, and a `List (:->) a`

is a
strict list of `a`

. We can define data values in a way that is
polymorphic over strictness type, for example enumerating all integers
in a range.

```
range :: FunctionLike arrow => Int -> Int -> List arrow Int
range a b = if a > b
then Nil
else cons ?a ?(range (a+1) b)
```

(Recall that the operator `?`

should be interpreted as function
application which is polymorphic over strictness.)

Then `count 1 1000000 :: List (->) Int`

is a lazy list where the one
million elements are computed as required. `count 1 1000000 :: List (:->) Int`

is a strict list where all one million elements are
computed at once.

Wadler talks about a “strictness monad” in section 3.2 on page 9 of Comprehending Monads but I don’t think it solves the problem I want it to solve.

For example, consider

```
foldl :: (a -> b -> a) -> Str a -> [b] -> Str a
foldl _ z [] = z
foldl f z (b:bs) = foldl f (f <$> z <*> pure b) bs
```

This still builds up a chain of thunks in the same way that our
original `Strict`

attempt did. All the `Str`

monad seems to achieve
is enforcing an ordering of evaluations with respect to each other.
Perhaps there’s a way of getting the desired behaviour with a cleverer
usage of `Str`

, but I don’t see it.

Strictness in Haskell is generally hidden away and not reflected by types, but there does seem to be a way of representing strictness in the type system!