Laziness in PureScript
PureScript does have laziness support but you must choose to use it explicitly. In this post, I’ll describe the fundamentals of laziness in PureScript.
Laziness in PureScript is build on top of the
package. It provides two fundamental tools in the
Data.Lazy module –
force. Let’s talk about
defer first. Here is its signature:
defer :: forall a. (Unit -> a) -> Lazy a
defer function is a smart constructor for the
Lazy type. In a nutshell,
if you want to create a lazy value, you give
defer a function that wraps the
value you want to create. You ignore the argument to the function (a
type) and return the value you want to be lazy. Let’s try an example.
import Data.Lazy (Lazy, defer) inc :: Int -> Lazy Int inc n = defer \_ -> n + 1
From the repl, we can call
inc to create a lazy incremented integer.
> :t inc 1 Lazy Int > inc 1 (defer \_ -> 2) > inc 2 (defer \_ -> 3)
It’s important to note that when the repl prints out the
Lazy Int, it is
actually forcing the computation in order to print the wrapped value. In your
real code, the underlying value won’t be forced until it is required by another
computation or forced manually. You can see from the first line that the return
inc is indeed a
Lazy Int (the
:t statement lets us see the type
of an expression in the repl).
This brings us to the second fundamental function,
force. Here is the
force :: forall a. Lazy a -> a
We can use
force to force the evaluation of a lazy value. Assuming the
definition above, we can do the following in the repl:
> import Prelude > import Data.Lazy (force) > :t force $ inc 2 Int > force $ inc 2 3
force function retrieves the lazy value by applying the wrapper function
to the value
unit and returning the result.
Lazy type offers more than just these building blocks. It is an instance
of many useful type classes, allowing you to easily operate on and compose lazy
values. First off,
Lazy is a
Functor. This means we can apply regular
functions with lazy values.
Suppose we have our existing
inc function that returns a
Lazy Int and
another function that operates on
Int. We can use
map, just like any other
Functor, to operate on the value “inside” of the
> import Data.Lazy (defer) > :t map forall a b f. Functor f => (a -> b) -> f a -> f b > :t inc Int -> Lazy Int > :t (_ * 10) Int -> Int > map (_ * 10) $ inc 1 (defer \_ -> 20)
<$> operator is just an infix alias for
map, so we could rewrite this
> (_ * 10) <$> inc 1 (defer \_ -> 20)
Lazy is also a
Monad. This means we can chain together functions that accept
regular types and return
Lazy types. To do this, we use
bind or its operator
>>= (or the flipped variant
> :t (>>=) forall a b m. Bind m => m a -> (a -> m b) -> m b > inc 2 >>= inc (defer \_ -> 4)
We can also use the do notation, as we can with any other
incAndAdd :: Int -> Int -> Lazy Int incAndAdd x y = do x' <- inc x y' <- inc y pure $ x' + y'
Let’s call it in the repl.
> incAndAdd 3 4 (defer \_ -> 9)
It’s very important to remember that all of these operations and their results
are lazy. No computation will actually happen until something eventually calls
force on a
Lazy has instances for several other interesting type classes, but the last
I’ll mention is
Semigroup. If the value you’re lazily wrapping is a
Semigroup, then the lazy value is also a
Semigroup (meaning it supports an
append operation). Let’s try it.
> import Data.Lazy (defer) > :t (<>) forall a. Semigroup a => a -> a -> a > (defer \_ -> [1,2]) <> (defer \_ -> [3,4]) (defer \_ -> [1,2,3,4])
PureScript provides a higher-level abstraction on top of these building blocks
Data.List.Lazy module in the
purescript-lists package. First, let’s
look at type relevant type constructors.
> import Data.List.Lazy (List(..), Step(..)) > :t List > forall t1. Lazy (Step t1) -> List t1 > :t Nil > forall t1. Step t1 > :t Cons > forall t1. t1 -> List t1 -> Step t1
Data.List.Lazy) is constructed with a
Step is constructed with either a
Nil or a
Cons with an element and
another lazy list. We can use these constructors to build a lazy, infinite list
of the fibonacci sequence.
import Data.Lazy (defer) import Data.List.Lazy (List(..), Step(..)) fibs :: List Int fibs = fibs' 0 1 where fibs' :: Int -> Int -> List Int fibs' a b = List $ defer \_ -> Cons a $ fibs' b (a + b)
> import Data.List.Lazy (step) > :t step forall a. List a -> Step a
step function takes a lazy list and “forces” the head element, giving us
Step. Let’s use this to find the nth number from the fibonacci
nthFib :: Int -> Maybe Int nthFib n = nthFib' n $ step fibs where nthFib' :: Int -> Step Int -> Maybe Int nthFib' 0 (Cons h _) = Just h nthFib' i (Cons _ t) | i > 0 = nthFib' (i - 1) $ step t nthFib' _ _ = Nothing