Haskell置换函数无法编译

Question

我正在复习一些Haskell，我正在尝试编写一个置换函数，它将映射1,2,3 -> [1,2,3，2，2,1,3，3，2，2，3，3，2，2,3,1，1，2，3,2,1]。我有以下资料-

permute:: [a] -> [[a]]
permute [] = []
permute list = map f list
        where
                f x = listProduct x (permute (exclude x list))
                exclude e list1 = filter (/= e) list1
                listProduct x list2 = map (x :) list2

以下是我收到的错误消息-

permutations.hs:3:20:
    Couldn't match type `a' with `[a]'
      `a' is a rigid type variable bound by
          the type signature for permute :: [a] -> [[a]]
          at permutations.hs:1:11
    Expected type: a -> [a]
      Actual type: a -> [[a]]
    In the first argument of `map', namely `f'
    In the expression: map f list
    In an equation for `permute':
        permute list
          = map f list
          where
              f x = listProduct x (permute (exclude x list))
              exclude e list1 = filter (/= e) list1
              listProduct x list2 = map (x :) list2
Failed, modules loaded: none.

我会试着调试，但它甚至不能编译。有什么想法吗？

Answer 1

让我们只关注涉及的列表类型：

permute (exclude x list)

由于permute的类型签名，它的类型为[[a]]，因此

listProduct x (permute (exclude x list))

根据定义，也是[[a]]类型。listProduct的

listProduct x list2 = map (x :) list2

总而言之，

 f x = listProduct x (permute (exclude x list))

返回[[a]]，但随后

permute list = map f list

将f应用于[a]的所有元素，并返回[[[a]]]，这不是permute的正确返回类型。

如何修复

1. 通过连接所有列表将该[[[a]]]转换为[[a]]。
2. 添加了一个Eq a约束，因为您在基本用例中使用的是/= x，当前声明空列表没有排列，这是错误的。[]有一种排列方式。(实际上，0!=1，而不是0)

Answer 2

对于任何可能感兴趣的人来说-为了解决这个问题，我需要一种方法来模拟命令式编程的迭代，因此出现了一个循环列表(本质上，我一直在尝试模拟我曾经用javascript编写的解决方案，它涉及到我描述的相同过程，唯一的例外是我利用了for循环)。

permute [] = [[]]
permute list = [h:tail | h <- list, tail <- (permute (exclude h list))]
  where
    exclude x = filter (/= x)

不一定是最有效的解决方案，因为exclude是一个O(n)操作，但很整洁，可以很好地作为概念验证。

Answer 3

要做到这一点，“正确”的方法是将挑选和排除列表项合并为一个纯粹的位置操作select :: [a] -> [(a,[a])]

import Control.Arrow (second)
-- second f (a, b) = (a, f b)

select [] = []
select (x:xs) = (x,xs) : map (second (x:)) (select xs)

permute [] = [[]]    -- 1 permutation of an empty list
permute xs = [x : t | (x,rest) <- select xs, t <- permute rest] 

要“调试”你的程序，你可以把它作为一个全局的程序来调试( define each internal function on its own )，然后看看这些零碎的东西是否适合在一起：

> let exclude e list1 = filter (/= e) list1
> let listProduct x list2 = map (x :) list2
> let f x = listProduct x (permute (exclude x list)) 
<interactive>:1:25: Not in scope: `permute' -- permute is not defined yet!!
<interactive>:1:44: Not in scope: `list'    -- need to pass 'list' in
> let f list x = listProduct x (undefined (exclude x list))
                                ---------   -- use a stand-in for now
> let permute [] = [] ; permute list = map (f list) list
> :t permute                           ---
permute :: (Eq t) => [t] -> [[[t]]]    -- one too many levels of list!

所以它们确实适合在一起，只是结果不是我们想要的。我们可以改变其结果的组合方式，而不是改变f产生的内容(正如编译器所建议的)。concat删除了一层列表嵌套(它是[]类型构造函数的一元join )：

> let permute [] = [] ; permute list = concatMap (f list) list
> :t permute                           ---------
permute :: (Eq t) => [t] -> [[t]]      -- much better

顺便说一句，如果您不自己指定类型签名，它将编译[a] -> [[[a]]]类型并将其报告给您。

更重要的是，通过将/=带入图片中，您不必要地需要对列表中的项进行Eq a约束：permute :: (Eq a) => [a] -> [[a]]。