haskell - 型コンストラクターをOrd型を返すように制限するにはどうすればよいですか？

Question

ツリーの次の実装があるとします。

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

children戻り型に制限することは可能Ordですか？

似たようなもの：

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

Answer 1

少なくとも 2 つの方法が考えられます。

1.GADT

たとえば、ここを参照してください。

{-# LANGUAGE GADTs #-}

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

これで、次のことができます。

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

2.スマートコンストラクター

制限された型シグネチャを持つスマート コンストラクターで通常のデータ型を使用できます。

{-# 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

そして、次のことができるようになりました:

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

ただし、注文できないタイプを追加しようとすると、次のようになります。

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) []