PureScript by Example - Tree Traversal question

Help
#1

Hi, I’m educating myself and having fun learning about PureScript by reading PureScript by Example.

In the Applicative Validation chapter there’s an exercise to [w]rite a Traversable instance for the following binary tree data structure […] which I did for this structure

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

by creating a Traversable instance for this algebraic type. It worked, yay!

The book mentions that [t]his corresponds to an in-order traversal of the tree. I had a tough time figuring out that to create a tree which can be traversed differently (using traverse) I would need to create a different algeraic structure where I shuffle the order of the position of the left and right subtree and the node’s value in the structures definition.

My question: how would one traverse the above mentioned structure (left subtree, node value, right subtree) in a preorder or any other way (sensibly)?

#2

You don’t actually have to create different algebraic structure to traverse the tree differently.
You can just reuse one and implement different traverse-like functions which will only differ in the order in which effects are evaluated.

module Main where

import Prelude

import Effect (Effect)
import Effect.Console (logShow)

main :: Effect Unit
main = do
  -- t1, t2 and t3 will be identical, but the order of effects (printing values at nodes) will be different
  t1 <- traverseInOrder logShow sampleTree -- 1 2 3
  t2 <- traversePreOrder logShow sampleTree -- 2 1 3
  t3 <- traversePostOrder logShow sampleTree -- 1 3 2  
  pure unit

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

sampleTree :: Tree Int
sampleTree = Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)

traverseInOrder :: forall f a b . Applicative f => (a -> f b) -> Tree a -> f (Tree b)
traverseInOrder _ Leaf = pure Leaf
-- first evaluate left branch, then node, then right branch
traverseInOrder f (Branch l x r) = Branch <$> traverseInOrder f l <*> f x <*> traverseInOrder f r

traversePreOrder :: forall f a b . Applicative f => (a -> f b) -> Tree a -> f (Tree b)
traversePreOrder _ Leaf = pure Leaf
-- first evaluate node, then left branch and then right branch. Notice the lambda function shuffles the arguments where they need to be
traversePreOrder f (Branch l x r) = (\x' l' r' -> Branch l' x' r') <$> f x <*> traversePreOrder f l <*> traversePreOrder f r

traversePostOrder :: forall f a b . Applicative f => (a -> f b) -> Tree a -> f (Tree b)
traversePostOrder _ Leaf = pure Leaf
traversePostOrder f (Branch l x r) = (\l' r' x' -> Branch l' x' r') <$> traversePostOrder f l <*> traversePostOrder f r <*> f x

Not sure If I’m answering your question though :slight_smile:

4 Likes
#3

Ah! I would have never thought about using a lambda to wrap the Branch type constructor to shuffle the arguments in order to force a different eval order. Very nifty trick :slight_smile: Thanks for the clarification and you indeed answer my question! :slight_smile: