помощь в написании "Колисты Монады" (Упражнение из вступительной статьи Idioms) - PullRequest
Новая
       17

помощь в написании "Колисты Монады" (Упражнение из вступительной статьи Idioms)

8 голосов
/ 24 июня 2011

Я читаю книгу Конора Макбрайда и Росса Патерсона "Функциональная жемчужина / идиомы: прикладное программирование с эффектами:" ( новая версия с "идиомами" в названии).У меня небольшие трудности с Упражнением 4, которое объясняется ниже.Любые подсказки будут высоко оценены (особенно: я должен начать писать fmap и join или return и >>=?).

Постановка проблемы

Вы хотите создатьinstance Monad [], где 

return x = repeat x

и ap = zapp.

Стандартные библиотечные функции

Как на стр.2 статьи, ap применяет монадическое значение-функцию к монадическому значению. 

ap :: Monad m => m (s -> t) -> m s -> m t
ap mf ms = do
    f <- mf
    s <- ms
    return (f s)

Я расширил это в канонической записи до, 

ap mf ms = mf >>= (\f -> (ms >>= \s -> return (f s)))

Функция, зависящая от спискаzapp («приложение zippy») применяет функцию из одного списка к соответствующему значению в другом, а именно: 

zapp (f:fs) (s:ss) = f s : zapp fs ss

Мои трудности

Обратите внимание, что в развернутом виде mf :: m (a -> b) это список функций [(a -> b)] в нашем случае.Итак, в первом приложении >>= мы имеем 

(f:fs) >>= mu

, где mu = (\f -> (ms >>= \s -> return (f s))).Теперь мы можем вызвать fs >>= mu в качестве подпрограммы, но это не знает, как удалить первый элемент ms.(Напомним, что мы хотим, чтобы результирующий список был [f1 s1, f2 s2, ...]. Я пытался что-то взломать, но ... как и предполагалось, это не сработало ... любая помощь будет высоко оценена.

Заранее спасибо!

Редактировать 1

Я думаю, что я заставил его работать, сначала я переписал ap с fmap и join как пользователь "comonad"предложил.

Мой прыжок веры предполагал, что fmap = map. Если кто-нибудь может объяснить, как туда добраться, я был бы очень признателен. После этого ясно, что join работает в спискеперечисляет предложенную пользователем "comonad" и должна быть диагональю \x -> zipWith ((!!) . unL) x [0..]. Мой полный код такой: 

newtype L a = L [a] deriving (Eq, Show, Ord)
unL (L lst) = lst
liftL :: ([a] -> [b]) -> L a -> L b
liftL f = L . f . unL

joinL :: L (L a) -> L a
joinL = liftL $ \x -> zipWith ((!!) . unL) x [0..]

instance Functor L where
    fmap f = liftL (map f)

instance Monad L where
    return x = L $ repeat x
    m >>= g = joinL (fmap g m)

надеюсь, это правильно (похоже, это "решение" на стр. 18 статьи) ... спасибо за помощь всем!

Ответы [ 3 ]

11 голосов
/ 24 июня 2011

Hm.Я не могу не думать, что это упражнение немного несправедливо в том виде, в каком оно представлено.

Упражнение 4 (монада колиста)

Хотя repeat иzapp не являются return и ap обычного Monad [] экземпляра, они, тем не менее, return и ap альтернативной монады, более подходящей для коиндуктивной интерпретации [].Что такое join :: [[x]] → [x] этой монады?

Прокомментируйте относительную эффективность этой монады ap и нашей zapp.

Во-первых, я вполне уверен, чторассматриваемый экземпляр монады недопустим для [] в общем .Когда они говорят «коиндуктивная интерпретация», я подозреваю, что это относится к бесконечным спискам .Экземпляр действительно действителен для конечных списков в некоторых случаях, но не для произвольных списков в целом.

Итак, это ваш первый, очень общий совет - почему экземпляр монады может быть действительным только для определенных списков, особеннобесконечные?

Вот ваш второй намек: fmap и return тривиальны, учитывая другие определения ранее в статье.У вас уже есть return;fmap лишь немного менее очевиден.

Кроме того, (>>=) имеет простую реализацию с точки зрения других функций, как и для любого Monad, что оставляет join в качестве сути вопроса.В большинстве случаев (>>=) более естественно для программирования, но join является более концептуально фундаментальным, и в этом случае, я думаю, более простым для анализа.Поэтому я рекомендую поработать над этим и на время забыть о (>>=).Получив реализацию, вы можете вернуться и восстановить (>>=) и проверить законы монады, чтобы убедиться, что все работает должным образом.

Наконец, предположим, что на мгновение у вас есть fmap, но ничегоостальное.При заданных значениях типа [a -> b] и [a] их можно объединить, чтобы получить что-то типа [[b]].Тип join здесь [[a]] -> [a].Как вы могли бы написать join таким образом, чтобы получить тот же результат, что и при использовании zapp для исходных значений?Обратите внимание, что вопрос об относительной эффективности, как и вопрос, является ключом к реализации.

7 голосов
/ 04 июля 2011

Я просто подумал, что должен уточнить, что версия с упражнениями и "идиомами" в названии является довольно более ранним проектом статьи, которая в конечном итоге появилась в JFP. В то время я ошибочно думал, что колисты (под которыми я подразумеваю, возможно, бесконечные, возможно, конечные списки) были монадой в смысле, соответствующем zapp: есть вероятный кандидат на объединение (на которое ссылаются в других ответах), но Джереми Гиббонс был достаточно любезен, чтобы указать нам, что это не удовлетворяет законам монады. Контрпримеры включают «рваные» списки списков с различной конечной длиной. Соответственно, в статье JFP мы исправились. (Мы были очень рады этому, потому что мы любим находить аппликативные функторы, чьи (<*>) не являются ап Монады.)

Обязательно бесконечные списки (т. Е. streams ), исключая рваные случаи, действительно формируют монаду, ap которой ведет себя как zapp. Для подсказки, обратите внимание, что поток x изоморфен Nat -> x.

Мои извинения за путаницу. Иногда опасно оставлять старые, незаконченные черновики (изобилующие ошибками) валяться (ха-ха) в Интернете.

3 голосов
/ 29 июня 2011

Минимальное полное определение монады: fmap + return + join или return + (>>=). Вы можете реализовать одно с другим: 

(>>=) :: Monad m => m a -> (a->m b) -> m b
(>>=) ma amb = join $ fmap amb ma

fmap :: Monad m => (a->b) -> m a -> m b
fmap f ma = ma >>= (return . f)
join :: Monad m => m (m a) -> m a
join mma = mma >>= id

Теперь реализация ap может быть переписана в терминах join и fmap: 

ap :: Monad m => m (a->b) -> m a -> m b
ap mf ma = do
    f <- mf
    a <- ma
    return (f a)
ap mf ma = do
    f <- mf
    fmap f ma
ap mf ma = join $ fmap (flip fmap ma) mf

В упражнении дана семантика fmap и return и ap. Все остальное станет очевидным, как только вы изучите один пример: 

ap [f1,f2,f3...] [1,2,3...] = join $ fmap (flip fmap [1,2,3...]) [f1,f2,f3...]
                            = join $ [ [(f1 1), f1 2 , f1 3 ...]
                                     , [ f2 1 ,(f2 2), f2 3 ...]
                                     , [ f3 1 , f3 2 ,(f3 3)...]
                                     ...
                                     ]
                            = [(f1 1)
                              ,     (f2 2)
                              ,          (f3 3)
                              ...
                              ]
...