Haskell

Question

给定一个排序的元组列表，return一个包含元组列表的列表，其中每个元组列表都符合以下条件：

1) 对于元组列表中的每个 (a,b) 和 (c,d)，a == c

2) 每个元组的第二个元素必须是前一个+1，所以对于[(a, y1), (b, y2), (c, y3)] => y2 = y1+1; y3 = y2 + 1

示例：

输入

ex = [(0,2),(1,0),(1,2),(1,3),(1,4),(2,4)]

输出

groupTogether ex = [[(0,2)], [(1,0)], [(1,2),(1,3),(1,4)],[(2,4)]]

这必须使用 fold 来实现。

我的实现：

groupTogether :: [(Integer,Integer)]-> [[(Integer,Integer)]]
groupTogether [] = []
groupTogether pairs@(x:xs) = foldr (\(a,b) acc -> if ( (a == fst(last(last(acc)))) && (b == fst(last(last(acc)))) ) 
                                                  then (a,b) : (last(last(acc))) 
                                                  else [(a,b)] : ((last(acc)))
                                   ) [[]] pairs

我得到的错误：

Answer 1

在

[(a,b)] : last acc

我们有：

     acc :: [[(Integer, Integer)]] -- presumed
last acc ::  [(Integer, Integer)]
[(a,b)]  ::  [(Integer, Integer)]

所以 [(a,b)] 具有作为 [[(Integer, Integer)]] 的第一个元素的正确类型，但是 last acc 没有作为 [=15= 的尾部的正确类型].

在

(a,b) : last (last acc)

我们有：

           acc  :: [[(Integer, Integer)]] -- presumed
      last acc  ::  [(Integer, Integer)]
last (last acc) ::   (Integer, Integer)
(a,b)           ::   (Integer, Integer)

所以 (a,b) 没有正确的类型作为 [[(Integer, Integer)]] 的第一个元素，并且 last (last acc) 没有正确的类型作为 [= 的尾部15=].

我把修复留给你；希望这足以阐明错误的含义，以便您取得进展。

Answer 2

注意当使用foldr时，给定列表右侧的元素将首先被处理。例如，列表：

[(0,2),(1,0),(1,2),(1,3),(1,4),(2,4)]

当处理第3个元素(1,2)时，处理的元素，即acc

acc = [[(1,3),(1,4)],[(2,4)]]

所以，需要与(1,2)比较的元素是(1,3)。那是 head (head acc) 而不是 last (last acc)。此外，可以通过模式匹配访问它，而不是使用 head：

(pairs@((x, y):xs):xss)

并与 (a, b) 比较：

a == x && b == (y - 1)

如果满足条件，将它们组合在一起：

((a, b):pairs):xss

此外，定义一个阶梯函数比使用匿名函数更具可读性，因为它需要处理最右边的空列表元素：

step p [] = [[p]]

一旦处理了第一个元素，acc = [[p]]并且在后续步骤中永远不会为空列表，因此匹配上面定义的模式。以下是阶梯函数的定义方式：

groupTogether = foldr step []
    where step p [] = [[p]]
          step p@(a, b) acc@(pairs@((x, y):xs):xss) 
                | a == x && b == (y - 1) = (p:pairs):xss
                | otherwise              = [p]:acc

了解foldr如何操作后，步进函数就很简单了。最后，作为旁注， declare:

groupTogether [] = []

没有必要。由于 foldr 在将空列表传递给 groupTogether 时将 return 它的第二个参数，在本例中， return [].

Haskell - 将一个列表拆分为多个列表

Haskell - spliting a list into several lists

list

fold