可变长度与固定集合的组合

Question

我有一组可能的颜色定义如下：

data Peg = Red | Green | Blue | Yellow | Orange | Purple
         deriving (Show, Eq, Ord)
colors = [Red, Green, Blue, Yellow, Orange, Purple]

代码是这样定义的颜色组合：

type Code = [Peg]

我希望能够生成所有可能的长度组合列表 len，这些组合可以由定义的颜色组成。

这是我的原创。我还在学习，所以我什至不确定我是否犯了一些不受支持的语法错误或结构。

allCodes :: Int -> [Code]
allCodes len = map (\p -> Code p) (permutations len)
    where
        permutations::Int->[Peg]
        permutations 0 = [[]]
        permutations n = [x:xs | x <- colors, xs <- permutations (n - 1)]

编译失败，出现错误：

[1 of 1] Compiling HW02             ( HW02.hs, interpreted )

HW02.hs:59:27: Not in scope: data constructor `Code'
Failed, modules loaded: none.

Code 在我使用过它的其他地方也可以使用，所以我不确定这里发生了什么。我知道像 replicateM 这样的函数可以很容易地解决这个问题，但我只想使用 Prelude.

中的函数

Answer 1

bhelkir 对问题的评论已正确诊断出您的错误，因此我将跳过它。

您的 allCodes 函数的逻辑基本上是合理的（撇开排列与组合问题）。值得指出的一件事是，通过在 Prelude:

中使用两个函数，可以实现与单行代码相同的效果

allCodes :: Int -> [Code]
allCodes len = sequence (replicate len colors)

跟随它一直到堆栈底部是有益的。首先，replicate函数做一个指定长度的列表，用相同的值填充所有位置：

replicate :: Int -> a -> [a]
replicate 0 _ = []
replicate n a | n > 0 = a : replicate (n-1) a
              | otherwise = error "replicate called with n < 0"

所以replicate 3 colors产生一个包含三个元素的列表，都是colors列表

现在，sequence函数有点神奇：

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) =
    do a <- ma
       as <- sequence mas
       return (a:as)

然而，当m = []时，这等同于：

sequence' :: [[a]] -> [[a]]
sequence' [] = [[]]
sequence' (ma:mas) = [(a:as) | a <- ma, as <- sequence mas]

所以基本上，单行代码与您的解决方案的想法相同，但重构为两个可重复使用的部分。

可变长度与固定集合的组合

Combinations of variable length with fixed set

haskell

permutation

combinatorics