如何避免类型类实例的二次爆炸？

Question

请考虑：

{-# OPTIONS -fglasgow-exts #-}

data Second = Second
data Minute = Minute
data Hour = Hour

-- Look Ma', a phantom type!
data Time a = Time Int

instance Show (Time Second) where
  show (Time t) = show t ++ "sec" 

instance Show (Time Minute) where
  show (Time t) = show t ++ "min" 

instance Show (Time Hour) where
  show (Time t) = show t ++ "hrs" 

sec :: Int -> Time Second
sec t = Time t

minute :: Int -> Time Minute
minute t = Time t 

hour :: Int -> Time Hour
hour t = Time t 

class TimeAdder a b c | a b -> c where
  add :: Time a -> Time b -> Time c

instance TimeAdder Second Second Second where
  add (Time s1) (Time s2) = sec (s1 + s2)

instance TimeAdder Second Minute Second where
  add (Time s) (Time m) = sec (s + 60*m)

instance TimeAdder Second Hour Second where
  add (Time s) (Time h) = sec (s + 3600*h)

instance TimeAdder Minute Second Second where
  add (Time m) (Time s) = sec (60*m + s)

instance TimeAdder Minute Minute Minute where
  add (Time m1) (Time m2) = minute (m1 + m2)

instance TimeAdder Minute Hour Minute where
  add (Time m) (Time h) = minute (m + 60*h)

instance TimeAdder Hour Second Second where
  add (Time h) (Time s) = sec (3600*h + s)

instance TimeAdder Hour Minute Minute where
  add (Time h) (Time m) = minute (60*h + m)

instance TimeAdder Hour Hour Hour where
  add (Time h1) (Time h2) = hour (h1 + h2)

add (minute 5) (hour 2)
--125min

虽然我很高兴这种疯狂的东西能够运行，但我想知道如何避免TimeAdder实例数量的二次爆炸。

- Landei

---

小时，分钟和秒并不是这种类型安全的好选择，因为你为什么会有一个只接受秒钟时间的函数呢？这种类型安全更好的练习可能是物理单位。你可以使用幻影类型，例如Time、Mass、Length等，并对速度、能量等进行类型安全的计算。这也有助于减少实例数量，因为并非所有类型都像你的时间示例中那样可互换。 - shang

@shang：没错。我应该提到这只是一个玩具示例，用于更好地掌握类型类和幻影类型。我明白，在实际的时间单位应用中，hammar的第一个答案会更加实用。 - Landei

Answer 1

除非你有充分的理由，否则我建议你跳过类型类(Type Classes)并使用普通的ADT(代数数据类型)：

data Time = Hour Int | Minute Int | Second Int

instance Show Time where
  show (Hour x) = show x ++ "hrs"
  show (Minute x) = show x ++ "min"
  show (Second x) = show x ++ "sec"

add x y = fromSeconds (toSeconds x + toSeconds y)

toSeconds (Hour x) = 3600 * x
toSeconds (Minute x) = 60 * x
toSeconds (Second x) = x

fromSeconds x | mod x 3600 == 0 = Hour (div x 3600)
              | mod x 60 == 0 = Minute (div x 60)
              | otherwise = Second x

这种方法的优点在于可以进行某些类型类方法无法实现的简化，例如：

> add (Second 18) (Second 42)
1min

- hammar

---

好的观点！对于实际应用，我一定会这样做。但是我特别想通过我的示例更好地理解幽灵类型。 - Landei

你可以将hammar的代码转换回类型类，它不会出现二次级爆炸问题，因为它使用秒作为中间单位。 - Sjoerd Visscher

@SjoerdVisscher，您能详细说明一下吗？我不明白如何在返回类型中获得正确的幻影类型。 - dave4420

@dave4420 嗯，你说得对，返回类型将取决于整数值，这是不可能的。 - Sjoerd Visscher

Answer 2

你可以像这样做，但它并不能给你提供函数依赖关系。

class TimeUnit a where
    toSeconds :: a -> Int
    fromSeconds :: Int -> a

instance TimeUnit (Time Second) where toSeconds = id; fromSeconds = id
instance TimeUnit (Time Minute) where toSeconds = (* 60); fromSeconds = (`quot` 60)

class TimeAdd a b c where
    add :: a -> b -> c

instance (TimeUnit a, TimeUnit b, TimeUnit c) => TimeAdd a b c where
    add a b = fromSeconds (toSeconds a + toSeconds b)

- augustss

Answer 3

在类型层面上，我会将幻影类型映射到类型级自然数，并使用“最小值”操作来找到正确的返回类型，然后让实例解析完成其余工作。

我将在此处使用类型族，但如果您更喜欢功能依赖关系，则可能也可以完成。

{-# LANGUAGE TypeFamilies, EmptyDataDecls, FlexibleInstances #-}

首先，我们需要一些类型级别自然数和最小值操作。

data Zero
data Succ n

type family Min a b
type instance Min Zero a = Zero
type instance Min a Zero = Zero
type instance Min (Succ a) (Succ b) = Succ (Min a b)

接下来，我们将定义幻像类型，并提供与我们的类型级自然数之间的映射：

data Second
data Minute
data Hour

type family ToIndex a
type instance ToIndex Hour = Succ (Succ Zero)
type instance ToIndex Minute = Succ Zero
type instance ToIndex Second = Zero

type family FromIndex a
type instance FromIndex (Succ (Succ Zero)) = Hour
type instance FromIndex (Succ Zero) = Minute
type instance FromIndex Zero = Second

接下来是Time类型和Show实例。它们与您原始代码中的相同。

data Time a = Time Int

instance Show (Time Second) where
  show (Time t) = show t ++ "sec" 

instance Show (Time Minute) where
  show (Time t) = show t ++ "min" 

instance Show (Time Hour) where
  show (Time t) = show t ++ "hrs" 

sec :: Int -> Time Second
sec t = Time t

minute :: Int -> Time Minute
minute t = Time t 

hour :: Int -> Time Hour
hour t = Time t 

就像在我对ADT的回答中一样，我们将使用秒作为中间单位：

class Seconds a where
    toSeconds :: Time a -> Int
    fromSeconds :: Int -> Time a

instance Seconds Hour where
    toSeconds (Time x) = 3600 * x
    fromSeconds x = Time $ x `div` 3600

instance Seconds Minute where
    toSeconds (Time x) = 60 * x
    fromSeconds x = Time $ x `div` 60

instance Seconds Second where
    toSeconds (Time x) = x
    fromSeconds x = Time x

现在，唯一需要做的就是定义add函数。

add :: (Seconds a, Seconds b, Seconds c,
       c ~ FromIndex (Min (ToIndex a) (ToIndex b)))
       => Time a -> Time b -> Time c
add x y = fromSeconds (toSeconds x + toSeconds y)

魔法发生在类型相等约束中，这确保了选择正确的返回类型。

这段代码可以像你想要的那样使用：

> add (minute 5) (hour 2)
125min

要添加另一个单位（例如Days），您只需要添加Show，FromIndex，ToIndex和Seconds的实例即可。也就是说，我们成功地避免了二次爆炸。

- hammar

---

哇，这真的很有趣。 - Landei

Answer 4

在Haskell 2010中，第一部分不能以这种方式完成，因为对实例化类型的限制是它们必须采用以下形式：

T t1 ... tn

其中t1 ... tn是不同的类型变量，并且每个类和类型最多只有一个实例。在Frege中，虽然对类型的形式限制稍微放宽了一些，但关键的限制仍然是每个类和类型构造函数最多只有一个实例。

以下是展示部分的方法：

module Test where

data Seconds = Seconds
data Minutes = Minutes
data Hours   = Hours

data Time u = Time Int

class TimeUnit u where
  verbose :: u -> String
  fromTime :: Time u -> u

instance TimeUnit Seconds where 
  verbose _  = "sec"
  fromTime _ = Seconds
instance TimeUnit Minutes where 
  verbose _   = "min"
  fromTime _  = Minutes
instance TimeUnit Hours   where 
  verbose _ = "hrs"
  fromTime _ = Hours

instance Show (TimeUnit u) => Time u where
  show (o@Time t) = t.show ++ verbose (fromTime o)

main _ = do
 println (Time 42 :: Time Seconds)
 println (Time 42 :: Time Minutes)
 println (Time 42 :: Time Hours)

fromTime 应用程序强制调用站点构建一个适当的字典，以便可以从虚无中创建 TimeUnit 值，或者看起来是这样。同样的技术可以用于不同时间类型之间的算术运算，通过创建使计算以最小单位进行的因子。

- Ingo

Answer 5

继续采用hammar的建议，我认为针对这个特定的例子，只需完全消除类型部分，而是使用智能构造函数。

newtype Time = Sec Int

instance Show Time where
  show (Sec n) = h ++ " hrs " ++ m ++ " min " ++ s ++ " sec"
    where h = ...
          m = ...
          s = ...

sec :: Int -> Time
sec = Sec

min :: Int -> Time
min = sec . (*60)

hr  :: Int -> Time
hr  = min . (*60)

add (Sec n) (Sec m) = Sec (n+m)

当然，这样做并不好玩，因为它没有幻影类型。有趣的练习：为 hr、min、sec 制作镜头。

- Dan Burton

Answer 6

所有的实例都是相当模板化的。我想这是模板Haskell的一个案例（尽管我会把如何做的解释留给那些已经使用过它的人）。

- dave4420