3 ways to reduce sharing in Haskell 2022.09.27

Haskell is prone to space leaks, but luckily there are several ways to work around them.

A simple example for a space leak is iterating over the fibonacci sequence twice, as described in the previous post.

Luckily, several solutions to this problem were suggested by r/haskell:

Using INLINE pragmas

oberblastmeister suggested inlining:

fibs = map fst (iterate (\(cur, next) -> (next, cur + next)) (1, 1))
{-# INLINE fibs #-}

This will make separate iterations be independent from each other, each using their own copy of the list which is iterated once and is immediately collected by the GC.



Using the -fno-full-laziness GHC flag

MorrowM_ suggested using the -fno-full-laziness after wrapping fibs with a lambda:

{-# OPTIONS -fno-full-laziness #-}

fibs _ = map fst (iterate (\(cur, next) -> (next, cur + next)) (1, 1))

Note that adding the dummy lambda alone will suffice if not compiling with optimizations, but that's not something that we would like to rely on, hence the additional -fno-full-laziness option comes into place.

Without it, GHC may notice that the expression in fibs doesn't use its parameter and so it may float it out and shares it.




Alonzo Church famously discovered that data can be encoded in functions, and we can use it to avoid creating data structures that could be shared.

As the Fibonacci sequence is infinite we'll use a function encoding for infinite lists:

fibs :: (Integer -> a -> a) -> a
fibs cons =
    go 1 1
        go cur next =
            cons cur (go next (cur + next))

We can convert it to a list using fibs (:) but to avoid sharing we'll have to change our code using it, and to solve the problem in the previous post we'll use a custom variant of find:

findInf :: (a -> Bool) -> ((a -> a -> a) -> a) -> a
findInf pred infList =
    infList f
        f x rest
            | pred x = x
            | otherwise = rest

Btw, yeled_kafot suggested a formulation based on lens, which might be of use to folks using this eco-systems.