Экспоненциальное офункторивание

[deni_ok]

Как вам скорее всего известно, написать представителя класса типов Functor для типа эндоморфизма невозможно. Если неизвестно, то можете попробовать
newtype Endo a = Endo (a -> a) instance Functor Endo where fmap f (Endo g) = Endo undefined Даже если ваш результат сойдется по типам, законам для функтора он удовлетворять не будет.

Вот вам другой

Comments

[migmit]

Блин, я сначала подумал, что твоё undefined - и есть предлагаемая тобой реализация.

[deni_ok]

Я противозаконными реализациями стараюсь не грешить!

[migmit]

Это правильно.

А ещё это (совершенно законная) монада. Очень интересная.

[deni_ok]

Ничесе!

(a -> b) -> b знаю, а (a -> b) -> a - не знаю :(

[migmit]

Это, кажется, называется search monad. Идея в том, что b - это вроде как "хорошесть" (в каком угодно смысле), a -> b - это "критерий" хорошести значений типа a, а (a -> b) -> a - это функция, которая по критерию ищет "наилучший" ответ (это не значит, что она его хорошо ищет).

Соответственно, return - это функция, которая всегда возвращает одно и то же. Типа стоящих часов: дважды в сутки они всё-таки дают правильный ответ
return a = Quest (\_ -> a)А вот (>>=) интереснее. У нас есть способ находить самый лучший a, и для каждого a мы ищем наилучший c, пользуясь a как дополнительной информацией. Если дополнительная информация не ахти, то и результат мы получим, видимо, паршивый.

Значит, если у нас есть критерий на c, то мы можем сделать из него критерий на a таким образом: пусть у нас есть какой-то a; по нему мы попытаемся найти наилучший c, и посмотрим, насколько хорошо у нас получится:
comap :: (a -> Quest b c) -> (c -> b) -> (a -> b)
comap f p = \a -> case f a of Quest h -> p (h p)Ну а раз у нас есть функция поиска на a, мы можем по

[migmit]

А теперь смешное.

Пусть наша "хорошесть" - это просто Bool, в смысле "подходит/не подходит".
data A = X | YДля конечного типа можно сделать совершенно точную поисковую функцию:
a :: Quest Bool A
a = Quest (\h -> if h X then X else Y)Конечно, если наш критерий не выполняется никогда, то мы получим не подходящий ответ; но это лучшее, что мы можем сделать.

Для пар точная поисковая функция делается очень просто:
aa :: Quest Bool (A, A)
aa = liftM2 (,) a aА теперь берём потоки:
data Stream = Stream A Stream и определяем поисковую функцию:
stream :: Quest Bool Stream
stream = liftM2 Stream a streamСамое смешное, что это работает. Но! Если наш критерий - тотальная функция. Тогда поиск найдёт нам то, что надо.

[deni_ok]

Круто, ты кладезь монадической мудрости!

[migmit]

(шаркает ножкой и изучает потолок)