CODEWITHSUNDEEP
haskellbinary-tree
m0meni
m0meni

Reputation: 16435

Postorder traversal of binary tree using flipped : operator. Right hand side evaluated before left?

Given the binary tree

data BinaryTree a =
    Leaf
  | Node (BinaryTree a) a (BinaryTree a)
  deriving (Show)

My solutions to preorder/inorder were done using :

preorder :: BinaryTree a -> [a]
preorder Leaf = []
preorder (Node left x right) = x : preorder left ++ preorder right

inorder :: BinaryTree a -> [a]
inorder Leaf = []
inorder (Node left x right) = inorder left ++ (x : inorder right)

But for postorder, this didn't work:

postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder (Node left x right) = (postorder left ++ postorder right) : x

and rightfully so because I figured out the type signature was

(:) :: a -> [a] -> [a]

I thought I could solve this by doing:

append :: [a] -> a -> [a]
append = flip (:)

postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder (Node left x right) = (postorder left ++ postorder right) `append` x

But it ended up giving me the same answer as preorder. I'm confused because I assumed that the left hand side would be evaluated before the right hand side.

I assumed this because I know postorder can also be solved like this (not a fan of this method since it means making x a list for no reason but to append):

postorder (Node left x right) = postorder left ++ postorder right ++ [x]

Can someone please tell me where I went wrong, and perhaps why the postorder has the same results of the preorder?

Upvotes: 1

Views: 124

Answers (1)

sclv
sclv

Reputation: 38893

Let's use equational reasoning to see where your postorder with append fails.

append = flip (:)

(postorder left ++ postorder right) `append` x
-- bring append to front
append (postorder left ++ postorder right)  x
-- substitute append
flip (:) (postorder left ++ postorder right) x
-- expand flip
(\f x y -> f y x) (:) (postorder left ++ postorder right) x
-- partially apply expanded flip
(\x y -> y : x) (postorder left ++ postorder right) x
-- finish application
x : (postorder left ++ postorder right)

Now, since we know that in general (x : y) ++ z === x : (y ++ z) we can see that your "postorder" method is actually equivalent to your preorder method!

The error you made was in trying to think about order of evaluation, and reason with ideas like "the left hand side would be evaluated before the right hand side". As you can see from this equational approach, order of evaluation may by and large be ignored in a pure lazy functional setting. What matters are is just following through substitution and simplification of the functions themselves.

If you don't like putting x in a list just to append it, here's an exercise, write a function

consEnd :: [a] -> a -> [a]

that inserts something on to the end of a list directly.

Upvotes: 2

Related Questions