Associated types

[lomeo]

Сегодня прочитал о associated data types - вещь, согласно SPJ менее `tricky`, чем fundeps . Действительно, очень красиво. Жаль, что пока нет реализаций этой красивой идеи (сырой phrac пока не считаем).

Вкратце.
Допустим у нас есть код.

class Mul a b c | a b -> c where
    mul :: a -> b -> c

instance Mul a b c => Mul a [b] [c] where
    mul a b = map (mul a) b -- здесь неважно какой код.

f b x y = if b then x `mul` [y] else y

При вызову f True 1 [2] вывод типа зациклится. В общем, это можно понять если немного задуматься (я практически перевожу):
При выведении типа мы должны будем соединиться с instance Mul a b c => Mul a [b] [c]. Далее (см. код), предполагая, что b = [c], получаем Mul a [[c]] [c], что упрощается нами в Mul a [c] c. Начиная с этого места, опять повторяем свои рассуждения. Бесконечно. И это только из-за того, что здесь есть fundeps. Без него, разумеется, не было бы смысла делать проверку после упрощения.

Это, собственно, проблема (одна из), показывающая несогласованность fundeps. Они там еще много пишут о CHR. Почитайте! Это такое обобщение fundeps.

Так вот, в качестве замены предлагаются как раз эти ассоциированные типы.
Вот стандартная задача, которую решают fundeps: описание интерфейса коллекций, в частности отображений (Map).
А вот как она решается на AT:

class MapKey k where
    data Map k v
    empty :: Map k v
    lookup :: k -> Map k v -> Maybe v

Т.е. вместо записи | k -> v мы будем описывать нужный тип внутри.

instance MapKey Int where
    data Map Int v = MI [v]
    empty = MI []
    lookup k (MI xs) = List.lookup k xs

Ну и так далее, думаю смысл ясен.
Преимущества: мы получаем более согласованную формализацию, чем fundeps. По крайней мере, проблемы, присущие fundeps, здесь не наблюдаются.
Недостатки: писать теперь надо больше :-) Да и, если честно, думаю, своих проблем там найдётся.

Ждём, когда монадические трансформеры перепишут на AT :-)

Comments

[lomeo.livejournal.com]

А как он определит в данном случае, какую реализацию foobar юзать для Y?

[kozodoev.livejournal.com]

да, это я глупость написал не глядя
другое дело, что само себе Y -> a выглядит уж больно надуманно - то есть как такое с классами предлагается перегружать?

[lomeo.livejournal.com]

С классами у нас будет все явно:

class Foo a where
    foo :: a -> R
class Bar a where
    bar :: a -> R
class Foobar a where
    foobar :: a -> R
-- потом 4 instance - пары (X,Foo), (Y,Foo), (X,Bar), (Y,Bar)
-- а потом
instance Foobar X where
    foobar = foo
instance Foobar Y where
    foobar = bar