Rustom Mody <rustompm...@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/ -- https://mail.python.org/mailman/listinfo/python-list
