How to define a binary tree in Haskell?

Question

In Haskell, a binary tree can be defined in one of two ways:

data Tree a = Empty | Branch a (Tree a) (Tree a)

or

data Tree a = Leaf a | Branch (Tree a) (Tree a)

What are the advantages of choosing one of them? In what situations is one tree structure best suited to each other?

Answer 1

It pretty much depends on your application. The first definition is better if the shape of the tree is determined by elements, for example, if you have a balanced binary tree:

On the other hand, if your tree acts as a container for unlimited elements, where the shape of the tree does not depend on them, it makes sense to put values ​​in the leaves.

Heinrich Apfelmus .

data Tree v a = Leaf   v a
              | Branch v (Tree v a) (Tree v a)

a , ( , ) v, v, .

Answer 2

PetrPudlák, . . , () , :

instance Monad Tree where
    return = Leaf
    Leaf x >>= f = f x
    Branch t1 t2 >>= f = Branch (t1 >>= f) (t2 >>= f)

(>>=) " ".

Functor Applicative . GHC 7.10 Monad. :

instance Functor Tree where fmap = Control.Monad.liftM
instance Applicative Tree where pure = return; (<*>) = Control.Monad.ap

Answer 3

, , . , :

• .

• node, , ( ).

Answer 4

, , () , . , ; , . , O (log n), .

If anyone finds a precedent for such a data structure, let me know.