Trees

[Paul Rubin]

Rustom Mody <rustompmody at gmail.com> writes:
> ## The depth first algorithm
> dfs (L x)   = [x]
> dfs (B x lst rst) = [x]  ++  dfs lst  ++  dfs rst

Cute.  I can't resist posting the similar breadth first algorithm:

bfs (L x)   = [x]
bfs (B x lst rst) = bfs lst  ++ [x] ++  bfs rst

> *Main> dfs t
> [6,2,1,4,3,5,8,7,9]

*Main> bfs t
[1,2,3,4,5,6,7,8,9]

> The Haskell is bullseye¹ in capturing the essense of a tree because
> conceptually a tree of type t is recursive in the sense that it can contain
> 2 subtrees -- (B x lst rst) -- or its a base case -- L x.

You might like this discussion of a red-black tree implementation whose
datatype makes sure the RB tree invariants are preserved.  The data
definition is kind of verbose, but with more recent GHC versions it can
be made a lot crisper, with datakinds and type-level numeric literals.

https://www.reddit.com/r/haskell/comments/ti5il/redblack_trees_in_haskell_using_gadts_existential/