具有新数据的类型的限制集，例如“Tree a”

Question

探索和研究 Haskell 中的类型系统我发现了一些问题。

1) 让我们将多态类型视为二叉树：

 data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show

并且，例如，我想限制我对 Tree Int、Tree Bool 和 Tree Char 的考虑。当然，我可以做一个这样的新类型：

data TreeIWant = T1 (Tree Int) | T2 (Tree Bool) | T3 (Tree Char) deriving Show

但是是否有可能以更优雅的方式（并且没有像 T1、T2、T3 这样的新标签）制作新的受限类型（对于同质树）（也许一些高级类型扩展）？

2) 第二个问题是关于具有异质值的树。我可以用通常的 Haskell 来做它们，即我可以做新的帮助类型，包含标记的异构值：

data HeteroValues = H1 Int | H2 Bool | H3 Char deriving Show

然后用这种类型的值创建树：

type TreeH = Tree HeteroValues

但是有没有可能以更优雅的方式（并且没有像 H1、H2、H3 这样的新标签）（也许有一些高级类型扩展）？我知道，也许是同一个问题？

Answer 1

对于问题 #2，使用 GADT 和类型 class:

很容易构造一个没有显式标签的 "restricted" 异构类型

{-# LANGUAGE GADTs #-}
data Thing where
  T :: THING a => a -> Thing
class THING a

现在，为您要允许的内容声明 THING 个实例：

instance THING Int
instance THING Bool
instance THING Char

并且您可以创建 Things 和 Things 的列表（或树）：

> t1 = T 'a'       -- Char is okay
> t2 = T "hello"   -- but String is not
... type error ...
> tl = [T (42 :: Int), T True, T 'x']
> tt = Branch (Leaf (T 'x')) (Leaf (T False))
>

就您问题中的类型名称而言，您有：

type HeteroValues = Thing
type TreeH = Tree Thing

您可以将相同类型 class 与新的 GADT 一起用于问题 #1：

data ThingTree where
  TT :: THING a => Tree a -> ThingTree

你有：

type TreeIWant = ThingTree

你可以这样做：

> tt1 = TT $ Branch (Leaf 'x') (Leaf 'y')
> tt2 = TT $ Branch (Leaf 'x') (Leaf False)
... type error ...
>

一切都很好，直到您尝试使用您构建的任何值。例如，如果您想编写一个函数来从可能是布尔值的 Thing:

中提取 Bool

maybeBool :: Thing -> Maybe Bool
maybeBool (T x) = ...

你会发现自己被困在这里。如果没有某种 "tag"，就无法确定 x 是 Bool、Int 还是 Char.

实际上，您有一个可用的隐式标记，即 x 的 THING 类型 class 字典。所以，你可以这样写：

maybeBool :: Thing -> Maybe Bool
maybeBool (T x) = maybeBool' x

然后在你的类型 class:

中实现 maybeBool'

class THING a where
  maybeBool' :: a -> Maybe Bool
instance THING Int where
  maybeBool' _ = Nothing
instance THING Bool where
  maybeBool' = Just
instance THING Char where
  maybeBool' _ = Nothing

你是金色的！

当然，如果您使用了显式标签：

data Thing = T_Int Int | T_Bool Bool | T_Char Char

那么你可以跳过类型 class 并写成：

maybeBool :: Thing -> Maybe Bool
maybeBool (T_Bool x) = Just x
maybeBool _ = Nothing

最后发现，三种代数和最好的Haskell表示就是三种代数和：

data Thing = T_Int Int | T_Bool Bool | T_Char Char

试图避免对显式标签的需要可能会导致其他地方出现许多不雅的样板文件。

更新： 正如@DanielWagner 在评论中指出的那样，您可以使用 Data.Typeable 代替此样板文件（实际上，让 GHC 为生成大量样板文件你），所以你可以写：

import Data.Typeable

data Thing where
  T :: THING a => a -> Thing
class Typeable a => THING a

instance THING Int
instance THING Bool
instance THING Char

maybeBool :: Thing -> Maybe Bool
maybeBool = cast

乍一看这似乎 "elegant"，但如果您在实际代码中尝试这种方法，我想您会后悔失去在使用站点 Thing 构造函数上进行模式匹配的能力（以及因此必须替换 cast 的链 and/or 与 TypeRep 的比较）。

具有新数据的类型的限制集，例如“Tree a”

The limit set of types with new data like `Tree a`

haskell

type-systems

gadt

data-kinds

phantom-types