deniok: (Рыжий)
[personal profile] 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

Date: 2015-11-05 07:56 pm (UTC)
From: [identity profile] nponeccop.livejournal.com
Если чо, (->) бифунктор. Т.е. есть более простой способ экспоненциально офункторить.

Date: 2015-11-05 08:39 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Бифунктор по-кметтовски ковариантен по обоим параметрам. А (->) - это профунктор. Хотя это все вопрос терминологии.

Date: 2015-11-05 08:56 pm (UTC)
From: [identity profile] nponeccop.livejournal.com
ошибся. Профунктор, конечно

Date: 2015-11-06 04:14 am (UTC)
From: [identity profile] thedeemon.livejournal.com
42
https://gist.github.com/thedeemon/ddf63573f089dff61aae
Просто по типам разворачиваешь, не думая.

Date: 2015-11-06 11:36 am (UTC)
From: [identity profile] deni-ok.livejournal.com
А если напустить на эту лямбду pointfree (связав предварительно еще и переменные, которые слева от равенства - как бы снимая упаковку/распаковку в newtype), то оказывается, что этот fmap - очень симметричный liftM в примитивном ридере.

Date: 2015-11-06 07:02 am (UTC)
From: [identity profile] migmit.livejournal.com
Блин, я сначала подумал, что твоё undefined — и есть предлагаемая тобой реализация.

Date: 2015-11-06 11:39 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Я противозаконными реализациями стараюсь не грешить!

Date: 2015-11-06 12:21 pm (UTC)
From: [identity profile] migmit.livejournal.com
Это правильно.

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

Date: 2015-11-06 12:55 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Ничесе!

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

Date: 2015-11-06 01:10 pm (UTC)
From: [identity profile] 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)

Date: 2015-11-06 01:15 pm (UTC)
From: [identity profile] 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
Самое смешное, что это работает. Но! Если наш критерий — тотальная функция. Тогда поиск найдёт нам то, что надо.
Edited Date: 2015-11-06 01:20 pm (UTC)

Date: 2015-11-06 01:50 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Круто, ты кладезь монадической мудрости!

Date: 2015-11-06 01:52 pm (UTC)
From: [identity profile] migmit.livejournal.com
(шаркает ножкой и изучает потолок)

Date: 2015-11-06 10:32 pm (UTC)
From: [identity profile] 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 . При этом функция не должна “жульничать” (например, пытаться определить какой ей тип подсунули и специально работать медленно, если тип не тот). Она должна быть более-менее естественной, чтобы демонстрировать пользу унарной записи в реальной жизни.

Date: 2016-01-17 07:29 am (UTC)
From: [identity profile] papa-lyosha.livejournal.com
Да, конечно

Profile

deniok: (Default)
deniok

April 2017

S M T W T F S
      1
23 45678
9101112131415
16171819202122
23242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 24th, 2017 03:04 am
Powered by Dreamwidth Studios