Как справиться с рекурсией по списку в Haskell (операция транспонирования)

Хотя я понимаю, что в Haskell могут быть функции транспонирования или ZipList, я пытаюсь создать свою собственную функцию транспонирования, которая будет принимать n списки равной длины m и транспонировать их в m списков длины n.

Пока у меня есть функция, почти работающая со следующим кодом:

list = [[1,2,3],[4,5,6],[7,8,9]]

head' (x:xs) = x

head'' [] = []
head'' (xs:lxs) = head' xs:head'' lxs

tail' [] = []
tail' (x:xs) = xs

tail'' [] = []
tail'' (xs:lxs) = tail' xs:tail'' lxs

merge (xs:lxs) = (head' xs:head'' lxs):(merge (tail' xs:tail'' lxs))

и я получаю следующий вывод, когда я запускаю > merge list в ghci, я получаю:

[[1,4,7],[2,5,8],[3,6,9],[*** Exception: list2.hs:16:1-16: Non-exhaustive patterns in function head'

что, я почти уверен, означает, что базовый случай пустого списка в моей функции head' отсутствует. Список транспонируется, просто не закрывается. Как решить эту проблему в данном случае? У меня есть подозрение, что это может быть связано с Maybe, но у меня возникли проблемы с его реализацией таким образом.


list recursion transpose haskell non-exhaustive-patterns
person Ron F    schedule 04.01.2019    source источник
comment
head' (x:xs) = x, а что такое head' []?   -  person Adam Smith    schedule 04.01.2019
comment
Начиная с head' xs:head'' lxs = head'' (xs:lxs), вы можете свернуть merge (xs:lxs) = (head' xs:head'' lxs):... в merge (xs:lxs) = (head'' (xs:lxs)):.... Аналогичные рассуждения об уравнениях применимы к ..., что дает merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). В этот момент нет особого смысла в сопоставлении с образцом; merge lxs = head'' lxs:tail'' lxs. Но теперь вы определенно должны быть подозрительны: это определение merge, очевидно, всегда вызывает (:) и никогда []. Так как же добраться до конца вывода merge?   -  person Daniel Wagner    schedule 04.01.2019

Ответы (2)


arrow_upward
1
arrow_downward

Вам нужно добавить условия выхода:

merge [] = []
merge ([]:xss) = merge xss
person talex    schedule 04.01.2019
comment
Так когда же работает merge ([]:xss) = merge xss в отличие от двух других определений merge? - person Ron F; 04.01.2019

arrow_upward
0
arrow_downward

map — это все, что вам нужно, в дополнение к существующим функциям head и tail. Для простоты предполагается, что ввод всегда является непустым списком (т. е. xs может быть [[],[],[]], но никогда не [], поэтому нет проблем с использованием head или tail).

> map head list
[1,4,7]
> map tail list
[[2,3],[5,6],[8,9]]
> let foo xs = if null (head xs) then [] else map head xs : foo (map tail xs)
> foo list
[[1,4,7],[2,5,8],[3,6,9]]
person chepner    schedule 04.01.2019