python - 尝试将 python 函数转换为 haskell 时，haskell 出现无限类型错误。为什么？

Question

def get_N_Partition_Permutations(xs, n):
    if n == 1:
        return [[xs]]
    acc = []
    for i in xrange(1,len(xs)):
        acc += [[xs[:i]] + j for j in get_N_Partition_Permutations(xs[i:], n-1)]
    return acc

我正在尝试在下面的 haskell 中实现上面的函数(在 Python 中)。

getNPartitionPermutations :: [a] -> Int -> [[[a]]]
getNPartitionPermutations xs 1 = [[xs]]
getNPartitionPermutations xs n = iter xs 1 []
  where iter ys i acc
          | length xs == i = acc
          | otherwise      =
              iter ys (i+1) (elem':acc)
                where elem' = map (\x -> [(take i ys)]:x) rec'
                      rec' = getNPartitionPermutations (drop i ys) (n-1)

我遇到了一个我不完全理解的奇怪错误。为什么这段代码在 python 中有效，但在 haskell 中无效？错误信息如下

partitionArr.hs|23 col 104 error| Occurs check: cannot construct the infinite type: a ~ [[a]]
Expected type: [[[a]]]
Actual type: [a]
Relevant bindings include
  acc :: [[[[[a]]]]] (bound at partitionArr.hs:21:19)
  ys :: [a] (bound at partitionArr.hs:21:14)
  iter :: [a] -> GHC.Types.Int -> [[[[[a]]]]] -> [[[[[a]]]]] (bound at partitionArr.hs:21:9)
  xs :: [[[a]]] (bound at partitionArr.hs:20:27)
  getNPartitionPermutations :: [[[a]]] -> GHC.Types.Int -> [[[[[a]]]]]
  (bound at partitionArr.hs:19:1)
  In the first argument of ‘Algo.getNPartitionPermutations’,
    namely ‘(GHC.List.drop n ys)’
  In the second argument of ‘(GHC.Base.$!)’,
    namely ‘Algo.getNPartitionPermutations (GHC.List.drop n ys) (n
    GHC.Num.- 1)’

partitionArr.hs|20 col 39 error| Occurs check: cannot construct the infinite type: a ~ [[a]]
Expected type: [a]
Actual type: [[[a]]]
Relevant bindings include
  iter :: [a] -> GHC.Types.Int -> [[[[[a]]]]] -> [[[[[a]]]]] (bound at partitionArr.hs:21:9)
  xs :: [[[a]]] (bound at partitionArr.hs:20:27)
  getNPartitionPermutations :: [[[a]]] -> GHC.Types.Int -> [[[[[a]]]]]
  (bound at partitionArr.hs:19:1)

In the first argument of ‘iter’, namely ‘xs’In the expression: iter xs 1 []

编辑:因为我不清楚。 python 函数所做的是返回列表的所有可能的 n 个分区。所以参数 [1,2,3,4],2 给出 [[[1],[2,3,4]],[[1,2],[3,4]],[[1,2,3 ][4]]]

haskell 函数的类型签名是 [a] -> Int -> [[[a]]]

Answer 1

首先，我使您的 Haskell 代码更易于理解:

getNPartitionPermutations :: [a] -> Int -> [[[a]]]
getNPartitionPermutations xs 1 = [[xs]]
getNPartitionPermutations xs n = iter xs 1 []
      where iter ys n acc
              | length xs == n = acc
              | otherwise      =
                  iter ys (n+1) (elem:acc)
                    where elem = map (\x -> [(take n ys)]:x) rec'
                          rec' = getNPartitionPermutations (drop n ys) (n-1)

看起来类型问题来自 elem 定义中的这个表达式:

[(take n ys)]:x

如果将其替换为 head x 或 take n ys 或 take n ys++ x，代码将编译。这表明您以某种方式提供了 [[[a]]] 类型的值，而不是 [a] 类型的值。也就是说，您有 2 个带有 [] 的额外包装。

虽然我没有花时间完全理解您的代码的用途，但我很确定根据这些提示您可以找出问题所在。

编辑:问题是使用 : 而不是 ++，以及 [take n ys] 中不必要的包装，所以替换为 take n ys++ x 是可行的方法。 (只是将评论合并到答案中)

---

一般建议:

跟踪/查明类型错误的方法是首先按照我的方式重构代码，即拆分大表达式并为子表达式命名，以便它们的含义变得更加明显，这样您就可以临时替换某些部分undefined 的整体表达式，因为 undefined 有你喜欢的任何类型，因此你可以让你的代码编译，而不必一次性弄清楚所有的代码。例如，这是我在尝试 head x 和 take n ys 之前结束的地方(注意 (\x -> undefined) 位) :

getNPartitionPermutations :: [a] -> Int -> [[[a]]]
getNPartitionPermutations xs 1 = [[xs]]
getNPartitionPermutations xs n = iter xs 1 []
      where iter ys n acc
              | length xs == n = acc
              | otherwise      =
                  iter ys (n+1) (elem:acc)
                    where elem = map (\x -> undefined) rec'
                          rec' = getNPartitionPermutations (drop n ys) (n-1)

——这是仍在编译的原始代码的最大子集。

在那之前，我有:

getNPartitionPermutations :: [a] -> Int -> [[[a]]]
getNPartitionPermutations xs 1 = [[xs]]
getNPartitionPermutations xs n = iter xs 1 []
      where iter ys n acc = undefined

之后我逐渐开始重新引入原始位，将 undefined 位移到代码树的下方:

getNPartitionPermutations :: [a] -> Int -> [[[a]]]
getNPartitionPermutations xs 1 = [[xs]]
getNPartitionPermutations xs n = iter xs 1 []
      where iter ys n acc
              | length xs == n = acc
              | otherwise      = undefined

然后

getNPartitionPermutations :: [a] -> Int -> [[[a]]]
getNPartitionPermutations xs 1 = [[xs]]
getNPartitionPermutations xs n = iter xs 1 []
      where iter ys n acc
              | length xs == n = acc
              | otherwise      =
                  iter ys (n+1) (elem:acc)
                    where elem = undefined
                          rec' = undefined

等等。