Оптимизировать метод суперкласса в зависимости от подкласса - PullRequest
Новая
       6

Оптимизировать метод суперкласса в зависимости от подкласса

0 голосов
/ 26 мая 2018

Могу ли я предоставить уточненную реализацию (также называемую переопределением в ООП) метода в экземпляре класса, когда тип также находится в другом классе?Или, по крайней мере, если этот другой класс является подклассом.

У меня есть класс C с методом m, подкласс S из C с методом s и типом T a так что есть экземпляры 

class C a where m :: [a] -> Bool
class C a => S a where s :: a -> a -> Bool
instance C a => C (T a) where m = ...
instance S a => S (T a) where s = ...

как обычно.Теперь случается так, что когда T a находится в подклассе (который я не могу знать, поскольку он зависит от a), метод m может быть реализован гораздо более эффективно (квадратичное и экспоненциальное время) с использованием s.

Я попытался переопределить m в реализации 

instance S a => S (T a) where
    s = ...
    m = (all . uncurry) (=^=) . pairs -- override C.m

, но компилятор в основном ошибался, потому что m не является публичным методом S.Ну, это не так, но он унаследован в ОО-смысле.

Для конкретной цели специализированная версия m может использоваться для всех случаев;это не значение по умолчанию для переопределения где-либо.

Редактировать: Поскольку запрос, конкретный код с небольшим количеством объяснения.

У меня есть класс Model который имеет (среди прочего) метод con, который проверяет список на согласованность. 

class Model a where
    con :: [a] -> Bool

Две модели могут образовывать модель стрелок. 

data Arrow a b = [a] :->: b
lhs w = [ a | (u :->: _) <- w, a <- u ]
rhs w = [ b | (_ :->: b) <- w ]

Для конкретного экземпляра Model (Arrow a b), общая реализация con очень дорога (обратите внимание powerset в определении). 

instance (Model a, Model b) => Model (Arrow a b) where
    con w = all (\w' -> con (lhs w') `implies` con (rhs w')) (powerset w)

Существует подкласс CoherentModel из Model, который имеет метод (=^=), которыйпроверяет согласованность для двух объектов.Условием для согласованных моделей является согласованность списка, если все пары. 

class Model a => CoherentModel a where
    (=^=) :: a -> a -> Bool
    a =^= b = con [a, b]

Класс CoherentModel является на данный момент большим количеством документации, чем функция.

Итак, учитывая, чтомодель согласована, согласованность гораздо эффективнее проверять. 

instance (Model a, CoherentModel b) => CoherentModel (Arrow a b) where
    (u :->: a) =^= (v :->: b) = con (u ++ v) `implies` a =^= b

И в этом случае con может быть реализовано с использованием 

con = (all . uncurry) (=^=) . pairs
  where
    pairs :: [a] -> [(a,a)]
    pairs [] = []
    pairs [_] = []
    pairs [x,y] = [(x,y)]
    pairs (x:xs) = map ((,) x) xs ++ pairs xs

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

1 Ответ

0 голосов
/ 27 мая 2018

Хороший вопрос.Следует помнить одну вещь: информация о том, является ли тип данных экземпляром класса типов, информация только во время компиляции - т.е. мы всегда можем выбрать, какой экземпляр использовать, используя статически доступную информацию на сайте использования,и полиморфизм происходит от возможности выбрать экземпляр из контекста.В общем, если вы спросите «Является ли a членом класса типов B?», Вы можете получить только ответы «да» и «Ошибка компиляции».(Это второе наблюдение немного изменилось на OverlappingInstances, но, похоже, оно не помогает в вашем случае)

Таким образом, ответ на ваш ближайший вопрос нет .Вы не можете принять решение о принадлежности типа к классу типов, если вы не являетесь методом этого класса типов.Что мы можем сделать, это добавить это решение в качестве метода (используя пакет constraints) 

import Data.Constraint

class Model a where
    con :: [a] -> Bool
    isCoherent :: Maybe (Dict (CoherentModel a))
    isCoherent = Nothing

, который вы можете определить тривиально для любого типа, который вы создали CoherentModel в:

instance Model Foo where
    con = ...
    isCoherent = Just Dict

Теперь вы можете реализовать свое решение следующим образом (с расширениями ScopedTypeVariables и TypeApplications): 

instance (Model a, Model b) => Model (Arrow a b) where
    con | Just Dict <- isCoherent @b = -- efficient implementation
        | otherwise                  = -- inefficient implementation

В теле первого случая мы получимместный CoherentModel b в контексте.Это круто.

Жаль, что у нас есть проблема выражения здесь, где все различные реализации con должны быть собраны в одном месте.Также очень плохо isCoherent необходимо внедрять вручную для каждого связного экземпляра Model, отдельно от того, где находится его экземпляр CoherentModel.

Здесь есть что исследовать, но мне нужно идти.Удачи!

...