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

Question

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

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

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

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

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, чтобы функция могла получить один элемент или список элементов.

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

Answer 1

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

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

 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]

Answer 2

Во-первых, тип A находится на правильном пути, но я не думаю, что это правильно. Вы хотите, чтобы он мог выравнивать произвольно вложенные списки, поэтому значение типа «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)

Answer 3

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

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]