haskell - 一种将 Haskell 的 Either 类型推广到任意多种类型的方法？

Question

我正在创建一个回合制游戏。我想定义一个数据类型，从许多可能的类型中编码一种类型。这是一个激励的例子:
我定义了一个 Turn type 使用 GADT，所以 Turn a 的每个值的类型说明了它的值(value)。

data Travel
data Attack
data Flee
data Quit

data Turn a where
   Travel :: Location -> Turn Travel
   Attack :: Int -> Turn Attack
   Flee :: Turn Flee
   Quit :: Turn Quit

现在我可以编写这样的类型 decideTravel :: GameState -> Turn Travel ，非常有表​​现力和漂亮。
当我想返回多种可能的转弯类型之一时，就会出现问题。我想编写类似于以下的函数:

-- OneOf taking two types
decideFightingTurn :: GameState -> OneOf (Turn Attack) (Turn Flee)
-- OneOf takes three types
decideTurn :: GameState -> OneOf (Turn Attack) (Turn Travel) (Turn Quit)

这个 OneOf数据类型带有“多种可能类型中的一种”的概念。问题在于定义此数据类型，我需要以某种方式在类型级别处理类型列表。
到目前为止，我有两个低于标准的解决方案:
解决方案 1:创建包装总和类型
只需为每个 Turn a 创建一个具有构造函数的新类型构造函数:

data AnyTurn
   = TravelTurn (Turn Travel)
   | TravelAttack (Turn Attack)
   | TravelFlee (Turn Flee)
   | TravelQuit (Turn Quit)

这并没有以我想要的方式帮助我。现在我必须对 AnyTurn 的所有情况进行模式匹配并考虑无效的输入类型。此外，类型级别信息被 AnyTurn 所掩盖。类型，因为它无法指示在类型级别上哪些特定的转弯实际上是可能的。
解决方案 2:为不同数量的类型创建“Either”类型
该解决方案在类型级别为我提供了我想要的东西，但使用起来很麻烦。基本上创建一个 Either -like 任意数量组合的类型，如下所示:

data OneOf2 a b
   = OneOf2A a
   | OneOf2B b

data OneOf3 a b c
   = OneOf3A a
   | OneOf3B b
   | OneOf3C c

-- etc, for as many as are needed.

这在类型级别传达了我想要的内容，因此我现在可以将前面的示例编写为:

decideFightingTurn :: GameState -> OneOf2 (Turn Travel) (Turn Flee)
decideTurn :: GameState -> OneOf3 (Turn Attack) (Turn Travel) (Turn Quit)

这行得通，但是最好用一种类型来表达它 OneOf .有什么办法可以写出广义的 OneOf输入Haskell？

Answer 1

我猜是这样的:

data OneOf as where
    ThisOne :: a -> OneOf (a : as)
    Later :: OneOf as -> OneOf (a : as)

然后你可以写，例如:

decideFightingTurn :: GameState -> OneOf [Turn Travel, Turn Flee]

您可能还想:

type family Map f xs where
    Map f '[] = '[]
    Map f (x:xs) = f x : Map f xs

这样，您可以编写如下内容:

decideFightingTurn :: GameState -> OneOf (Map Turn [Travel, Flee])

或者您可以构建 Map如果您认为自己会一直这样做，请进入 GADT:

data OneOfF f as where
    ThisOneF :: f a -> OneOfF f (a : as)
    LaterF :: OneOfF f as -> OneOfF f (a : as)

接着:

decideFightingTurn :: GameState -> OneOfF Turn [Travel, Flee]

如果这成为一个问题，可以做各种事情来提高效率；我尝试的第一件事是使用二进制索引而不是一元索引，如此处所示。