Example of a data structure with lazy spine and strict leaves

Question

One of the performance trick mentioned here is this:

As a safe default: lazy in the spine, strict in the leaves.

I'm having trouble imagining such a data structure.

If I take Lists as an example, and if I make it strict in the leaves then won't the spine will be automatically strict ?

Is there any data structure example where the spine is lazy and leaves are strict ?

Answer 1

"Lazy in the spine, strict in the leaves" is a property of the API, not (just) a property of the data structure. Here's an example of how it might look for lists:

module StrictList (StrictList, runStrictList, nil, cons, uncons, repeat) where

newtype StrictList a = StrictList { runStrictList :: [a] }

nil :: StrictList a
nil = StrictList []

cons :: a -> StrictList a -> StrictList a
cons x (StrictList xs) = x `seq` StrictList (x:xs)

uncons :: StrictList a -> Maybe (a, StrictList a)
uncons (StrictList []) = Nothing
uncons (StrictList (x:xs)) = Just (x, StrictList xs)

repeat :: a -> StrictList a
repeat x = x `seq` StrictList (let xs = x:xs in xs)

Note that compared to built-in lists, this API is a quite impoverished -- that's just to keep the illustration small, not for a fundamental reason. The key point here is that you can still support things like repeat, where the spine is necessarily lazy (it's infinite!) but all the leaves are evaluated before anything else happens. Many of the other list operations that can produce infinite lists can be adapted to leaf-strict versions (though not all, as you observe).

You should also notice that it is not necessarily possible to take a leaf-lazy, spine-lazy structure and turn it into a leaf-strict, spine-lazy one in a natural way; e.g. one could not write a generic fromList :: [a] -> StrictList a such that:

• fromList (repeat x) = repeat x and
• runStrictList (fromList xs) = xs for all finite-length xs.

(Forgive my punning, I'm a repeat offender).