John Launchbury posed a nice puzzle about
mutual recursive bindings in the do notation:
--------------------
test :: [Int]
test = do (x,z) <- [(y,1),(2*y,2), (3*y,3)]
Just y <- map isEven [z .. 2*z]
return (x+y)
isEven x = if even x then Just x else Nothing
---------------------
I would consider it as equivalent to:
---------------------
testTrans :: [Int]
testTrans = do (x,z) <- [(\y -> y,1),(\y -> 2*y,2), (\y -> 3*y,3)]
Just y <- map isEven [z .. 2*z]
return (x y+y)
isEven x = if even x then Just x else Nothing
---------------------
which hugs accepts and evaluates to [4,6,12,16,24].
The principle is to consider variables (x) bound to expressions containing
later-bound variables (y) as functions accepting values for y.
When x is used, the current y is supplied.
MORE GENERAL would be to consider the following equivalent version
of the original program:
---------------------
test' :: [Int]
test' = do (x,z) <- return (y,1) ++
return (2*y,2) ++
return (3*y,3)
Just y <- map isEven [z .. 2*z]
return (x+y)
---------------------
and adapt all occurrences of return
to returning functions accepting the later-bound variables.
Patterns fed by such returns are replaced by new function variables (f).
Variables bound in patterns fed by such returns
occur in two situation:
1: (z) before the later bindings:
Apply to undefined and extract from the pattern,
2: (x) after the later bindings:
Apply to the now bound variable and extract from the pattern.
---------------------
testTrans' :: [Int]
testTrans' = do f <- return (\y -> ( y,1)) ++
return (\y -> (2*y,2)) ++
return (\y -> (3*y,3))
let z = snd (f undefined)
Just y <- map isEven [z .. 2*z]
let x = fst (f y)
return (x + y)
---------------------
Hugs says:
Main> testTrans'
[4,6,12,16,24]
How about it?
Best regards,
Wolfram
