在Haskell中压缩

Question

我正在开发一个函数，该函数将使用两个六个六边形的骰子，并在元组列表中返回配对的所有可能性。

因此，我希望我的程序返回如下内容：

[(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)]

我认为我的头可能在正确的常规区域，但是执行起来有点麻烦，因为我是Haskell的新手。这是我所拥有的：

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 

我知道最后一部分是非常错误的，相信我。我以前是zip将两个骰子放在一起，然后想到要放下head第二个骰子，然后重复该过程，直到sndDice没有空并找到所有的骰子对为止。

我不确定这个想法是否错误，或者只是我的业余执行不正确。

（根据记录，我知道它不会编译！我也不知道如何处理该错误。）

Answer 1

When you first start 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 
            = 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

它通过“线性”匹配将其两个参数列表组合在一起，让人联想到内部乘积。

但是也

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 ]  []

以来

foldr f z xs = foldr (($) . f) z xs 
             = foldr ($) z (map f xs) 
             = f x1 (f x2 (f x3 (... (f xn z)...)))