Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.5k views
in Technique[技术] by (71.8m points)

haskell - Flatten a list of lists

I have to write a function that flattens a list of lists.

For example flatten [] = [] or flatten [1,2,3,4] = [1,2,3,4] or flatten [[1,2],[3],4,5]] = [1,2,3,4,5]

I'm having trouble with the being able to match the type depending on what is given to the flatten function.

Here's what I have:

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])

From what I can tell the issue is that the ++ operator is expecting a list for both of its arguments and I'm trying to give it something of type A. I've added the A type so the function can either get a single element or a list of elements.

Does anyone know a different way to do this differently, or explain what I can do to fix the type error?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

It's a bit unclear what you are asking for, but flattening a list of list is a standard function called concat in the prelude with type signature [[a]] -> [a].

If you make a data type of nested lists as you have started above, maybe you want to adjust your data type to something like this:

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

Then you can flatten these to a list;

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

As a test,

 > flatten (ListOfLists [List [1,2],List [3],ListOfLists [List [4],List[5]]])
 [1,2,3,4,5]

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...