递归数据结构的列表作为功能输入

问题描述：

data NestedList a = Element a | SubList [NestedList a]

，然后我希望定义一个flatten功能将于NestedList的列表，并返回扁平结果，例如：

Input: [Element 1, SubList [Element 2, SubList [] ]] 
Output: [Element 1, Element 2].

然而，我的函数定义是不正确的：

flatten :: NestedList a -> [a] 
flatten (Element a) = [a] 
flatten (SubList (x:xs)) = flatten x ++ flatten (SubList xs) 
flatten (SubList []) = []

根据这个定义，我的功能会像：的

flatten (SubList [Element 1, SubList []])

代替

flatten [Element 1, SubList []]

所以这flatten不能采取我上面提到的输入，所以我应该如何定义flatten，使其接受输入如[元素1，子列表[元素2，子列表[]]]？

以何种方式是不是定义你想要什么？在我看来，它工作得很好 - 结果将是'[1]'，并且如果你想要将结果的每个元素都包含在Element中（无论出于何种原因...），那么只需执行'map Element。 flatten'。 – user2407038

一个更简单的等价定义是用'flatten（Sublist xs）= xs >> = flatten'来代替最后两个子句。 – amalloy

FWIW，'NestedList'只是'Free []'，而'flatten'只是'fromFoldable f => Foldable（Free f）'和'instance Foldable []'的'toList'。 – Lazersmoke

答

我怀疑你正在寻找以下：

flatten :: [NestedList a] -> [NestedList a] 
flatten (Element a : rest) = Element a : flatten rest 
flatten (SubList xs : rest) = flatten xs ++ flatten rest 
flatten [] = []

这似乎做你想要什么：

> flatten [Element 1, SubList []] 
[Element 1] 
> flatten [Element 1, SubList [Element 2, SubList []]] 
[Element 1,Element 2] 
>

答

如果要将NestedList平面化为平面NestedList而不是普通列表，则可以定义一个单独的函数fromList :: [a] -> NestedList a，该函数从普通列表构建平面嵌套列表。

fromList :: [a] -> NestedList a 
fromList l = SubList (toElems l) 
    where 
    toElems :: [a] -> [SubList a] 
    toElems (x:xs) = Element x : toElems xs 
    toElems [] = []

或者干脆

fromList = SubList . map Element

，写

flattenNested :: NestedList a -> NestedList a 
flattenNested = fromList . flatten

当然，你也可以写flatten本身更简单地为：

flatten :: NestedList a -> [a] 
flatten (Element a) = [a] 
flatten (SubList xs) = concat (map flatten xs)

或这些甚至一越来越新RDY代用品：

flatten (SubList xs) = concatMap flatten xs

由于concatMap相同=<<：

flatten (SubList xs) = flatten =<< xs

由于NestedList同构Free []：

flatten :: Free [] a -> [a] 
flatten (Pure a) = [a] 
flatten (Free xs) = flatten =<< xs

或使用此关系进一步由（AB）：

flatten :: Free [] a -> [a] 
flatten = toList

递归数据结构的列表作为功能输入

相关推荐