Haskell - разбиение списка на несколько списков

Question

Если отсортирован список кортежей, вернуть список, содержащий список кортежей, где каждый список кортежей соответствует условиям:

1) для каждого (a, b) и (c, d) в списке кортежей, a == c

2) второй элемент каждого кортежа должен быть предыдущим + 1, поэтому для [(a, y1), (b, y2), (c, y3)] => y2 = y1 + 1; у3 = у2 + 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)] ]

Это должно быть реализовано с использованием сгиба.

Моя реализация:

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

Обратите внимание, что при использовании 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. Наконец, в качестве примечания, объявляем:

groupTogether [] = []

не обязательно. Поскольку foldr вернет свой второй аргумент при передаче пустого списка в groupTogether, в этом примере вернем [].

Answer 2

В

[(a,b)] : last acc

у нас есть:

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

Таким образом, [(a,b)] имеет правильный тип, чтобы быть первым элементом [[(Integer, Integer)]], но last acc не имеет правильного типа, чтобы быть хвостом [[(Integer, Integer)]].

В

(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) не имеет правильного типа в качестве хвоста [[(Integer, Integer)]].

Я оставляю исправления на ваше усмотрение; надеюсь, это объясняет значение ошибки настолько, что вы можете добиться прогресса.