Haskell monad- and error-handling-style

As an answer to excersise 2.3 in Chris Okasaki's book, Purely Functional Data Structures,


Inserting an existing element into a binary search tree copies the
entire search path even though the copied nodes are indistinguishable
from the originals. Rewrite insert using exceptions to avoid this
copying. Establish one handler per insertion rather than one handler
per iteration.

I've written the following haskell implementations of insertion in a binary heap:

import Data.Maybe

data Tree e = Leaf | T (Tree e) e (Tree e) deriving Show

empty = Leaf

insert x Leaf = T Leaf x Leaf
insert x tree@(T l e r)
  | x == e = tree
  | x >= \t -> case t of
                Leaf   -> Just $ T Leaf x Leaf
                tree@(T l e r)
                  | x == e -> Nothing
                  | x  (ins x (Just l)) >>= \nt -> Just $ T nt e r
                  | ot herwise -> (ins x (Just r)) >>= \nt -> Just $ T l e nt

fastInsert x t =
  fromMaybe t $ ins x $ Just t

The fastInsert function (using ins as a 'helper') and the insert function will return the same tree given the same input, but fastInsert wont copy sub-trees if no insertion is needed (if the tree already contains the node to be inserted).

The question is: how would this look if written more idiomatically, with regard to monadic operations/syntax in ins?

Another question: I'm using monads as a substitute for exceptions as suggested in the book. The point is to avoid rebuilding (reference copying) the tree when returning in the recursive calls. How should I have gone about this?

There are couple of points that I'd suggest:

• Be sure to always include types for top-level functions. Without them, the code becomes very quickly unreadable. For example, would you know what ins does and what is its type, if you didn't write it yourself? In many cases you can immediately judge what a function does just looking at its name and its type.

-
If you do

| x < e  = ...
  | x == y = ...
  | otherwise = ...

you're performing the comparison twice. In most cases this shouldn't be a problem, but if writing

case compare x e of
  LT -> ...
  EQ -> ...
  GT -> ...

will compare only once, and also allows the compiler to do more optimizations.

• This isn't a problem, just a note: Be aware that fastInsert trades speed for lazyiness. If you examine the root of the tree returned by a fastInsert call, the tree must be examined to check if it contains the inserted element or not. Under most circumstances you wouldn't mind that.

• There is no need for ins to take Maybe (Tree e) as the argument, only to apply >>= on it. Most monadic functions take pure arguments and return a monadic one.

• It's often convenient to use functions from Control.Applicative to lift pure functions/values to monadic computations. In particular pure, ` and `. See also Functor, Applicative and Monad.

I wasn't sure what error handling you have in mind, as these operations should never fail.

The updated program:

import Control.Applicative
import Data.Maybe

data Tree e = Leaf | T (Tree e) e (Tree e) deriving Show

empty = Leaf

insert :: (Ord e) => e -> Tree e -> Tree e
insert x Leaf = T Leaf x Leaf
insert x tree@(T l e r) = case compare x e of
  EQ -> tree
  LT -> T (insert x l) e r
  GT -> T l e (insert x r)

ins :: (Ord e) => e -> Tree e -> Maybe (Tree e)
ins x Leaf = return $ T Leaf x Leaf
ins x tree@(T l e r) = case compare x e of
  EQ -> Nothing
  LT -> (\l' -> T l' e r)  ins x l
-- you could also write a point-free version, if you like,
-- which better preserves the order of arguments
--  LT -> T  ins x l  pure e  pure r
  GT -> T l e  ins x r

fastInsert :: (Ord e) => e -> Tree e -> Tree e
fastInsert x t =
  fromMaybe t $ ins x t

StackExchange Code Review Q#64787, answer score: 3