压缩 Haskell

Question

我正在开发一个函数，它将使用两个六面骰子和 return 元组列表中的每一种可能的对。

所以，我希望我的程序 return 类似于：

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

当您第一次开始学习递归编程时/Haskell，手动编写解决方案很有价值。当你已经内化了它们捕获的各种模式时，你可以稍后学习基元的杂耍。

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

这将两个列表合并为一个矩阵，逐行跟踪它：

                  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)   ....
        .      ........................
        .      ........................

所以是的，您的想法或多或少是在正确的方向上，只是 zip 不是那里的正确工具，而是 map。其他写法是：

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

所以它只是两个列表的笛卡尔积，或者一种外积。

这种“正方形”/2D匹配与

形成对比

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)...)))
        {-   = 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 $ ()  -}

虽然在无限列表的情况下，请参考答案 here and here, these posts，等等。

Answer 2

这不是压缩，因为压缩意味着您同时迭代两个列表。您在这里想要为第一个列表中的每个项目和第二个列表中的每个项目生成一个元组。

我们可以使用 (<$>) :: Functor f => (a -> b) -> f a -> f b and the (<*>) :: Applicative f => f (a -> b) -> f a -> f b 来解决这个问题。列表是 Functor 和 Applicative 类型类的成员。因此，对于列表 (<$>) 与 map 相同，而对于列表 (<*>) :: [a -> b] -> [a] -> [b] 将从第一个列表中获取每个函数，从第二个列表中获取每个值，并将该函数应用于新列表。

因此我们可以将 rolls 实现为：

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

压缩 Haskell

Zipping in Haskell

haskell

tuples

list

cartesian-product