Haskell 列出 monad 循环

Question

我有一个如下所示的列表理解：

cross ps = [  p* pp * ppp | p <- ps, pp <- ps, ppp <- ps, p >= pp , pp >= ppp ]

如何在不直接输入列表名称的情况下使用 monad 实现此目的？

dim ps n = do
    p <- ps
    pp <- ps
    ppp <- ps
    p...p <- ps

    guard (p >= pp && pp >= ppp ... && p...p >=p....p)
    return (p*pp*ppp*p...p)

如何在不显式分配值的情况下执行此操作以使用列表 monad？

Answer 1

这是我的做法

ascending :: Ord a => [a] -> Bool
ascending list = and $ zipWith (>=) (tail list) list

dim ps n = map product $ filter ascending allComb 
    where allComb = replicateM n ps

replicateM 来自 Control.Monad 并且对于列表 monad，它生成给定列表的 n 元素的所有组合。然后我只过滤掉按升序排列的组合，最后计算剩下的列表的乘积。

Answer 2

近似翻译可以是：

dim :: Num a => [a] -> Int -> [a]
dim ps n = do
  chosen <- replicateM n ps
  guard $ increasing chosen
  return $ product chosen

increasing :: Ord a => [a] -> Bool
increasing []        = True
increasing xs@(_:ys) = and $ zipWith (<=) xs ys

然而，这可以通过更早地放置守卫来改善。我的意思是：

[ ... | p1<-xs, p2<-xs, p3<-xs, p1 <= p2, p2 <= p3 ]

比

差

[ ... | p1<-xs, p2<-xs, p1 <= p2, p3<-xs, p2 <= p3 ]

因为后者会在 p1 <= p2 时避免为 p3<-xs 扫描整个列表，所以无论如何我们都不会生成任何东西。

所以，让我们再试一次，用更原始的方法：

dim :: Num a => [a] -> Int -> [a]
dim ps 0 = [1]
dim ps n = do
   x  <- ps
   xs <- dim (filter (>=x) ps) (n-1)
   return (x * xs)

现在我们尽早丢弃不可能的备选方案，在递归调用之前将它们从 ps 中移除。

Answer 3

也许最容易理解的解决方案是“字面上使用循环”：

dim ps n = do
    pz <- forM [1..n] $ \_i -> do
       p <- ps
       return p

    guard $ descending pz
    return $ product pz

但是 do {p <- ps; return p} 是 equivalent to simply ps，对于 forM [1..n] $ \_i -> ps 我们有 shorthand replicateM n ps。所以你得到了 chi 的建议解决方案。不过，我想说 Luka Horvat 的实际上要好一些。

但是话又说回来，正如 chi 所说，您可以通过不选择所有可能的组合并丢弃绝大多数，而只选择降序排列来提高效率首先是可能性。为此，我手动编写了一个递归函数：

descendingChoices :: Ord a => Int -> [a] -> [[a]]
descendingChoices 1 ps = [[p] | p<-ps]  -- aka `pure<$>ps`
descendingChoices n ps = [ p : qs | qs <- descendingChoices (n-1) ps
                                  , p <- ps
                                  , all (<=p) qs
                         ]

Answer 4

鉴于您的素数列表是按升序排列的，您可以完全避免守卫，只需生成每组产品一次即可开始：

cross :: Int -> [a] -> [[a]]
cross 0 _ = [[]]
cross n [] = []
cross n all@(x:xs) = ((x:) <$> cross (n - 1) all) ++ cross n xs

dim :: Num a => Int -> [a] -> [a]
dim n xs = map product $ cross n xs

Answer 5

如果素数列表不是按升序排列，那么最好的选择是对其进行排序并使用假定列表已排序的算法。 amalloy 给出了一个，但是您可以通过使用共享 (an example) .

另一个这样的算法是

dim :: (Num a, Ord a) => Int -> [a] -> [a]
dim 0 xs = [1]
dim n xs = [y * x | x <- xs, y <- dim (n - 1) (takeWhile (<= x) xs)]

请注意 takeWhile 而不是 filter。这样你就不需要一遍又一遍地处理整个素数列表，而是总是只处理你真正需要的那些素数。

Haskell 列出 monad 循环

Haskell list monad looping

monads

haskell

list-comprehension