Should I avoid constructing in Haskell?

Question

While reading a snipped from Haskell for Great Good I found the following situation:

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
  | x == a = Node x left right  
  | x < a  = Node a (treeInsert x left) right  
  | x > a  = Node a left (treeInsert x right)

Wouldn't it be better for performance if we just reused the given Tree when x == a?

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x all@(Node a left right)   
  | x == a = all  
  | x < a  = Node a (treeInsert x left) right  
  | otherwise  = Node a left (treeInsert x right)

In real life coding, what should I do? Are there any drawbacks when returning the same thing?

Answer 1

Well, if the first case had used a instead of x as follows, then there's at least the chance that GHC would eliminate the allocation of a new node through common subexpression elimination.

treeInsert x (Node a left right)   
  | x == a = Node a left right

However, this is all but irrelevant in any non-trivial use case, because the path down the tree to the node is going to be duplicated even when the element already exists. And this path is going to be significantly longer than a single node unless your use case is trivial.

In the world of ML, the fairly idiomatic way to avoid this is to throw a KeyAlreadyExists exception, and then catch that exception at the top-level insertion function and return the original tree. This would cause the stack to be unwound instead of allocating any of the Nodes on the heap.

A direct implementation of the ML idiom is basically a no-no in Haskell, for good reasons. If avoiding this duplication matters, the simplest and possibly best thing to do is to check if the tree contains the key before you insert it.

The downside of this approach, compared to a direct Haskell insert or the ML idiom, is that it involves two traversals of the path instead of one. Now, here is a non-duplicating, single-pass insert you can implement in Haskell:

treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert x original_tree = result_tree
  where
    (result_tree, new_tree) = loop x original_tree

    loop x EmptyTree = (new_tree, singleton x)
    loop x (Node a left right) =
       case compare x a of
         LT -> let (res, new_left) = loop x left
                in (res, Node a new_left right)
         EQ -> (original_tree, error "unreachable")
         GT -> let (res, new_right) = loop x right
                in (res, Node a left new_right)

However, older versions of GHC (roughly 7-10 years ago) don't handle this sort of recursion through lazy pairs of results very efficiently, and in my experience check-before-insert is likely to perform better. I'd be slightly surprised if this observation has really changed in the context of more recent GHC versions.

One can certainly imagine a function that directly constructs (but does not return) a new path for the tree, and decides to return the new path or the original path once it's known whether the element exists already. (The new path would immediately become garbage if it is not returned.) This conforms to the basic principles of the GHC runtime, but isn't really expressible in the source language.

Of course, any completely non-duplicating insertion function on a lazy data structure is going to have different strictness properties than a simple, duplicating insert. So no matter the implementation technique, they are different functions if laziness matters.

But of course, whether or not the path is duplicated may not matter that much. The cases where it would matter the most would be when you are using the tree persistently, because in linear use cases the old path would become garbage immediately after each insertion. And of course, this only matters when you are inserting a significant number of duplicates.

Answer 2

My two cents... perhaps not even about the original question:

Instead of writing guards with x < a and x == a, I would match compare a b against LT, EQ and GT, e.g.:

treeInsert x all@(Node a left right) =
  case compare x a of
    EQ -> ...
    LT -> ...
    GT -> ...

I would do this especially if x and a can be complex data structures, since a test like x < a could be expensive.

Answer 3

In real life coding, what should I do? Are there any drawbacks when returning the same thing?

a == b does not guarantee that f a == f b for all functions f. So, you may have to return new object even if they compare equal.

In other words, it may not be feasible to change Node x left right to Node a left right or all when a == x regardless of performance gains.

For example you may have types which carry meta data. When you compare them for equality, you may only care about the values and ignore the meta data. But if you replace them just because they compare equal then you will loose the meta data.

newtype ValMeta a b = ValMeta (a, b)  -- value, along with meta data
    deriving (Show)

