如何将Haskell中的Tree转换为平面列表

Question

我在Haskell中定义了一个树，类似于：

data NTree a = Nil | Tree a [NTree a] deriving Show

我想"压平"树，以便所有节点都显示在列表中。我正试图通过以下方式做到这一点：

arrayify :: NTree Int -> [Int]
arrayify (x:xs) = x ++ arrayify xs

我可以看出这是错误的，但我不知道如何解决这个问题。作为参考，这是我得到的错误：

• Couldn't match expected type ‘NTree Int -> [Int]’
with actual type ‘[Int]’
• Possible cause: ‘(++)’ is applied to too many arguments
In the expression: x ++ arrayify xs
In an equation for ‘arrayify’: arrayify = x ++ arrayify xs

Answer 1

由于arrayify需要NTree Int，您可能希望对两个数据构造函数进行模式匹配，因此：

arrayify :: NTree Int -> [Int]
arrayify Empty = …
arrayify (Tree v ts) = …

对于Empty的情况，您应该返回一个空列表，对于Tree v ts，您可以制作一个以v开头的列表，然后将ts元素的arrayifys作为子元素。您可以使用(:) :: a -> [a] -> [a]和concatMap :: Foldable f => (a -> [b]) -> f a -> [b]。

但是，您可以让Haskell为您的NTree:派生Foldable的实例，而不是自己编写arrayify

{-# LANGUAGEDeriveFoldable#-}
data NTree a = Nil | Tree a [NTree a] deriving (Foldable, Show)

然后可以对NTree对象调用toList :: Foldable f => f a -> [a]。