How to restrict type constructor to returning Ord types?

Question

Suppose I have this implementation of a tree:

data Tree a children = EmptyTree | Tree a (children (Tree a children))

Is it possible to restrict children to returning Ord types?

Something akin to:

data (Ord children *) => Tree a children = EmptyTree | Tree a (children (Tree a children))

Answer 1

I can think of at least two ways:

1. GADTs

Eg see here.

{-# LANGUAGE GADTs #-}

data Tree a children where
    Empty :: Tree a children
    Tree :: Ord (children a) => a -> children (Tree a children) -> Tree a children

Now you can do:

ghci> let t = Tree 1 [Tree 2 [], Empty]
ghci> :t t
t :: Tree Integer []

2. Smart constructors

You could use a regular data type with smart constructors that have a restricted type signature:

{-# LANGUAGE FlexibleContexts #-}

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

empty :: Tree a children
empty = Empty

tree :: Ord (children a) => a -> children (Tree a children) -> Tree a children
tree val rest = Tree val rest

and you can now do:

ghci> let t = tree 1 [tree 2 [], empty]
ghci> :t t
t :: Tree Integer []

but if you try to add a type which isn't orderable:

ghci> let t = tree (+1) []
<interactive>:69:9:
    No instance for (Ord (a0 -> a0))
      arising from a use of `tree'
    Possible fix: add an instance declaration for (Ord (a0 -> a0))
    In the expression: tree (+ 1) []
    In an equation for `t': t = tree (+ 1) []