0

我正在研究 Haskell 中的一个函数，它将获取一个列表并将其分成两个大小均匀的列表。这是我所拥有的：

split (x:y:xs) = split2 ([((length(x:y:xs) `div` 2)-2) : x ++ y] : [xs])
split2 (x:xs:[y:ys]) = split2 ((x-1) : [xs] ++ y : [ys])
split2 (0:xs:[y:ys]) = (xs:[y:ys])

该函数获取列表的前两个元素，并将它们放在列表 #2 中，并将第一个列表作为第二个元素附加。然后它获取列表的长度，并将其除以 2 以找出运行次数，同时考虑到它已经从第一个列表中删除了两个元素。然后它将这两条信息放入 split2 中，它从第一个列表中获取另一个元素并将其附加到第一个元素中的第二个列表中，它还从运行次数倒数 1，然后再次运行。

问题是，当我运行它时，我得到了这个：

Functions.hs:19:49:
    Occurs check: cannot construct the infinite type: t0 = [t0]
    In the first argument of `(:)', namely `(y)'

19 指的是第 2 行，第一个 split2 函数。不完全确定如何解决此错误。有任何想法吗？

4

4 回答 4

3

很难知道从哪里开始...

让我们从更大的表达式块中定义函数split2。

f1 (x:y:xs) = (length(x:y:xs) `div` 2)-2
f1 :: [a] -> Int

好的，所以参数是一些东西的列表，它返回一个Int

f2 (x:y:xs) = ((length(x:y:xs) `div` 2)-2) : x
f2 :: [[Int]] -> [Int]

在这里，length Intis 与x, so xmust be [Int], so (x:y:xs)must be相矛盾[[Int]]。我们还可以推断出 与y具有相同类型的x，并且xs是相同类型事物的列表；[[Int]]. 所以x ++ y也会[Int]。

所以，[xs]会有 type [[[Int]]]。现在，我们将结果包装在一个列表构造函数中，并使用[xs]：

f3 (x:y:xs) = [((length(x:y:xs) `div` 2)-2) : x ++ y] : [xs]
f3 :: [[Int]] -> [[[Int]]]

我猜你没想到参数是Ints 列表的列表。

现在，如果我们查看split2，参数模式(x:xs:[y:ys])暗示它是以下类型：

split2 :: [[a]] -> b
     x :: [a]
    xs :: [a]
     y ::  a
    ys :: [a]

的第一个定义的 rhssplit2尝试通过连接(x-1) : [xs]和来构造一个新列表y : [ys]。但是，如果我们将类型替换为y : [ys]，我们会发现：

y : [ys] :: a : [[a]]

但是由于(:) :: a -> [a] -> [a]，这意味着它[[a]]必须与 的类型相同[a]，或者a必须是自身的列表，这是不可能的。

(x-1)也输入错误，因为它试图从列表中减去一个。

我不知道您是否要将列表拆分为偶数和奇数元素，或者拆分为前半部分和后半部分。

以下是分为前半部分和后半部分的两个版本，如果长度为奇数，则向下取整 (RD) 或向上取整 (RU)：

splitRD xs = splitAt (length xs `div` 2) xs
splitRU xs = splitAt ((length xs + 1) `div` 2) xs

这是一个将列表拆分为偶数和奇数元素的版本：

splitEO [] = ([], [])
splitEO [e] = ([e], [])
splitEO (e:o:xs) = (e:es, o:os) where (es, os) = splitEO xs
于 2012-10-09T05:32:56.117 回答
0

几点建议

  • 将类型写入所有函数。它使代码更具可读性，也有助于捕捉错误。

  • 的类型++是[a] -> [a] -> [a]，您正在添加列表的长度以及元素。由于 list 必须是统一类型并且长度返回Int类型，所以编译器推断类型为splitas [[Int]] -> t（假设 split2 返回 type t）。

  • 当您将 ([((length(x:y:xs)div传递2)-2) : x ++ y] : [xs])给 split2. xsis of type[[Int]]这意味着 [xs]is of type [[[Int]]] ，因此编译器推断类型为split2to [[[Int]]] -> t。

现在在 split2 的定义中

 split2 (x:xs:[y:ys]) = split2 ((x-1) : [xs] ++ y : [ys])

ys是类型的[[Int]]，所以y也是类型的[Int]。xs是类型[[Int]]，但你正在做[xs] ++ y，这意味着两者都[xs]应该y是相同的类型（[a]对于某些a）。

由于您没有提供任何类型，编译器完全混淆了如何推断这种类型。

如果您只是想将列表分成两个相等的部分，为什么不做一些更简单的事情，比如

split3 :: [a] -> ([a], [a])
split3 [] = ([],[])
split3 [x] =  ([x],[])
split3 (x:y:xs) = let (xs',ys') = split3 xs in (x:xs',y:ys')
于 2012-10-09T05:09:46.313 回答
0

在 Haskell 中，列表的元素必须是相同的类型。在您的函数中，列表包含 Ints、原始列表的元素和原始列表的子列表的混合，所有这些都可能是不同的类型。

您对如何附加列表和元素也有一些困惑。x ++ y 只能在 x 和 y 本身是列表时使用，而 x : y 只能在 y 是列表且 x 是列表的元素时使用；要创建一个包含 x 和 y 作为元素的新列表，请改用 [x, y] （尽管 x:[y] 也可以）。同样 [xs] ++ y 需要改为 xs ++ [y] 。

在不改变基本算法的情况下，最简单的解决方案可能是让 split2 采用 3 个单独的参数。

split (x:y:xs) = split2 ((length(x:y:xs) `div` 2)-2) [x,y] xs
split2 n xs (y:ys) = split2 (n-1) (xs++[y]) ys
split2 0 xs ys = [xs,ys]
于 2012-10-09T05:24:57.760 回答
0

您似乎在列表中传递状态而不是作为值传递给函数，当编译器看起来好像您正在创建异构值列表时会产生问题，而 Haskell 中的列表应该是同质类型.

代替

split2 (0:xs:[y:ys])

您应该像这样将不同的参数/值分别传递给函数

split2 n xs (y:ys)

您正在寻找的功能也在标准库函数中重现。

halveList xs = splitAt (length xs `div` 2) xs
于 2012-10-09T05:26:00.350 回答