Lazy search tree construction

We counted the number of reductions required for

• calculating the length of a list of length n,
• generating a search tree from a list of length n + a member query for the integer 500000, and
• generating a search tree + calculate the size of the tree (which forces the whole tree to be constructed).

Source code: search_tree.hs.

The resulting graph is values from the experiments are contained in the figure below. In the second figure we have plotted the values divided by n. The red curve can be approximated by the function 80n+32nlog n, which matches the expected O(nlog n) time for building a search tree.

Results of experiments