instance Eq a => Eq (ValMeta a b) where
    -- equality only compares values, ignores meta data
    ValMeta (a, b) == ValMeta (a', b') = a == a'

The point is Eq type-class only says that you may compare values for equality. It does not guarantee anything beyond that.

A real-world example where a == b does not guarantee that f a == f b is when you maintain a Set of unique values within a self-balancing tree. A self-balancing tree (such as Red-Black tree) has some guarantees about the structure of tree but the actual depth and structure depends on the order that the data were added to or removed from the set.

Now when you compare 2 sets for equality, you want to compare that values within the set are equal, not that the underlying trees have the same exact structure. But if you have a function such as depth which exposes the depth of underlying tree maintaining the set then you cannot guarantee that the depths are equal even if the sets compare equal.

Here is a video of great Philip Wadler realizing live and on-stage that many useful relations do not preserve equality (starting at 42min).

Edit: Example from ghc where a == b does not imply f a == f b:

\> import Data.Set
\> let a = fromList [1, 2, 3, 4, 5, 10, 9, 8, 7, 6]
\> let b = fromList [1..10]
\> let f = showTree
\> a == b
True
\> f a == f b
False

Another real-world example is hash-table. Two hash-tables are equal if and only if their key-value pairs tie out. However, the capacity of a hash-table, i.e. the number of keys you may add before having to re-allocate and rehash, depends on the order of inserts/deletes.

So if you have a function which returns the capacity of hash table, it may return different values for hash-tables a and b even though a == b.

Answer 4

Let's look at the core! (Without optimisations here)

$ ghc-7.8.2 -ddump-simpl wtmpf-file13495.hs

The relevant difference is that the first version (without all@(...)) has

                case GHC.Classes.> @ a_aUH $dOrd_aUV eta_B2 a1_aBQ
                of _ [Occ=Dead] {
                  GHC.Types.False ->
                    Control.Exception.Base.patError
                      @ (TreeInsert.Tree a_aUH)
                      "wtmpf-file13495.hs:(9,1)-(13,45)|function treeInsert"#;
                  GHC.Types.True ->
                    TreeInsert.Node
                      @ a_aUH
                      a1_aBQ
                      left_aBR
                      (TreeInsert.treeInsert @ a_aUH $dOrd_aUV eta_B2 right_aBS)

where reusing the node with that as-pattern does just

                TreeInsert.Node
                  @ a_aUI
                  a1_aBR
                  left_aBS
                  (TreeInsert.treeInsert @ a_aUI $dOrd_aUW eta_B2 right_aBT);

This is an avoided check that may well make a significant performance difference.

However, this difference has actually nothing to do with the as-pattern. It's just because your first snippet uses a x > a guard, which is not trivial. The second uses otherwise, which is optimised away.

If you change the first snippet to

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
  | x == a     = Node x left right  
  | x < a      = Node a (treeInsert x left) right  
  | otherwise  = Node a left (treeInsert x right)

then the difference boils down to

      GHC.Types.True -> TreeInsert.Node @ a_aUH a1_aBQ left_aBR right_aBS

vs

      GHC.Types.True -> wild_Xa

Which is indeed just the difference of Node x left right vs all.

...without optimisations, that is. The versions diverge further when I turn on -O2. But I can't really make out how the performance would differ, there.

Answer 5

answer seems to be wrong. I just leave it here, for reference...

---

With your second function you avoid creating a new node, because the compiler cannot really understand equality (== is just some function.) If you change the first version to

-- version C
treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
  | x == a = Node a left right  -- Difference here! Changed x to a.
  | x < a  = Node a (treeInsert x left) right  
  | x > a  = Node a left (treeInsert x right)

the compiler will probably be able to do common subexpression elimination, because the optimizer will be able to see that Node a left right is the same as Node a left right.

On the other hand, I doubt that the compiler can deduce from a == x that Node a left right is the same as Node x left right.

So, I'm pretty sure that under -O2, version B and version C are the same, but version A is probably slower because it does an extra instantiation in the a == x case.