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

我至少可以想到两种方法：

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