BST: how to define `insert` in terms of catamorphic fold?

Question

I have a typical binary search tree data type:

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

and a catamorphism

foldt :: b -> (a -> b -> b -> b) -> Tree a -> b
foldt empty _ Empty = empty
foldt empty branch (Branch a l r) = branch a (foldt empty branch l) (foldt empty branch r)

I tried to define an insert function using foldt and got some interesting results:

insert :: (Ord a) => a -> Tree a -> Tree a
insert x = foldt (single x) insertb
  where insertb a left right
          | x == a = Branch x left right
          | x < a = Branch a (insert x left) right
          | x > a = Branch a left (insert x right)

ghci> mytree = insert 2 (Branch 3 Empty Empty)  
ghci> mytree
Branch 3 (Branch 2 (Branch 2 Empty Empty) (Branch 2 Empty Empty)) (Branch 2 Empty Empty)
ghci> 

Of course, a traditional insert method behaves as expected:

insert' :: (Ord a) => a -> Tree a -> Tree a
insert' x Empty = single x
insert' x (Branch a left right)
  | x == a = Branch x left right
  | x < a = Branch a (insert' x left) right
  | x > a = Branch a left (insert' x right)

ghci> mytree2 = insert' 2 (Branch 3 Empty Empty)
ghci> mytree2
Branch 3 (Branch 2 Empty Empty) Empty
ghci>

Is there a way to define insert in terms of foldt, or am I barking up the wrong tree (ha) here?

Answer 1

Let's define a function

insertMaybe :: Ord a => Tree a -> Maybe a -> Tree a

This function takes a tree, and maybe an element. In the Just case, the element is inserted. In the Nothing case, the tree is returned unchanged. So then we can define

insert a t = insertMaybe t (Just a)

Now:

insertMaybe :: Ord a => Tree a -> Maybe a -> Tree a
insertMaybe = foldt leaf branch
  where
    leaf (Just new) = ?
    leaf Nothing = ?

    branch a l r Nothing = ?
    branch a l r (Just new)
      | ... = ?
      ...

---

Alternatively:

data Ins a = Ins
  { inserted :: Tree a
  , notInserted :: Tree a }

insert a t = inserted (insertAndNot a t)

-- Return the tree with the 
-- element inserted, and also unchanged.
insertAndNot :: Ord a => a -> Tree a -> Ins a
insertAndNot new = foldt leaf branch
  where
    leaf = Ins ? ?
    branch a ~(Ins li lni) ~(Ins ri rni)
      | ... = Ins ? ?
      ...

Paramorphism

The above solutions have a major efficiency problem: they completely rebuild the tree structure just to insert an element. As amalloy suggested, we can fix that by replacing foldt (a catamorphism) by parat (a paramorphism). parat gives the branch function access to both the recursively modified and the unmodified subtrees.

parat :: b -> (a -> (Tree a, b) -> (Tree a, b) -> b) -> Tree a -> b
parat leaf _branch Empty = leaf
parat leaf branch (Branch a l r) =
  branch a
         (l, parat leaf branch l)
         (r, parat leaf branch r)

Conveniently, it's also slightly easier to define insert using parat. Can you see how? This ends up being an efficient version of the "alternative" way I suggested for using foldt.

Answer 2

Thanks to dfeuer and amalloy for the tips on paramorphisms, TIL!

Given a paramorphism for the Tree data type:

parat :: b -> (a -> (Tree a, b) -> (Tree a, b) -> b) -> Tree a -> b
parat empty _ Empty = empty
parat empty branch (Branch a l r) =
  branch a
         (l, parat leaf branch l)
         (r, parat leaf branch r)

we can write an insert function as:

insert :: Ord a => a -> Tree a -> Tree a
insert x = parat (single x) branch
  where branch a (l, l') (r, r')
          | x == a = Branch x l r
          | x < a = Branch a l' r
          | x > a = Branch a l r'

ghci> mytree = insert 2 (Branch 3 Empty Empty)
ghci> mytree
Branch 3 (Branch 2 Empty Empty) Empty
ghci>

testing a bigger tree...

import Data.Function

mytree :: Tree Integer
mytree = (Branch 3 Empty Empty) & insert 2 & insert 4 & insert 6 & insert 5 & insert 10

inorder :: Tree a -> [a]
inorder = foldt [] (\a l r -> l ++ [a] ++ r)

ghci> mytree
Branch 3 (Branch 2 Empty Empty) (Branch 4 Empty (Branch 6 (Branch 5 Empty Empty) (Branch 10 Empty Empty)))
ghci> inorder mytree
[2,3,4,5,6,10]
ghci>