Haskell Tree to List - 前序遍历

Question

鉴于 Haskell 中的以下树结构:

data Tree = Leaf Int | Node Int Tree Tree deriving Show

如何让 Haskell 返回预先订购的数据列表？

例如给定一棵树:

Node 1 (Leaf 2) (Leaf 3)

返回类似:

preorder = [1,2,3]

Answer 1

您可以瞄准更通用的解决方案，并使您的数据类型成为 Foldable 的实例。 .
在 hackage 有一个非常相似的例子。 ，但这实现了订购后访问。
如果你想支持预购访问，你必须这样写:

import qualified Data.Foldable as F

data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving Show

instance F.Foldable Tree where
    foldr f z (Leaf x) = f x z
    foldr f z (Node k l r) = f k (F.foldr f (F.foldr f z r) l)

有了这个，您将能够使用适用于 Foldable 的所有功能。类型，如 elem , foldr , foldr , sum , minimum , maximum等等(请参阅 here 以供引用)。

特别是，您正在搜索的列表可以通过 toList 获得。 .以下是一些示例，说明您可以通过使用该实例声明来编写内容:

*Main> let t = Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5)
*Main> F.toList t
[1,2,3,4,5]
*Main> F.foldl (\a x -> a ++ [x]) [] t
[1,2,3,4,5]
*Main> F.foldr (\x a -> a ++ [x]) [] t
[5,4,3,2,1]
*Main> F.sum t
15
*Main> F.elem 3 t
True
*Main> F.elem 12 t
False