Haskell 中包含序列大小写的元组列表

Question

我正在 Haskell 中学习 Monads，我正在尝试从函数 (coupleUp3) 一路上升到 ... (coupleUp1) 的最小情况 m 就像我在电脑爱好者的视频中看到 https://www.youtube.com/watch?v=t1e8gqXLbsU&t=1173s.

然而，我卡住了，结果总是for

[1..3]

类似于：

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

这不是我想要的，我想要

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

这是其他函数的作用。这是代码，我只是在寻找如何以这种方式实现函数 coupleUp1 的想法。您可以通过查看 coupleUp3 和 coupleUp2 来了解我正在尝试做什么。谢谢！

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

列表理解和do 表示法：

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

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

对绑定运算符进行脱糖 >>=:

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

并且 >>= 和 pure 的定义可以为给定的 monad 内联：

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

再细分一下：

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

如果你想比这更进一步，你可以内联一些concat和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 [] = []

然后逐步重写，简化和内联，直到你得到这样的结果：

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

现在这个定义从字面上说明了它的作用：“将列表与其自身配对 (f)，对于列表中的每个元素 (pairWithSelf)，将该元素与每个元素配对列表的 (pairEachWith)”。

pairWithSelf中的(++)来自内联concat，pairWithSelf和pairEachWith中的递归来自内联[=]的两层23=]。您不能轻易地将其“折叠”为单个非嵌套递归函数，因为解决方案本质上涉及对列表的嵌套迭代。

此外，这是一个相当乏味的过程，因为您实际上是在手动执行，象征性地，语言将在优化期间或运行时自动为您执行的操作。

因为你有一个递归结构，你真的不能让它更“原始”。（好吧，您可以使用 fix 将局部函数 pairWithSelf 和 pairEachWith 转换为匿名 lambda，这可能是了解 fix 的一个很好的练习。）

此外，此过程与您通常在 Haskell 中执行的方式相反：我们通常希望找到最通用和高级的最少可以使用显式递归实现。

回到更高层次，当您看到绑定两个独立操作（在本例中为列表）并将结果与纯函数组合的常见模式时：

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

那你就可以用Applicative functions代替了。这里，combine 是对构造函数 (,) 并且 xs 和 ys 是相同的，因此您可以编写以下任一内容：

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

Applicative 的这种用法在普通 Haskell 代码中很常见，只要您需要形状类似于“笛卡尔积”的计算（例如一对 table 或乘法 table）或者您想将 monadic 操作的结果传递给纯函数，而不用 do 表示法中的绑定语句 <- 显式绑定名称。

Haskell 中包含序列大小写的元组列表

List of tuples in Haskell with case of sequences

monads

haskell