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

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 экземпляров.

Answer 1

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

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)

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

Answer 4

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

T t1 ... tn

, где t1 ... tn - переменные разных типов и чтосамое большее один экземпляр про тип и класс.В Frege , хотя ограничения на форму типа немного сняты, решающее ограничение остается не более одного экземпляра на класс и тип конструктор .Тем не менее, есть способ сделать show-Part:

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 можно было задавать ex nihilo, или такПоявляется

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

Answer 5

Продолжая предложение Хаммара, сделав еще один шаг, я бы сказал, для этого конкретного примера, просто полностью исключите типовые вещи и используйте вместо этого умные конструкторы.

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.

Answer 6

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