debugging - Haskell置换功能无法编译

Question

我正在复习一些Haskell，并且尝试编写一个可以映射[1,2,3]-> [[1,2,3]，[1、3、2]，[2,1]的置换函数，3]，[2,3,1]，[3,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)

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

listProduct x (permute (exclude x list))

def的类型也是[[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的正确返回类型。

怎么修

通过连接所有列表，将该[[[a]]]转换为[[a]]。

添加Eq a约束，因为您在/= x中使用exclude

当前的基本情况是，空列表没有排列，这是错误的。[]有一个排列。 (的确是0!= 1，而不是0)