Leftmost value in a tree (Haskell)

Question

How do I find the leftmost value in a tree? Leftmost is the value that is reached by going to the left child of the current Node for as long as possible.

The tree type is defined as:

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

I currently have the following:

leftest :: Tree a -> Maybe a
leftest (Leaf) = Nothing

Examples of what leftest should return:

leftest (Node 1 (Node 2 (Node 3 Leaf Leaf) Leaf) Leaf) --> Just 3

leftest (Node 1 (Node 2 Leaf (Node 3 Leaf Leaf)) (Node 4 Leaf Leaf)) --> Just 2

Let us forget about Haskell for a minute. How would you define yourself - in words - a way to find the leftmost value? — Willem Van Onsem
Check if the current Node has a left child. If yes, then go to that child. If not, then the current Node is the leftmost. — Aelin
good, can you now transfer that into an inductive definition? — Willem Van Onsem

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2018-04-12T20:41:01

Well before you write a function in Haskell, it is better to first think about an (inductive) definition about the leftmost element in the tree.

You actually already wrote one part of it:

leftest (Leaf) = Nothing

Here you basically state: "A leaf has no leftmost element". So now the question is, what is the leftmost value of a Tree a (Tree a) (Tree a)?

We can reason about several cases here. There are basically four cases here: the two subtrees can be Leafs or Tree ...s, for each of these cases, we can try to come up with a solution:

Tree x Leaf Leaf, here we thus have a node without any childs (in fact in most books on data structures, that is a leaf), in that case the leftmost value is the one that is carried by the Tree x Leaf Leaf, so x, so we can return Just x;
Tree x Leaf (Tree _ _ _), here we have a tree, with only a child on the right. Since that child, and all its descendants are on the right, we thus can again return the element of the node, so Just x;
Tree x (Tree _ _ _) Leaf, here we have only a child on the left. In that case the leftmost of this tree, is the same as the leftmost of the left child, so we recurse on the left child; and
Tree x (Tree _ _ _) (Tree _ _ _), here the node has two children, but like we already argued, the right child is of no importance, we can again recurse on the left child.

So we can write these as:

leftmost :: Tree a -> Maybe a
leftmost Leaf = Nothing
leftmost (Tree x Leaf Leaf) = Just x  -- (1)
leftmost (Tree x Leaf (Tree _ _ _)) = Just x  -- (2)
leftmost (Tree x c@(Tree _ _ _) Leaf) = leftmost c  -- (3)
leftmost (Tree x c@(Tree _ _ _) (Tree _ _ _)) = leftmost c  -- (4)

This actually works, but is rather verbose: since the right child is of no importance, why would we consider four cases? We can limit this to two cases:

leftmost :: Tree a -> Maybe a
leftmost Leaf = Nothing
leftmost (Tree x Leaf _) = Just x  -- (1+2)
leftmost (Tree x c@(Tree _ _ _) _) = leftmost c  -- (3+4)

Leftmost value in a tree (Haskell)

1 Answers