我可以禁止一个特定的数据构造函数在另一个内部，同时两者都提供相同的类型吗？

Question

我想在 Haskell 中创建一个允许

的类型 T

[Leaf 1, Rooted (Leaf 2), Branch (Leaf 3) (Branch (Leaf 4) (Leaf 5))]

但不是

[Leaf 1, Rooted (Leaf 2), Branch (Rooted (Leaf 3)) (Branch (Leaf 4) (Leaf 5))]

即。 T 除了 Rooted 的所有构造函数都可以出现在 Branch 的第一个或第二个参数中（完整代码还有几个构造函数）。

我试过

{-# LANGUAGE GADTs #-}
data T (x::Bool) where
  Leaf :: Int -> T True
  Rooted :: T True -> T False
  Branch :: T True -> T True -> T True

这确保我们不能做 Branch (Rooted …) … 但也意味着我们不能做 [Rooted …, One …] 因为那将是一个不同类型的列表 ([T True, T False]).

我研究了 DataKinds，希望我能做到

{-# LANGUAGE GADTs, DataKinds, KindSignatures #-}
data T where
  Leaf :: Int -> T
  Rooted :: T -> T
  Branch :: UnRooted a => a -> a -> T
class UnRooted a
instance UnRooted Leaf
instance UnRooted Branch

但是 ghc (7.10.3) 给出 Data constructor ‘Leaf’ comes from an un-promotable type ‘T’.

在 Haskell 中有没有办法做到这一点？

Answer 1

如果将所有内容包装在隐藏布尔值的构造函数中，则可以使用第一种解决方案：

{-# LANGUAGE GADTs, DataKinds, KindSignatures, RankNTypes #-}
data T (x::Bool) where
  Leaf :: Int -> T True
  Rooted :: T True -> T False
  Branch :: T True -> T True -> T True

data TWrap = forall (x :: Bool). TWrap (T x)

[TWrap $ Leaf 1, TWrap $ Rooted (Leaf 2), TWrap $ Branch (Leaf 3) (Branch (Leaf 4) (Leaf 5))]

但是，如果无论如何我们都必须包装类型，最好还是采用更直接的拆分类型的解决方案：

data T = Leaf Int | Branch T T
data TWrap = Unrooted T | Rooted T

[Unrooted $ Leaf 1, Rooted $ Leaf 2, Unrooted $ Branch (Leaf 3) (Branch (Leaf 4) (Leaf 5))]

你要的基本上就是dependent types, which Haskell doesn't have (yet).

我可以禁止一个特定的数据构造函数在另一个内部，同时两者都提供相同的类型吗？

Can I disallow one particular data constructor inside another, while both give the same type?

haskell

types

gadt

data-kinds