Haskell - Binary Search Tree

Question

Being a beginner in Haskell I am currently trying to get my head around BST. Currently I am trying to perform a fold on a tree inorder.

This is what I got so far, but it produces an error.

inorder' :: (b -> a -> b) -> b -> BinaryTree a -> b
inorder' _ a myTree = a
inorder' fun a (Node left root right) = inorder' fun (fun root (inorder' fun a left)) right

I am really dumbfounded now because I worked for quite some time now to figure out what exactly the problem is but I simply do not seem to come up with a solution.

Furthermore please include the definition of BinaryTree a. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jun 19, 2017 at 15:29

willeM_ Van Onsem · Accepted Answer · 2017-06-19 21:53:17Z

3

Inorder means that you (1) first process the left subtree, (2) then process the node itself, and (3) finally process the right subtree.

Leaves without values

Based on your function, the definition of BinaryTree a, is probably:

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

So that means that there are two cases: in case of a leaf, there is no data, so we simply return the given value:

inorder' _ a Leaf = a -- with an uppercase, otherwise it does match all

And for the Node case, we above already stated how that works:

inorder' f a (Node left val right) = inorder' f c right
    where b = inorder' f a left
          c = f b val

Or in full:

inorder' :: (b -> a -> b) -> b -> BinaryTree a -> b
inorder' _ a Leaf = a
inorder' f a (Node left val right) = inorder' f c right
    where b = inorder' f a left
          c = f b val

Leaves with values

In that case the BinaryTree is defined like:

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

In case the leaves have a value, we simply need to fix the first clause:

inorder' :: (b -> a -> b) -> b -> BinaryTree a -> b
inorder' f b (Leaf a) = f b a
inorder' f a (Node left val right) = inorder' f c right
    where b = inorder' f a left
          c = f b val

edited Jun 19, 2017 at 21:53

answered Jun 19, 2017 at 15:33

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

amalloy Over a year ago

myTree is a pattern that matches anything, not a constructor.

willeM_ Van Onsem Over a year ago

@amalloy: yeah, somehow i did not notice the lowercase, thanks.

Collectives™ on Stack Overflow

Haskell - Binary Search Tree

1 Answer 1

Leaves without values

Leaves with values

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Leaves without values

Leaves with values

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related