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

[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

[nponeccop.livejournal.com]

Если чо, (->) бифунктор. Т.е. есть более простой способ экспоненциально офункторить.

[thedeemon.livejournal.com]

42
https://gist.github.com/thedeemon/ddf63573f089dff61aae
Просто по типам разворачиваешь, не думая.

[migmit.livejournal.com]

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

[papa-lyosha.livejournal.com]

Если вам интересны задачи по Хаскелю, то как вам такая задача?
В Хаскеле можно определит натуральные числа, как в Пиановской арифметике:

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 . При этом функция не должна “жульничать” (например, пытаться определить какой ей тип подсунули и специально работать медленно, если тип не тот). Она должна быть более-менее естественной, чтобы демонстрировать пользу унарной записи в реальной жизни.