Как избежать квадратичного взрыва экземпляров typeclass?

Ответ 1

Вы можете сделать что-то подобное, но это не дает вам функциональной зависимости.

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)

Ответ 2

Если у вас нет веских оснований, я бы просто пропустил классы классов и использовал простой старый 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

Ответ 3

То, как я буду делать это на уровне уровня, состоит в том, чтобы сопоставить типы phantom для ввода натуральных чисел уровня и использовать "минимальную" операцию, чтобы найти правильный тип возвращаемого значения, а затем позволить разрешение экземпляра выполнять задание оттуда.

Я буду использовать семейства типов здесь, но, возможно, это возможно с функциональными зависимостями, если вы предпочитаете их.

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

Далее мы определим наши типы phantom и предоставим сопоставления к и от нашего уровня naturals:

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, т.е. мы успешно избегали квадратичного взрыва.

Ответ 4

Первая часть не может быть выполнена таким образом в Haskell 2010, потому что ограничение на экземплярные типы состоит в том, что они имеют вид

T t1 ... tn

где t1... tn - разные переменные типа и что существует не более одного типа pro type и class. В 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 ([email protected] 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 может быть выполнено ex nihilo, или так оно появляется.

Такую же технику можно использовать для выполнения арифметики между различными типами времени, создавая фактор, который делает возможными вычисления в наименьшей единице.

Ответ 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)

Конечно, это не забавно, так как у него нет типов phantom. Удовольствие: сделайте объективы для hr, min, sec.

Ответ 6

Экземпляры все довольно условно. Я бы сказал, что это пример шаблона Haskell (хотя я оставлю объяснение, как это сделать с тем, кто использовал его в гневе).