时间戳

首页 > 解决方案 > Haskell中带有序列大小写的元组列表

haskell - Haskell中带有序列大小写的元组列表

问题描述

我正在学习 Haskell 中的 Monads，我正试图从一个函数 (coupleUp3) 一直上升到 ... (coupleUp1) 的最小案例 m，就像我在电脑发烧友的视频中看到的那样 https:// www.youtube.com/watch?v=t1e8gqXLbsU&t=1173s。

但是，我被卡住了，结果总是

[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

标签： haskellmonads

解决方案

列出理解和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 内联and 的定义：

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

然后分解了一下：

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

如果你想更进一步，你可以内联一些简单的concatand定义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”。

(++)inpairWithSelf来自于内联，而in和concat递归来自于内联的两个层次。您不能轻易地将其“折叠”为单个非嵌套递归函数，因为该解决方案固有地涉及对列表的嵌套迭代。pairWithSelfpairEachWithmap

此外，这是一个相当乏味的过程，因为您实际上是在手工完成，象征性地，语言会在优化期间或运行时自动为您做些什么。

因为你有一个递归结构，所以你不能真正让它变得更“原始”。（好吧，您可以使用它fix来制作本地函数pairWithSelf和pairEachWith匿名 lambda，这可能是一个很好的学习练习fix。）

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

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

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

然后你可以用 Applicative 函数替换它。在这里，combine是对构造函数(,)，并且xs和ys是相同的，所以你可以编写以下任何一个：

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

Applicative 的这种用法在普通的 Haskell 代码中非常常见，无论何时您需要类似“笛卡尔积”的计算（例如配对表或乘法表），或者您想将单子操作的结果传递给纯函数而不显式绑定一个带有绑定语句的<-名称do。

推荐阅读