展平列表清单

Question

我必须编写一个使列表列表变平的函数.

例如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类型,因此函数可以获得单个元素或元素列表.

有没有人知道以不同的方式做到这一点,或解释我可以做些什么来修复类型错误？

Answer 1

它有点不清楚你要求的是什么,但是列表列表是一个标准函数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]

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)