Nice! Here is my code for comparison.

[nomeata]

A year ago, when I gave the talk the first time, I also investigated this. This was my code, just for comparison:

import Criterion.Main

import Tree

tree :: Int -> Int -> T Int
tree x 0 = L
tree x n = N (tree x (n-1)) (x + 2^(n-1) - 1) (tree (x + 2^(n-1)) (n-1))

main = defaultMain
   [ bench ("isOrdered" ++ show n) (whnf f t)
   | (n,f) <- zip [0..] allFuns
   ]
  where
    t = tree 0 10

allFuns :: Ord a => [T a -> Bool]
allFuns = [
  isOrdered0,
  isOrdered1,
  isOrdered2,
  isOrdered3,
  isOrdered4,
  isOrdered5,
  isOrdered6,
  isOrdered7,
  isOrdered8,
  isOrdered9,
  isOrdered10,
  isOrdered11,
  isOrdered12,
  isOrdered13,
  isOrdered14,
  isOrdered15,
  isOrdered16,
  isOrdered17,
  isOrdered18,
  isOrdered19
  ]

The HTML report looks better than the text output :-)

[noughtmare]

Cool! I know I should have used a list of functions like a real functional programmer :). Was the left-to-right approach also the fastest in your benchmarks? I did discover that the 'top-down' approach can be specialized and optimized for the case of Int, then it becomes faster than the left-to-right approach. See:

https://github.com/noughtmare/breitnerbench/blob/ab9a27776ae8e2f092f040d862ba0bcfdf231ab4/Main.hs#L87-L114

I'm going to add a HTML report now.

[nomeata]

The fastest one for me were isOrdered10 and isOrdered16 and isOrdered18, but in the ordering of the extended version (see https://gist.github.com/nomeata/3f61dc16cfed360c3df51eab1892e0a5). These are

• top-down with Maybe unboxed by specialization
• bottom-up with one layer of Maybe removed by handling L separately
• left-to-right with difference lists

[noughtmare]

Interesting. I just ran your code and there are some differences on my machine:

Did you use GHC 8.10.1 and the -O2 option?

Most notably: 9 and 10 take the same time, 3-6 all take the same time, 0 and 1-7 take significantly more time and 9 and 11-13 and 17 take significantly less time on my machine.

Also, do you know why 0 is so fast?

[nomeata]

Looks similar enough to me, given the black art that is performance measurement :)

I ran these last year, and it seems using 8.4.4. (judging from running string on the binary from then)

But it might be ConstSpec become more aggressive since 8.4.4, turning isOrdered9 into isOrdered10. I vaguely remembering that be the case if I tweaked the flags back then.

Also, do you know why 0 is so fast?

Because it’s wrong :-) (The full version of the talk starts with type-driving development producing a version that’s buggy – but fast!)