Ограничение параметра типа до Monoid

Ранее я определил функцию, которая берет список Maybe и превращает его в Maybe списка, например так:

floop :: [Maybe a] -> Maybe [a]
floop [] = Just []
floop (Nothing:_) = Nothing
floop (Just x:xs) = fmap (x:) $ floop xs

Теперь я хочу переопределить его, чтобы он был совместим с большим классом контейнеров, а не только со списками, и я обнаружил, что он должен реализовать функции foldr, mappend, mempty, fmap и pure; поэтому я полагаю, что следующая строка типа будет уместной:

floop :: (Foldable t, Functor t, Monoid t) => t (Maybe a) -> Maybe (t a)

Поскольку (я думаю) это гарантирует, что эти функции реализованы для данного контейнера, однако это приводит к следующей ошибке:

Expecting one more argument to ‘t’
The first argument of ‘Monoid’ should have kind ‘*’,
  but ‘t’ has kind ‘* -> *’
In the type signature for ‘floop'’:
  floop' :: (Foldable t, Functor t, Monoid t) =>
            t (Maybe a) -> Maybe (t a)

Изучив его, я обнаружил, что тип Monoid отличается от вида Functor и Foldable, но я не понимаю, почему это так, и как исправить ошибку.

Кому интересно, вот текущая реализация:

floop :: (Foldable t, Functor t, Monoid t) => t (Maybe a) -> Maybe (t a)
floop xs = let
                f :: (Foldable t, Functor t, Monoid t) => Maybe a -> Maybe (t a) -> Maybe (t a)
                f Nothing _ = Nothing
                f (Just x) ys = fmap (mappend $ pure x) ys
            in
                foldr f (Just mempty) xs

Примечание. Мне сообщили, что это уже существует как встроенная функция (sequence), но я намерен реализовать ее в качестве учебного упражнения.


types haskell type-kinds
person Zoey Hewll    schedule 01.02.2017    source источник
comment
Дополнительное примечание: если вы хотите сравнить floop со встроенным обобщением, я предлагаю взглянуть на более общий sequenceA вместо sequence.   -  person duplode    schedule 01.02.2017
comment
Релевантно: Что мы можем сделать с альтернативой, но не можем сделать с моноидом?   -  person duplode    schedule 01.02.2017
comment
(Есть довольно много интересных вопросов об отношениях между Alternative, MonadPlus и Monoid, которые вы, возможно, захотите проверить. Я дал ссылку именно на этот вопрос, потому что он действительно краток и более четко связан с вашей конкретной проблемой.)   -  person duplode    schedule 01.02.2017
comment
@duplode Спасибо за ссылку, она помогла мне понять, что я делаю не так с Monoid t. Я не понимал, что Monoid a - это "конкретный" тип, а не конструктор типа, такой как Foldable t.   -  person Zoey Hewll    schedule 02.02.2017
comment
Что бы это ни стоило, вы можете также исправить это, просто изменив Monoid t на Monoid (t a) везде (и обновив Functor t до Applicative t везде, но это не имеет отношения к вашему фактическому вопросу).   -  person Daniel Wagner    schedule 02.02.2017
comment
Спасибо, да, это тоже сработало бы. Я действительно заметил, что t даже не обязательно должно быть Functor. Я использую fmap на Maybe, а не на t   -  person Zoey Hewll    schedule 02.02.2017

Ответы (2)


arrow_upward
9
arrow_downward

Моноидальные аппликативы описываются классом Alternative с использованием (<|>) и empty вместо mappend и mempty:

floop :: (Foldable t, Alternative t) => t (Maybe a) -> Maybe (t a)
floop xs = let
                f :: (Foldable t, Alternative t) => Maybe a -> Maybe (t a) -> Maybe (t a)
                f Nothing _ = Nothing
                f (Just x) ys = fmap ((<|>) $ pure x) ys
            in
                foldr f (Just empty) xs
person Lee    schedule 01.02.2017

arrow_upward
3
arrow_downward

Это может быть хорошим местом для обсуждения гугл.

Поиск t (m a)-> m (t a) возвращает sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a) в качестве первого результата. Затем это приводит к классу типа Traversable, который довольно близок к тому, что вы ищете.

Как сказал Ли, вы можете использовать класс Alternative, который является аппликативным эквивалентом Monoid. Чуть более обобщенно:

sequence' :: (Alternative t, Foldable t, Applicative a) => t (a b) -> a (t b)
sequence' = foldr step (pure empty)
  where step = liftA2 prepend
        prepend = (<|>) . pure

Здесь prepend first оборачивает некоторый отдельный элемент в t, чтобы он мог использовать (‹|>) для его добавления. liftA2 позволяет нам абстрагироваться от аппликативного a, вы можете представить его как развертывание двух аргументов, применение их в начале и перенос результата обратно.

person Taren    schedule 01.02.2017
comment
Это работает отлично, и мне нравится, что это значительно более общее; однако я не совсем понимаю, как работают step и liftA2. liftA2 похож на fmap? (хотя я замечаю, что у него более высокая арность) - person Zoey Hewll; 02.02.2017
comment
Давайте посмотрим на сигнатуру fmap, добавив для ясности скобки: (a -> b) -> (f a -> f b). Мы могли бы рассматривать это как поднятие функции, чтобы она работала над f. Однако это работает только для функций с 1 аргументом. Если мы fmap +1 вместо Just 1 получим Just (+1) и не сможем продолжить fmap. Поэтому вместо этого мы используем функцию <*> из Applicative, которая распаковывает обе стороны перед применением: Just (+1) <*> Just 2 == Just 3. Существует также операторная форма для fmap, <$>. Тогда мы получаем liftA2 f a b = f <$> a <*> b! Так что ваша интуиция верна, liftA2 по сути является fmap для двух аргументов. - person Taren; 02.02.2017
comment
Я предполагаю, что в первом примере вы имеете в виду fmap + поверх Just 1. Что касается <*>, правильно ли я думаю, что (Just f) <*> (Just x) == f <$> (Just x)? Итак, liftA2 f a b концептуально сопоставляет f с a, разворачивает результат, а затем сопоставляет его с b? - person Zoey Hewll; 03.02.2017
comment
Ты получил это! Точно так же вы также можете реализовать fmap/‹$›, используя только аппликатив, как fmap f a = pure f <*> a. - person Taren; 03.02.2017