haskellbinary-tree

Is there any concrete reason to prefer `Node a (Tree a) (Tree a)` over `Node (Tree a) a (Tree a)`?


Consider the following two binary tree definitions:

data Tree a = Empty | Node a (Tree a) (Tree a)
data Tree a = Empty | Node (Tree a) a (Tree a)

I know this is a bit of a trivial question, but I am wondering if there is any concrete reason to prefer one parameter order over the other.

When we move from imperative languages to functional languages, we learn that parameter order suddenly matters quite a lot because of currying. Similarly, when we move from a functional language to a dependently-typed language, we learn that the order in which we introduce definitions in a file suddenly matters quite a lot, because of totality/termination checking.

In Haskell it's often a stylistic choice whether top-level/entrypoint functions go at the top or bottom of the file, but in e.g. Agda, there is only one choice. Helper functions must be defined first, and top-level stuff goes at the bottom. So in fact there is a natural choice.

Is there a natural choice here, for any good reason?


Solution

  • It does not really matter.

    There are no typing-related reasons to prefer either.

    There are no performance-related reasons I can see.

    Partial application of Node could be a reason, but I believe that to be very rare for Node.

    Another potential reason to prefer either: automatically derived instances. Especially deriving Ord, which will order trees differently. (Still, comparing trees is not terribly common, in my experience.) Further, deriving (Foldable, Traversable) will provide different folds and traverses.

    Other things being equal, my personal preference is

    data Tree a = Empty | Node (Tree a) a (Tree a)
    

    because the tree could be a binary search tree (BST), and in such case I believe that having Node left x right helps remembering that values in left are smaller than x which is smaller than values in right.