尝试将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是要走的路.(只是将评论纳入答案)

一般建议:

跟踪/精确定位类型错误的方法是首先按照我的方式重构代码,即拆分大表达式并为子表达式赋予名称,使其含义变得更加明显,因此您可以暂时替换整个表达式的某些部分with 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

等等.