List of tuples in Haskell with case of sequences

Question

I'm learning about Monads in Haskell and I'm trying to go all the way up from a function (coupleUp3) to the minimun case m of ... (coupleUp1) something like what I saw in the computerphile's video https://www.youtube.com/watch?v=t1e8gqXLbsU&t=1173s.

However, I got stuck and the result is always for

[1..3]

something like:

[(1,1), (2,2), (3,3)]

and that's not what I want, I'd like something like

[(1,1),(1,2),(1,3),(2,1),...,(3,3)]

which is what the other functions do. Here's the code and I just searching for ideas of how to implement the function coupleUp1 that way. You can see what I'm tryin' to do looking at coupleUp3 and coupleUp2. Thank's!

coupleUp3 :: [a] -> [(a, a)]
coupleUp3 x = do
  y <- x
  z <- x
  return (y, z)

coupleUp2 :: [a] -> [(a, a)]
coupleUp2 x = (x >>= (\y ->
               x >>= (\z ->
               return (y, z))))

 coupleUp1 :: [a] -> [(a, a)]
 coupleUp1 x = case x of
                []     -> []
                (y:ys) -> case ys of
                            []     -> []
                            (z:zs) -> (y, z):coupleUp1 ys

Answer 1

List comprehensions and do notation:

f xs = [(y, z) | y <- xs, z <- xs]

f xs = do
  y <- xs
  z <- xs
  pure (y, z)

Desugar to the bind operator >>=:

f xs = xs >>= \ y -> xs >>= \ z -> pure (y, z)

And the definitions of >>= and pure can be inlined for a given monad:

f xs = concatMap (\ y -> concatMap (\ z -> [(y, z)]) xs) xs

And then broken down a bit:

f xs = concat $ map (\ y -> map (\ z -> (y, z)) xs) xs

If you want to go further than this, you can inline some simple definitions of concat and map:

f xs = concat' $ map' (\ y -> map' (\ z -> (y, z)) xs) xs
  where
    concat' (xs:xss) = xs ++ concat' xss
    concat' [] = []

    map' f (y:ys) = f y : map' f ys
    map' f [] = []

And then rewrite it step by step, simplifying and inlining until you end up with something like this:

-- Expanding…

f xs = concat' $ map1 xs
  where
    concat' [] = []
    concat' (xs:xss) = xs ++ concat' xss

    -- Previously ”map' (\ y -> …)”.
    map1 (y:ys) = map2 y xs : map1 ys
    map1 [] = []

    -- Previously “map' (\ z -> …)”.
    -- (Takes “y” as an explicit argument; previously,
    -- it was implicitly captured by the lambda.)
    map2 y (z:zs) = (y, z) : map2 y zs
    map2 y [] = []

-- Fully expanded.
-- (With renamed functions for clarity.)

f xs = pairWithSelf xs
  where
    pairWithSelf (y:ys) = pairEachWith y xs ++ pairWithSelf ys
    pairWithSelf [] = []

    pairEachWith y (z:zs) = (y, z) : pairEachWith y zs
    pairEachWith y [] = []

Now this definition says very literally what it does: “to pair a list with itself (f), for every element of the list (pairWithSelf), pair that element with every element of the list (pairEachWith)”.

The (++) in pairWithSelf comes from inlining concat, and the recursion in pairWithSelf and pairEachWith comes from inlining the two levels of map. You can’t easily “collapse” this down into a single non-nested recursive function because the solution inherently involves nested iteration over the list.

Also, this is a fairly tedious process because you’re essentially doing by hand, symbolically, what the language would be doing for you automatically during optimisation or at runtime.

Because you have a recursive structure, you can’t really make this any more “primitive”. (Well, you could use fix to make the local functions pairWithSelf and pairEachWith into anonymous lambdas, and that might be a good exercise to learn about fix.)

In addition, this process is working backward from how you’d typically do it in Haskell: we usually want to find the most generic and high-level implementation with the least use of explicit recursion possible.

Going back to a higher level, when you see this common pattern of binding two independent actions (lists, in this case) and combining the results with a pure function:

do
  x <- xs
  y <- ys
  pure (combine x y)

Then you can replace it with Applicative functions. Here, combine is the pair constructor (,) and xs and ys are the same, so you could write either of these:

f xs = liftA2 (,) xs xs
f xs = (,) <$> xs <*> xs

This usage of Applicative is very common in ordinary Haskell code, whenever you need a computation shaped like a “Cartesian product” (e.g. a pair table or multiplication table) or you want to pass the results of monadic actions to a pure function without explicitly binding a name with a bind statement <- in do notation.