与发电机

Question

的任意数的Haskell列表综合所以我到目前为止是这样的：

combs :: [[Char]] 
combs = [[i] ++ [j] ++ [k] ++ [l] | i <- x, j <- x, k <- x, l <- x] 
    where x = "abc" 

因此，这是对于n = 4的工作职能，有没有什么办法，使这项工作为任意数量的发电机？我可以为n = 1,2,3等编程，但理想情况下需要它为任何给定的n工作。作为参考，x只是一个任意字符串的唯一字符。我正在努力想办法以某种方式将它解压为n个生成器。

Answer 1

您可以使用replicateM：

replicateM :: Applicative m => Int -> m a -> m [a] 

例如为：

generate :: Num a => Int -> [[a]] 
generate = flip replicateM [1,2,3] 

产生给定长度的所有possiible列表和由元件1..3的。

Answer 2

据我所知，你不能用任意数量的生成器构造列表理解，但通常如果你做任意深度的事情，递归就是这样做的方法。

所以我们必须考虑解决这个问题，就其本身而言。如果您想要使用x中的字符生成所有可能的字符串。在n = 0的情况下，我们可以生成一个字符串：空字符串。

combs 0 = [""] 

所以一个元素列表[]。

现在的情况下，我们要生成一个字符的字符串，我们当然可以简单地返回x：

combs 1 = x 

现在的问题是如何处理的情况下，n > 1做。在这种情况下，我们可以获得所有长度为n-1的字符串，并且对于每个这样的字符串以及每个这样的字符在x中产生一个新的字符串。像：

combs n = [ (c:cs) | c <- x, cs <- combs (n-1) ] 

请注意，这使得第二种情况（n = 1）是多余的。我们可以从x中挑选一个字符c，并将其预先添加到空字符串中。所以一个基本的实现是：

combs :: Int -> [[Char]] 
combs 0 = [""] 
combs n = [(c:cs) | c <- x, cs <- combs (n-1)] 
    where x = "abc" 

现在我们仍然可以寻找改进。列表理解基本上是列表monad的语法糖。因此，我们可以在这里使用liftA2：

import Control.Applicative(liftA2) 

combs :: Int -> [[Char]] 
combs 0 = [""] 
combs n = liftA2 (:) x (combs (n-1)) 
    where x = "abc"

我们可能也想使字符集的参数：

import Control.Applicative(liftA2) 

combs :: [Char] -> Int -> [[Char]] 
combs _ 0 = [""] 
combs x n = liftA2 (:) x (combs (n-1))

，我们没有给我们限制字符，我们可以生产出certesian功率所有可能的类型：

import Control.Applicative(liftA2) 

combs :: [a] -> Int -> [[a]] 
combs _ 0 = [[]] 
combs x n = liftA2 (:) x (combs (n-1))

Answer 3

首先，我会将理解翻译为单调表达式。

x >>= \i -> x >>= \j -> x >>= \k -> x >>= \l -> return [i,j,k,l] 

随着n = 4我们看到我们有4 x的，一般都会有nx的。因此，我在考虑长度为n的x的列表。

[x,x,x,x] :: [[a]] 

我们该如何从[x,x,x,x]转到monadic表达式？第一个好的猜测是foldr，因为我们想要对列表中的每个元素进行一些操作。特别是，我们希望从每个x中获取一个元素并用这些元素形成一个列表。

foldr :: (a -> b -> b) -> b -> [a] -> b 
-- Or more accurately for our scenario: 
foldr :: ([a] -> [[a]] -> [[a]]) -> [[a]] -> [[a]] -> [[a]] 

有两个方面拿出了foldr相似，我会打电话f :: [a] -> [[a]] -> [[a]]和z :: [[a]]。我们知道什么是foldr f z [x,x,x,x]：

foldr f z [x,x,x,x] = f x (f x (f x (f x z))) 

如果加上括号前面的一元表达，我们有这样的：

x >>= \i -> (x >>= \j -> (x >>= \k -> (x >>= \l -> return [i,j,k,l]))) 

你可以看到两个表达式是如何寻找相似。我们应该能够找到一个f和z使它们相同。如果我们选择f = \x a -> x >>= \x' -> a >>= \a' -> return (x' : a')我们得到：

f x (f x (f x (f x z))) 
= (\x a -> a >>= \a' -> x >>= \x' -> return (x' : a')) x (f x (f x (f x z))) 
= f x (f x (f x z)) >>= \a' -> x >>= \x' -> return (x' : a') 
= f x (f x (f x z)) >>= \a' -> x >>= \l -> return (l : a') 
= (f x (f x z) >>= \a' -> x >>= \k -> return (k : a')) >>= \a' -> x >>= \l -> return (l : a') 
= f x (f x z) >>= \a' -> x >>= \k -> x >>= \l -> return (l : k : a') 

• 请注意，我已经逆转i,j,k,l顺序l,k,j,i但在寻找组合的情况下，这应该是不相关的。如果真的担心，我们可以试试a' ++ [x']。

的最后一步是因为(a >>= \b -> c) >>= \d -> e相同a >>= \b -> c >>= \d -> e（占可变卫生时）和return a >>= \b -> c相同(\b -> c) a。

如果我们继续展开这个表达式，最终我们将在前面达到z >>= \a' -> …。这里唯一有意义的选择是z = [[]]。这意味着foldr f z [] = [[]]可能并不理想（改为[]）。相反，我们可能使用foldr1（对于非空列表，我们可能使用Data.NonEmpty），或者我们可能会为空列表添加一个单独的子句到combs。

看着f = \x a -> x >>= \x' -> a >>= \a' -> return (x' : a')我们可能会意识到这种有用的等价性：a >>= \b -> return (c b) = c <$> a。因此，f = \x a -> x >>= \x' -> (x' :) <$> a。然后还有a >>= \b -> c (g b) = g <$> a >>= \b -> c等f = (:) <$> x >>= \x' -> x' <$> a。最后，a <*> b = a >>= \x -> x <$> b等等f = (:) <$> x <*> a。

The official implementationsequenceA列表是foldr (\x a -> (:) <$> x <*> a) (pure [])，正是我们在这里想到的。这可以进一步缩短为foldr (liftA2 (:)) (pure [])，但可能存在一些优化差异，使得实现者不选择此选项。

最后一步是仅仅想出一个nx的列表。这只是replicatereplicate n x。碰巧有一个既有复制又有排序的功能，叫做replicateMreplicateM n x。