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