Menu
Consider the following two nearly identical functions:
buildList 0 = []
buildList n = n : buildList (n - 1)
buildListM 0 = return []
buildListM n = buildListM (n - 1) >>= return . (n :)
The laziness aspect of Haskell allows for buildList to generate the list without much overhead in memory because it generates the head of the list and then builds the tail.
But the monadic version buildListM seems to use more memory as n gets larger because it must build the tail first and then prepend the head.
Is this a good way to build lists inside monads, or is there a more efficient way?
923
Lists are a fundamental part of Haskell, and we've used them extensively before getting to this chapter. The novel insight is that the list type is a monad too! As monads, lists are used to model nondeterministic computations which may return an arbitrary number of results.
List as a data structure is not a Monad, but the fact that Scala's List implements flatMap is what gives it its monadic super-powers. It also needs to fulfil associativity, left unit and right unit laws to qualify as a Monad.
Bind takes a non-composable function f and returns a new function g that accepts the monadic type as input and returns the monadic type. g is composable. The unit function takes an argument of the type that f expected, and wraps it in the monadic type.
In Haskell a monad is represented as a type constructor (call it m ), a function that builds values of that type ( a -> m a ), and a function that combines values of that type with computations that produce values of that type to produce a new computation for values of that type ( m a -> (a -> m b) -> m b ).
Many Monads (e.g., IO, strict ST s, strict State s) are "strict", in that >>= is strict in its left operand. Others, most notably Identity but also (->) a, lazy State s, lazy Writer q, lazy ST s, are "lazy" in the sense that >>= is not strict in its left operand. Consider applying toListM in the Identity monad:
buildListM 0 = return []
buildListM n = buildListM (n - 1) >>= return . (n :)
Here, return = Identity and Identity m >>= f = f m, so
buildListM 0 = Identity []
buildListM n = Identity . (n :) $ runIdentity (buildListM (n - 1))
= Identity (n : runIdentity (buildListM (n - 1)))
Since Identity and runIdentity are complete no-ops at runtime, buildListM is actually the same as buildList when run in the Identity monad. It's the particular monad, not the monadic nature, that makes things strict.
You can sometimes do lazy things in "strict" monads in one of two ways:
Cheat using unsafeInterleaveIO or unsafeInterleaveST.
Use the more powerful MonadFix abstraction which lets you get hold of the result of a computation before it's been executed, but that will fail on you if you access such a result before it's available.
112
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
