[Haskell-cafe] [] vs [()]

[Ryan Ingram]

(This is a literate haskell post, save into SMM.lhs and load in ghci!)

Here's one place you might use [()] and []:

> guard :: Bool -> [()]
> guard True = [()]
> guard False = []

You can then use "guard" in monadic list computations to abort the
computation on some branches:

> sendmoney :: [[Int]]
> sendmoney = do
>    choice@[s,e,n,d,m,o,r,y] <- generate 8 [0..9]
>    guard (s /= 0)
>    guard (m /= 0)
>    guard (val [s,e,n,d] + val [m,o,r,e] == val [m,o,n,e,y])
>    return choice

(evaluating this in ghci takes a little while, but it does succeed!
You can easily optimize by noticing that m must be equal to 1 and
therefore s must be 8 or 9.)

Using guard in this way works because of the definition of bind on lists:

    xs >>= f  =  concatMap f xs = concat (map f xs)

Consider a simpler example:

> simple = do
>    x <- [1,2,3]
>    guard (x /= 2)
>    return x

This is the same as
     [1,2,3] >>= \x ->
     guard (x /= 2) >>= \_ ->
     return x

= mapConcat (\x -> mapConcat (\_ -> return x) (guard (x /= 2))) [1,2,3]
= concat
     [ mapConcat (\_ -> return 1) (guard (1 /= 2))
     , mapConcat (\_ -> return 2) (guard (2 /= 2))
     , mapConcat (\_ -> return 3) (guard (3 /= 2))
     ]
= concat
     [ mapConcat (\_ -> return 1) [()]
     , mapConcat (\_ -> return 2) []
     , mapConcat (\_ -> return 3) [()]
     ]
= concat
     [ concat [ [1] ]
     , concat []
     , concat [ [3] ]
     ]
= concat [ [1], [], [3] ]
= [1,3]

Another fun example:

> double :: [()]
> double = [(), ()]

> sixteen:: Int
> sixteen = length $ do
>    double
>    double
>    double
>    double

Helper code for "send more money" follows...

> generate :: Int -> [a] -> [[a]]
> generate 0 _ = return []
> generate n as = do
>    (x,xs) <- select as
>    rest <- generate (n-1) xs
>    return (x:rest)

> select :: [a] -> [(a,[a])]
> select [] = []
> select [x] = return (x,[])
> select (x:xs) = (x,xs) : [ (y, x:ys) | (y,ys) <- select xs ]

> val xs = val' 0 xs where
>    val' v [] = v
>    val' v (x:xs) = val' (10*v + x) xs