一种将 Haskell 的 Either 类型概括为任意多种类型的方法？

Question

我正在制作一款回合制游戏。我想定义一种数据类型，它对多种可能类型中的一种类型进行编码。这是激励人心的例子：

我已经使用 GADT 定义了一个 Turn 类型，因此 Turn a 的每个值的类型说明了它的值。

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，非常有表现力和漂亮。

当我想 return 多种可能的转弯类型之一时，问题就出现了。我想写类似下面的函数：

-- 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 的类型，如下所示：

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。有什么方法可以在 Haskell 中编写通用的 OneOf 类型？

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]

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

Answer 2

有一个名为 row-types that might give you what you want. Specifically, it provides an extensible variant 的 Haskell 库，有点像 Either，但带有任意多个选项。

在你的情况下，你可以创建你的类型：

import Data.Row

decideFightingTurn :: GameState -> Var ("travel" .== Turn Travel .+ "flee" .== Turn Flee)
decideTurn :: GameState -> Var ("attack" .== Turn Attack .+ "travel" .== Turn Travel .+ "quit" .== Turn Quit)

使用变体的最简单方法是打开 OverloadedLabels。然后，要创建一个，您可以这样写：

decideFightingTurn gs = case gs of
  Foo -> IsJust #travel $ Travel loc
  Bar -> IsJust #flee Flee

可以通过几种不同的方式进行解构。如果你只想检查特定类型，你可以使用 trial 或 view（由 Data.Row.Variants 导出），但如果你想一次处理所有选项，你可能想使用 switch。你会这样写：

handleTravelOrFlee :: Var ("travel" .== Turn Travel .+ "flee" .== Turn Flee) -> GameState -> GameState
handleTravelOrFlee v gs = switch v $
     #travel .== (\(Travel loc) -> updateGameStateWithLoc gs loc)
  .+ #flee   .== (\Flee -> updateGameStateFlee gs)

查看文档并the examples file了解更多信息。

Answer 3

另一个选项可能是激活和停用求和类型的构造函数：

{-# LANGUAGE GADTs, TypeOperators, DataKinds, PolyKinds, 
             TypeFamilies, StandaloneKindSignatures #-}
{-# OPTIONS_GHC -Werror=incomplete-patterns -Werror=overlapping-patterns #-}
import Data.Void
import Data.Kind

data TurnType =
      Travel
    | Attack
    | Flee
    | Quit

type Turn :: TurnType -> Type
data Turn tt  where
   TurnTravel :: Location -> Turn Travel
   TurnAttack :: Int -> Turn Attack
   TurnFlee :: Turn Flee
   TurnQuit :: Turn Quit

type X :: TurnType -> [TurnType] -> Type
type family X x tts :: Type where
    X _ '[] = Void 
    X x (x : xs) = ()
    X x (_ : xs) = X x xs

-- Exhaustiveness checker knows that branches where
-- X returns Void are impossible.
type AnyTurn :: [TurnType] -> Type
data AnyTurn allowed
   = TravelTurn !(X Travel allowed) (Turn Travel)
   | TravelAttack !(X Attack allowed) (Turn Attack)
   | TravelFlee  !(X Flee allowed) (Turn Flee)
   | TravelQuit  !(X Quit allowed) (Turn Quit)

投入使用：

someTurn :: AnyTurn '[Travel, Attack]
someTurn = TravelAttack () (TurnAttack 0)

-- This doesn't give an exhaustiveness error because other branches are impossible.
-- The problem is that we now have those annoying () cluttering every match.
turn2string :: AnyTurn '[Travel, Attack] -> String
turn2string t = case t of
   TravelTurn () _ -> "foo" 
   TravelAttack () _ -> "bar"
   -- TravelQuit _ _ -> "doesn't compile"

一种将 Haskell 的 Either 类型概括为任意多种类型的方法？

A way to generalize Haskell's Either type for arbitrarily many types?

haskell

types

either

parametric-polymorphism

解决方案 1：创建包装总和类型

解决方案 2：为不同数量的类型创建“任一”类型