[Haskell-cafe] SmallCheck Depth

Richard A. O'Keefe ok at cs.otago.ac.nz
Wed Feb 11 01:24:16 UTC 2015

On 6/02/2015, at 7:29 am, Roman Cheplyaka <roma at ro-che.info> wrote:
>> "Test.SmallCheck.Series" still states
>> that "For data values, [depth] is the depth of nested constructor
>> applications."
> True is a single constructor, so its depth is 1.
> Just True is a constructor application of depth 2.

Arguably, while True *is* a constructor, it is not a *nested* constructor.
To me it obviously isn't, while to you it obviously is.
This kind of problem with natural language is why we need more
formal specifications.

In the same way, to me (Just True) *obviously* has depth (actually height) 1.
It is the tree
     |  Just  |
     |  True  |
in which the longest path from the root to a leaf contains 1 edge.
Where is the second edge?

For example, http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html says
  - The depth of a node is the number of edges from the root to the node.
  - The height of a node is the number of edges from the node to the deepest leaf.
  - The height of a tree is [the] height of the root.
These are essentially the same definitions found in http://en.wikipedia.org/wiki/Tree_(data_structure)

So we don't just have a potential ambiguity (what is "nested"?) but an actual
clash with standard terminology; you are defining

  depth tree = height tree + 1

More information about the Haskell-Cafe mailing list