[Haskell-cafe] questions on lazy pattern, StateT monad
Wolfgang Jeltsch
wolfgang at jeltsch.net
Wed Nov 23 14:42:03 EST 2005
Am Mittwoch, 23. November 2005 19:02 schrieb Fan Wu:
> HI Wolfgang,
>
> The code is from GHC source
> ghc-6.4.1/libraries/monads/Monad/StateT.hs, am I looking at the wrong
> place?
>
> I found the thread discussing "Monad strictness", where is your StateT
> defined?
Hello Fan,
the GHC source is just where I looked, except that my GHC version is 6.2.2.
Obviously they corrected the implementation of (>>=) for StateT to use a lazy
pattern between 6.2.2 and 6.4.1.
> But it is still not clear to me why lazy pattern is used here. Any ideas?
Let's discuss this for State instead of StateT because this makes the
discussion easier.
A state transformer should ideally be implemented as a kind of function which
gets one argument (the initial state) and returns *two* results (the output
and the final state). Of course, a real function cannot return two results,
so the obvious solution is to use a function which returns a pair, consisting
of the output and the final state. If we would do so, it would work.
But Haskell's pairs are not real pairs but lifted pairs. There are pairs like
(x,y) which are an application of the data constructor (,) to x and y, and
there is the special pair _|_ which denotes undefinedness. Note that _|_ is
not the same as (_|_,_|_). Pattern matching of _|_ against the pattern (_,_)
will not be successful while matching (_|_,_|_) against the same pattern
will.
The problem now is that when using Haskell pairs for implementing state
transformers, it might not immediately be clear for a given state transformer
if it returns an application of (,) (i.e., a "true pair") or if it returns
_|_. Pattern matching of a state transformer's result against a pattern of
the form (x,y) may therefore result in unnecessary evaluation of certain
expressions.
Let's look at an example. We have two types S and T as well as some state
transformer next :: State S T. Now we want to construct a state transformer
which calls next infinitely many times and returns the outputs of the next
invocations as an infinite list. We would write:
everything :: State S [T]
everything
= do
x <- next
xs <- everything
return (x : xs)
The do expression can be rewritten as:
next >>= (\x -> everything >>= \xs -> return (x : xs))
If we use an implementation of State *without lazy patterns*, it becomes
something like this:
\s -> case next s of
(x,s') -> case everyting s' of
(xs,s'') -> ((x : xs),s'')
Note that I used case expressions to realize strict patterns because pattern
binding in let expressions is implicitely lazy.
Now lets apply the function denoted by the last code fragment to some initial
state and try to extract just the first element of the output. In order to
do so we have to take the result of the function and match it against
((x : _),_). Especially, we have to reduce the pair, i.e., we have to make
sure that it's really an application of (,) and not _|_.
In order to do so we have to first reduce next s. After this, s' has to be
taken and the result of everything s' has to be reduced. We cannot tell that
the result of the whole function is really a (,) application until we have
reduced everything s' and made sure that its result is not bottom. The
problem is that for reducing everything s', we have to start the whole
procedure again. So we end up in an infinite recursion and never get any
result.
However, if we use lazy patterns, we don't have to reduce next s at first. We
also don't have to reduce everything s'. No matter whether these two
expressions are _|_ or not, we know that the whole function always has a
result of the form ((x : xs),s''). The first component of the pair can be
immediately extracted from the pair and so can the first element of the list.
Only if we start to evaluate this first element, next s has to be reduced.
But only next s!
I hope, this did clarify this problem a bit. If you still have questions,
feel free to ask.
> Thanks,
> Fan
Best wishes,
Wolfgang
More information about the Haskell-Cafe
mailing list