Zipping in Haskell

Question

I'm working on a function that will take two six-sided dice and return every possibility of pairs in a list of tuples.

So, I'd like my program to return something like:

[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),
 (2,1),(2,2),(2,3),(2,4),(2,5),(2,6),
 (3,1),(3,2),(3,3),(3,4),(3,5),(3,6),
 (4,1),(4,2),(4,3),(4,4),(4,5),(4,6),
 (5,1),(5,2),(5,3),(5,4),(5,5),(5,6),
 (6,1),(6,2),(6,3),(6,4),(6,5),(6,6)]

I think my head might be in the right general area, but I'm having a little trouble executing it, since I am new to Haskell. Here's what I have:

rolls :: [(Integer, Integer)]
fstDice = [1, 2, 3, 4, 5, 6]
sndDice = [1, 2, 3, 4, 5, 6]
rolls
    | zip fstDice sndDice
    | drop 1 sndDice
    | otherwise = rolls

I know that last part is very wrong, trust me. I was using zip to put the two dice together, then my thought was to drop the head off of the second dice, and repeat that process until sndDice is empty and until all the pairs are found.

I'm not sure if this idea is wrong, or if it's just my incorrect amateur execution.

(And for the record, I know this doesn't compile! I'm not sure what to do about the error either.)

It is not quite clear to me what your idea is so I cannot tell where exactly it goes wrong. There is about a zillion way to do this, the simplest one probably being list comprehension `rolls = [(fst,snd) | fst <- fstDice, snd <- sndDice]`. — n. m. could be an AI, Sep 25 '19 at 07:00
@n.m. Ooooh, I see. That makes a lot more sense! I tend to have the problem of overthinking very simple problems like this one, unfortunately. Your solution is a lot simpler and makes a ton more sense. Thanks for the tip! — larn, Sep 25 '19 at 07:03
If you’re interested, another way to do it is `(,) <$> list1 <*> list2`. This uses _applicative functors_, if you haven’t encountered them before. — bradrn, Sep 25 '19 at 07:06
fyi, with MonadComprehensions, the two code snippets proposed in the comments above are equivalent. — Will Ness, Sep 25 '19 at 07:12
@larn simplicity is only easy in retrospect, and is usually only found after a lot of overthinking — luqui, Sep 25 '19 at 07:29

Will Ness · Accepted Answer · 2021-01-01T16:07:31.620

When you're first starting learning recursive programming / Haskell, there's value in coding a solution by hand. You can learn the juggling of primitives later, when you've internalized the various patterns captured by them.

rolls []     _  = []
rolls (x:xs) ys = foo ys            -- for x in (x:xs),
    where
    foo (y:ys) = (x,y) : foo ys     -- for each y in ys
    foo []     = rolls xs ys        -- for the rest of x in xs, with the same ys

This combines the two lists as a matrix, tracing it row-by-row:

                  e      f      g    ....      -- ys
 x1:    a      (a,e)  (a,f)  (a,g)   ....
 x2:    b      (b,e)  (b,f)  (b,g)   ....
 x3:    c      (c,e)  (c,f)  (c,g)   ....
 x4:    d      (d,e)  (d,f)  (d,g)   ....
        .      ........................
        .      ........................

So yes, your idea was more or less in the right direction, except that it's not zip that's the right tool there, but map. Other ways of writing this are:

rolls xs ys = concat (map (\ x -> map (x ,)         ys)        xs)
            = concat [                [(x,y) | y <- ys] | x <- xs ]
            = [ r     | x <- xs, r <- [(x,y) | y <- ys] ]
            = [ (x,y) | x <- xs,               y <- ys  ]
            = [  x y  | x <- map (,) xs,       y <- ys  ]
            =   (<*>)      (fmap (,) xs)            ys      -- apA
            = liftA2             (,) xs             ys

so it's just a Cartesian product, or kind of an outer product, of the two lists.

This kind of "square" / 2D match-up is contrasted with

zip xs ys = zipWith             (,)          xs           ys 
          = getZipList $ liftA2 (,) (ZipList xs) (ZipList ys)
          = [                  (x,y) |  x <- xs  |   y <- ys ]
                           -- with Parallel List Comprehensions

which combines its two argument lists by a "linear" match-up, reminiscent of an inner product.

But also

rolls xs ys = concat        [         [(x,y) | y <- ys] | x <- xs ]
            = fold          [         [(x,y) | y <- ys] | x <- xs ]
            = foldr (++) [] [         [(x,y) | y <- ys] | x <- xs ]
            = foldr ($)     [   ( [(x,y) | y <- ys] ++) | x <- xs ]  []

since

foldr f z xs = foldr (($) . f) z xs 
             = foldr ($) z (map f xs) 
             = f x1 (f x2 (f x3 (... (f xn z)...)))
        {-   = foldr (.) id (map f xs) z
             = foldr ((.) . f) id xs z
             = foldr ((.) . f) (const z) xs ()
             = f x1 . f x2 . f x3 . ... . f xn . const z $ ()  -}

In the case of infinite lists though, do consult the answers here and here, these posts, etc..

I would upvote twice, if I could. In particular I found the other ways of writing it quite educational! — Micha Wiedenmann, Sep 25 '19 at 08:44
@MichaWiedenmann thanks! I'm glad it helps. :) (btw I proposed once, on meta, the ability to up/down vote multiple times in exchange for some reputation deduction, and was downvoted into the ground. :) ) — Will Ness, Sep 25 '19 at 10:03

score 2 · Answer 2 · answered Sep 25 '19 at 08:09

That's not zipping, since zipping means you iterate concurrently over the two lists. You here want to produce a tuple for every item in the first list, and every item in the second list.

We can handle that by making use of the (<$>) :: Functor f => (a -> b) -> f a -> f b and the (<*>) :: Applicative f => f (a -> b) -> f a -> f b. A list is both a member of the Functor and Applicative typeclass. So for a list (<$>) is the same as map, and for a list (<*>) :: [a -> b] -> [a] -> [b] will take every function from the first list, and every value from the second list, and apply the function to that item in the new list.

We thus can implement the rolls as:

rolls :: (Num a, Enum a, Num b, Enum b) => [(a,b)]
rolls = (,) <$> [1 .. 6] <*> [1 .. 6]

Zipping in Haskell

2 Answers2