Entry tags:
Экспоненциальное офункторивание
Как вам скорее всего известно, написать представителя класса типов Functor для типа эндоморфизма невозможно. Если неизвестно, то можете попробовать
Вот вам другой экспоненциальный тип данных, для которого, однако, написать законного представителя класса типов 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
no subject
no subject
no subject
no subject
https://gist.github.com/thedeemon/ddf63573f089dff61aae
Просто по типам разворачиваешь, не думая.
no subject
no subject
no subject
no subject
А ещё это (совершенно законная) монада. Очень интересная.
no subject
(a -> b) -> b знаю, а (a -> b) -> a - не знаю :(
no subject
b
— это вроде как "хорошесть" (в каком угодно смысле),a -> b
— это "критерий" хорошести значений типаa
, а(a -> b) -> a
— это функция, которая по критерию ищет "наилучший" ответ (это не значит, что она его хорошо ищет).Соответственно, return — это функция, которая всегда возвращает одно и то же. Типа стоящих часов: дважды в сутки они всё-таки дают правильный ответ А вот (>>=) интереснее. У нас есть способ находить самый лучший
a
, и для каждогоa
мы ищем наилучшийc
, пользуясьa
как дополнительной информацией. Если дополнительная информация не ахти, то и результат мы получим, видимо, паршивый.Значит, если у нас есть критерий на
c
, то мы можем сделать из него критерий наa
таким образом: пусть у нас есть какой-тоa
; по нему мы попытаемся найти наилучшийc
, и посмотрим, насколько хорошо у нас получится: Ну а раз у нас есть функция поиска наa
, мы можем по этому критерию найтиa
, а отсюда уже недалеко и доc
:no subject
Пусть наша "хорошесть" — это просто
Bool
, в смысле "подходит/не подходит". Для конечного типа можно сделать совершенно точную поисковую функцию: Конечно, если наш критерий не выполняется никогда, то мы получим не подходящий ответ; но это лучшее, что мы можем сделать.Для пар точная поисковая функция делается очень просто: А теперь берём потоки: и определяем поисковую функцию: Самое смешное, что это работает. Но! Если наш критерий — тотальная функция. Тогда поиск найдёт нам то, что надо.
no subject
no subject
no subject
В Хаскеле можно определит натуральные числа, как в Пиановской арифметике:
data Natural = Zero | S Natural
Легко написать instance Num Natural, instance Ord Natural, instance Show Natural, и т.д.
Фактически такой тип Natural это тип натуральных чисел, записанных в унарной системе. Вообще-то унарная система сильно не эффективна. Тем не менее, как это ни странно, существуют естественные ситуации, когда такое представление чисел оказывается более эффективным! Вот смотрите:
Prelude Data.Number.Natural> :t f
f :: (Num a, Ord a) => a -> Bool
Prelude Data.Number.Natural> f (10^5 :: Natural)
True
(0.01 secs, 32896040 bytes)
Prelude Data.Number.Natural> f (10^5 :: Integer)
True
(2.44 secs, 1934967184 bytes)
Prelude Data.Number.Natural> f (10^5 :: Int)
True
(2.17 secs, 2094407992 bytes)
Prelude Data.Number.Natural>
Задача: придумать такую функцию f, которая работала бы одинаково для натуральных чисел из Natural, Integer и Int (конечно для чисел меньше maxBound::Int), но при этом, она работола бы сильно эффективней для пиановских натуральных чисел, чем для стандартных типов, таких как Integer и Int . При этом функция не должна “жульничать” (например, пытаться определить какой ей тип подсунули и специально работать медленно, если тип не тот). Она должна быть более-менее естественной, чтобы демонстрировать пользу унарной записи в реальной жизни.
no subject
no subject