Haskell Tree to List - preorder遍历

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等(见这里供参考).

特别是,您可以获取您要搜索的列表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