2

在 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）的方式（也许使用一些高级类型扩展）来制作新类型（用于异构树）？我知道异构列表，也许是同一个问题？

4

1 回答 1

2

对于问题 #2，使用 GADT 和类型类很容易构造一个没有显式标记的“受限”异构类型：

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

对于问题 #1，您可以使用具有新 GADT 的相同类型类：

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 ...
>

这一切都很好，直到您尝试使用您构建的任何值。例如，如果您想编写一个函数来Bool从可能的 boolish中提取 a Thing：

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

你会发现自己被困在这里。如果没有某种“标签”，就无法确定x是 a Bool、Int还是Char。

但实际上，您确实THING有一个可用的隐式标记，即x. 所以，你可以写：

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

然后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

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

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

起初这可能看起来“优雅”，但是如果您在实际代码中尝试这种方法，我认为您会后悔失去Thing在使用站点上对构造函数进行模式匹配的能力（因此必须替换casts 链和/或比较TypeReps)。

于 2019-06-28T16:39:39.083 回答