[Haskell-cafe] questions on lazy pattern, StateT monad

[Wolfgang Jeltsch]

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