[Haskell-beginners] Simplifying code

[Daniel Fischer]

Am Dienstag 09 Februar 2010 23:07:55 schrieb Patrick LeBoutillier:
> Daniel,
>
> > Sure. If you don't mind that the mutations come in a different order,
> > one thing that works wonders is "sequence",
> >
> > sequence :: Monad m => [m a] -> m [a]
> >
> > In particular, for m = [], sequence :: [[a]] -> [[a]]. Then, knowing
> > what sequence does, we can write
> >
> > import Control.Monad (sequence)
> >
> > generateAll :: String -> [String]
> > generateAll word = sequence (map f word)
> >     where
> >     f c = case lookup c leat of
> >                Just r  -> [c,r]
> >                Nothing -> [c]
>
> That's very nice!

Thanks. But from a clean-code-higher-level perspective, it's even nicer 
with your

> -- Returns a list of possible characters for c
> mutateLetter :: Char -> [Char]
> mutateLetter c = c : (maybeToList $ lookup c leet)

(here is a point where it would be even nicer if lookup had the type

lookup :: (Eq a, MonadPlus m) => a -> [(a,b)] -> m b
). The performance-junkie in me would want to look at the core to make sure 
the maybeToList is eliminated by the compiler, though.

>
> One question though: In the docs sequence is described as:
>
>   "Evaluate each action in the sequence from left to right, and
> collect the results."
>
> How is one supposed to deduce what the behavior will be for the list
> monad (besides looking at the source)?

Given its polymorphic type

sequence :: Monad m => [m a] -> m [a]

, what can sequence do?

For
sequence []
, there's really only one possibility (not involving undefined/error), so
sequence [] = return []

Okay, that was the trivial part, now what can be done with nonempty lists?
It could ignore the input and return [] in any case, but that wouldn't be 
useful at all, so we can discard that possibility. What could be usefully 
done with

sequence (m1:ms) ?

It has to do something with m1 and something with ms, then combine the 
results to a list of [a], which it returns.
What can it do with m1? Since all that sequence knows about m1 is the type 
(Monad m => m a), it can't do anything but what's provided by that 
constraint. Basically, it can only put it on the left of a (>>=). There's 
on decision to be made, shall it be

sequence (m1:ms) = m1 >>= \x -> something with x and ms

or

something with ms >>= \xs -> (m1 >>= \x -> something with x and xs)
?
And what can it do with the tail of the list, ms? Why, sequence it of 
course.
So it's either

sequence (m1:ms) = m1 >>= \x -> (sequence ms >>= \xs -> return (fun x xs))
{-
sequence (m1:ms) = do
    x <- m1
    xs <- sequence ms
    return (fun x xs)
-}
or

sequence (m1:ms) = sequence ms >>= \xs -> (m1 >>= \x -> return (fun x xs))
{-
sequence (m1:ms) = do
    xs <- sequence ms
    x <- m1
    return (fun x xs)
-}

where

fun :: forall a. a -> [a] -> [a]

Now there's a lot of nonsense you could use for 'fun',

fun x xs = reverse (x:xs)
fun x xs = x:xs ++ [x,x,x]
fun x xs = front ++ x:back where (front,back) = splitAt 17 xs
...
, but the most prominent function of type forall a. a -> [a] -> [a] is the 
only one to be reasonably expected here, so

fun x xs = x : xs

and the only question that remains is in which order things are chained.
That is answered by the docs, left to right, so

sequence [] = return []
sequence (m1:ms) = m1 >>= \x -> sequence ms >>= \xs -> return (x:xs)
{-
sequence (m1:ms) = do
    x <- m1
    xs <- sequence ms
    return (x:xs)

sequence (m1:ms) = m1 >>= \x -> liftM (x :) (sequence ms)
-}
(or equivalent).
Now you need to know how (>>=) is defined for [], namely

ys >>= f = concatMap f ys.

The short answer is, you can't deduce it wihout knowing the Monad instance 
for [], and if you know that well enough to not be confused by "evaluate 
the action" (which takes time), it's fairly straightforward.

>
>
> Patrick