Свести список списков

Мне нужно написать функцию, которая сглаживает список списков.

Например, flatten [] = [] или flatten [1,2,3,4] = [1,2,3,4] или flatten [[1,2],[3],4,5]] = [1,2,3,4,5]

У меня проблемы с возможностью сопоставить тип в зависимости от того, что задано функции сглаживания.

Вот что у меня есть:

data A a = B a | C [a] deriving (Show, Eq, Ord)

flatten::(Show a, Eq a, Ord a)=>A a -> A a
flatten (C []) = (C [])
flatten (C (x:xs) ) = (C flatten x) ++ (C flatten xs)
flatten (B a) = (C [a])

Из того, что я могу сказать, проблема заключается в том, что оператор ++ ожидает список для обоих своих аргументов, и я пытаюсь дать ему что-то типа A. Я добавил тип A, чтобы функция могла получить либо один элемент, либо список элементов.

Кто-нибудь знает другой способ сделать это по-другому или объяснить, что я могу сделать, чтобы исправить ошибку типа?


list types abstract haskell
person captainpirate    schedule 29.02.2012    source источник
comment
Я не уверен, что именно вы хотите. Может быть, flatten :: A [a] -> A a; flatten (B xs) = C xs; flatten (C xss) = C (concat xss) поможет вам? По сути, вы не можете написать flatten так, чтобы он брал списки с разной вложенностью и делал с ними разные вещи, если только вы не завернете их в новый тип и не разграничите случаи по конструктору.   -  person Daniel Fischer    schedule 01.03.2012
comment
Тип вашей функции должен быть [[a]] -> [a]. Это означает, что flatten [] допустимо, flatten [[1,2,3,4]] допустимо, а flatten [1,2,3,4] нет. [1,2,3,4] не является списком списков. Если вы подумаете об этом и начнете с самого начала, избавившись от своего особого типа, вам будет намного легче.   -  person Dan Hulme    schedule 01.03.2012
comment
возможный дубликат операции над списком списков | как   -  person rampion    schedule 01.03.2012

Ответы (4)


arrow_upward
30
arrow_downward

Немного неясно, что вы просите, но выравнивание списка списка — это стандартная функция, называемая concat в прелюдии с сигнатурой типа [[a]] -> [a].

Если вы создаете тип данных вложенных списков, как вы начали выше, возможно, вы захотите настроить свой тип данных примерно так:

 data Lists a = List [a] | ListOfLists [Lists a]

Затем вы можете свести их к списку;

 flatten :: Lists a -> [a]
 flatten (List xs) = xs
 flatten (ListOfLists xss) = concatMap flatten xss

В качестве теста,

 > flatten (ListOfLists [List [1,2],List [3],ListOfLists [List [4],List[5]]])
 [1,2,3,4,5]
person Malin    schedule 29.02.2012

arrow_upward
9
arrow_downward

Во-первых, тип А находится на правильном пути, но я не думаю, что это совсем правильно. Вы хотите, чтобы он мог сглаживать произвольно вложенные списки, поэтому значение типа «A a» должно содержать значения типа «A a»:

data A a = B a | C [A a]

Во-вторых, тип функции должен немного отличаться. Вместо того, чтобы возвращать значение типа «A a», вы, вероятно, захотите, чтобы оно возвращало просто список a, поскольку по определению функция всегда возвращает плоский список. Таким образом, сигнатура типа выглядит следующим образом:

flatten :: A a -> [a]

Также обратите внимание, что ограничения класса типов не нужны — эта функция полностью универсальна, поскольку она вообще не смотрит на элементы списка.

Вот моя реализация:

flatten (B a) = [a]
flatten (C []) = []
flatten (C (x:xs)) = flatten x ++ flatten (C xs)
person Mike T    schedule 29.02.2012

arrow_upward
2
arrow_downward

этот один лайнер сделает эту работу. Хотя, как упомянул Малин, сигнатура типа другая:

flatten :: [[a]] -> [a]         
flatten xs = (\z n -> foldr (\x y -> foldr z y x) n xs) (:) []

простой тест

frege> li = [[3,4,2],[1,9,9],[5,8]]
frege> flatten li
[3,4,2,1,9,9,5,8]
person A_P    schedule 08.02.2016
comment
Дело в том, что функция должна работать как для простых, так и для вложенных списков. Ваши работы только для простых списков. - person Lii; 08.02.2016

arrow_upward
1
arrow_downward

Сгладить через понимание списка.

flatten arr = [y | x<- arr, y <- x]
person windmaomao    schedule 06.12.2020