在Haskell中过滤具有相同数量不同元素的列表

html5 • • 问答

我非常新的Haskell和我的数据data Instruction = Add | Sub | Mul | Div | Dup | Pop deriving (Eq,Ord,Show,Generic)，我用所有可能的组合生成列表Mul和Dup与mapM (const [Mul, Dup]) [1..n])大小为n的。

我只想要以开头Dup和结尾的列表，Mul所以我使用了filter((== Mul) . last)(filter((== Dup) . head) (mapM (const [Mul, Dup]) [1..n]))但我也只想要具有相同数量的列表Mul，并Dup在他们，但我似乎无法拿出这样做的方式。我如何过滤这个，是否有更有效的方法来做到这一点，因为随着列表变大可能会有大量的组合？

样本名单是这样的：[Dup,Mul,Dup,Mul]和[Dup,Dup,Mul,Mul]尺寸为4的名单。

回答

虽然您的方法是正确的，但我认为这不是最有效的方法。您生成2^N列表，然后过滤掉其中的许多列表。忘记保持计数简单的其他要求，通过要求我们有与Muls一样多的Dups，我们最终只得到choose(N, N/2)列表（大小N/2为的子集的数量1..N），这是一个小得多的数字。

相反，我们可以尝试避免过滤并生成想要的列表，首先。我建议采用以下方法，您可以根据需要对其进行修改以满足其他要求。

我们定义一个函数sameMulDup，它接受两个整数m和d，并产生所有列表m MulS和d Dup秒。

sameMulDup :: Int -> Int -> [[Instruction]]
sameMulDup 0 d = [replicate d Dup]
sameMulDup m 0 = [replicate d Mul]
sameMulDup m d = do
    -- generate the first element
    x <- [Dup, Mul]
    -- compute how many m and d we have left
    let (m', d') = case x of
           Dup -> (m  , d-1)
           Mul -> (m-1, d  )
    -- generate the other elements
    xs <- sameMulDup m' d'
    return (x:xs)

直观地说，如果d=0或m=0只有一个可能的列表包含在 out list-of-lists 结果中。否则，我们非确定性地选择第一个元素，递减相应的计数器dor m，并生成其余的。

或者，最后一个方程可以替换为以下更基本的方程：

sameMulDup m d =
    map (Dup:) (sameMulDup m (d-1))
    ++
    map (Mul:) (sameMulDup (m-1) d)

无论如何，鉴于sameMuldup，您应该能够解决您的全部任务。

以上是在Haskell中过滤具有相同数量不同元素的列表的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>