遞歸數據結構的列表作爲功能輸入

我定義在Haskell遞歸數據結構：遞歸數據結構的列表作爲功能輸入

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，子列表[]]]？

來源

2017-04-14 Mithsul

以何種方式是不是定義你想要什麼？在我看來，它工作得很好 - 結果將是'[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] 
>

來源

2017-04-21 20:58:48

如果要將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

來源

2017-04-14 05:21:46 Lazersmoke

遞歸數據結構的列表作爲功能輸入

回答

相關問題