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

[thesz.livejournal.com]

Как я от этого далек (пока;).

Редко-редко у меня классы появляются.

[lomeo.livejournal.com]

Ну, я же ОО программист :-)
Отсюда все эти извращенные интересы к Scala и HaskellOO :-)

Эх, просто мне понравилось - красиво получается - вот и написал.
Ну, красиво же :-)

Вместо несколько невнятного | k -> v мы пишем

data Map Int a = MI [a]
data Map Bool a = MB a a

и все хорошо ложится на

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

[thesz.livejournal.com]

Красиво, согласен.

Насчет CHR: http://homepages.dcc.ufmg.br/~camarao/CT/

Там вообще пишешь почти все, что хочешь, а система выводит, выводит... Несколько типов может вывести, даже с разным количеством операндов. ;)

[kozodoev.livejournal.com]

Там вообще пишешь почти все, что хочешь, а система выводит, выводит...

потом уходишь домой, приходишь с утра, а система все выводит, выводит...

;)

[lomeo.livejournal.com]

Какое то сырое это.
А что будет если

foo :: X -> a
foo :: Y -> a
bar :: X -> a
bar :: Y -> a

а потом

foobar x = foo x
foobar x = bar x

непонятно что использовать для типа X, а что для Y.

[kozodoev.livejournal.com]

да то же самое, что и с классами, только автоматом сделает что-то типа

instance Y Foobar where foobar x =

вычислительная сложность этого дела, очевидно, получается соответствующая

[kozodoev.livejournal.com]

ну в смысле "instance Foobar Y" конечно

[thesz.livejournal.com]

И будет ошибка. ;)

Все правильно. ;)

[lomeo.livejournal.com]

А с классами такие вещи явно можно указывать, и ошибки бы не было.
Фиг знает, в общем.

[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