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

[deniok]

Как вам скорее всего известно, написать представителя класса типов Functor для типа эндоморфизма невозможно. Если неизвестно, то можете попробовать

newtype Endo a = Endo (a -> a)

instance Functor Endo where
   fmap f (Endo g) = Endo undefined

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

Вот вам другой экспоненциальный тип данных, для которого, однако, написать законного представителя класса типов Functor можно:

newtype Quest b a = Quest ((a -> b) -> a)

instance Functor (Quest b) where
  fmap f (Quest g) = Quest undefined

Попробуйте сделать это, после чего ответьте на вопрос: чему равен результат такого вызова

> let Quest f = fmap succ $ Quest (\h -> h 40) in f id

Comments

[migmit.livejournal.com]

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

[deni-ok.livejournal.com]

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

[migmit.livejournal.com]

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

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

[deni-ok.livejournal.com]

Ничесе!

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

[migmit.livejournal.com]

Это, кажется, называется 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, мы можем по этому критерию найти a, а отсюда уже недалеко и до c:

Quest h >>= f = Quest (\p -> let a = h (comap f p) in case f a of Quest j -> j p)

[migmit.livejournal.com]

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

Пусть наша "хорошесть" — это просто 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.livejournal.com]

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

[migmit.livejournal.com]

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