Что означает тип foldMap :: (Monoid m) => (a -> m) -> fa -> m и как его реализовать?

Question

Может ли кто-нибудь объяснить, что означает тип и как его реализовать?

class Foldable f where
  foldMap :: (Monoid m) => (a -> m) -> f a -> m

На основании https://hackage.haskell.org/package/base-4.9.1.0/docs/Data-Foldable.html#v:foldMap, они объяснили это как "Сопоставить каждый элемент структуры с моноидом и объединитьрезультаты, достижения."но я не совсем понимаю, что это значит. Как я могу сопоставить элемент со структурой моноида?

Я пытался foldMap f = mconcat . (<$>) f, но я получил эту ошибку:

 • Couldn't match type ‘f’ with ‘[]’
      ‘f’ is a rigid type variable bound by
        the class declaration for ‘Foldable’
        at traversable.hs:41:16
      Expected type: f a -> m
        Actual type: [a] -> m
    • In the expression: mconcat . (<$>) f
      In an equation for ‘foldMap’: foldMap f = mconcat . (<$>) f
    • Relevant bindings include
        foldMap :: (a -> m) -> f a -> m (bound at traversable.hs:45:3)

Я попытался код @ WillemVanOnsem и получил эту ошибку:

error:
    • Could not deduce (Data.Foldable.Foldable f)
        arising from a use of ‘foldr’
      from the context: Foldable f
        bound by the class declaration for ‘Foldable’
        at traversable.hs:41:7-14
      or from: Monoid m
        bound by the type signature for:
                   foldMap :: forall m a. Monoid m => (a -> m) -> f a -> m
        at traversable.hs:42:14-47
      Possible fix:
        add (Data.Foldable.Foldable f) to the context of
          the type signature for:
            foldMap :: forall m a. Monoid m => (a -> m) -> f a -> m
          or the class declaration for ‘Foldable’
    • In the expression: foldr (\ x -> mappend (f x)) mempty
      In an equation for ‘foldMap’:
          foldMap f = foldr (\ x -> mappend (f x)) mempty

Answer 1

Итак, у вас есть следующая подпись: foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m. Давайте пошагово шаг за шагом

Ограничения:

a Monoid - это данные, которые можно объединить с помощью какой-либо операции. Вы можете получить много примеров, если подумаете. Просто упомянуть здесь:

• Integer в качестве данных и + в качестве операции. Элементы 1 и 2 могут быть объединены, давая 3 = 1 + 2.
• Integer как данные и * как операция. Элементы 1 и 2 могут быть объединены, давая 2 = 1 * 2.
• List в качестве данных и ++ в качестве операции. Элементы [1,2] и [2,3] могут быть объединены, давая [1,2,2,3] = [1,2] ++ [2,3].
• Vector размера 2 в качестве данных и + в качестве операции. Элементы <1,2> и <4,5> могут быть объединены, давая <5,7> = <1,2> + <4,5>.
• и т. Д.

Все приведенные выше примеры имеют типичное представление Monoid в haskell, типичноопределяется с помощью newtype или data ключевых слов. В haskell моноидная операция представлена ​​как <>.

Важным свойством является то, что моноиды имеют нейтральный элемент и являются ассоциативными. В контексте Integer в соответствии с + нейтральным элементом является 0, ассоциативность определяется тем фактом, что (a + b) + c = a + (b + c). Вы можете легко найти эти свойства во всех приведенных примерах. Попробуйте!

Ограничение Foldable стало проще. По сути, вы можете объединить структуру данных Foldable в одно единственное значение.

Параметры функции

Код стоит тысячи слов, поэтому ...

foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
--          ^^^^^^^^^^^^^^^^^^^^     ^^^^^^^     ^^^
--          |- We've seen this       |           |
--                                   |           |- A 'Set' of a's which can be collapse into a single value
--                                   |- A function to convert a's into a monoid

Итак, по определению вы можете легко следовать этому рассуждению / алгоритму:

Помещения

1. У меня есть структура элементов, которую можно свернуть в одно значение
2. У меня есть способ преобразовать эти элементы в элемент моноида
3. Моноиды имеют нейтральный элемент
4. Два элемента моноидов можно объединить вместе

Алгоритм

• Свернуть элементыструктура, объединяя их, используя оператор моноида
• , если структура пуста, используйте нейтральный элемент в качестве результата.

очень необычно, но ... я все еще не понимаю

Проблема в том, что когда вы определяете экземпляр Foldable, вы еще не определили, как сложить структуру, и это отличается для каждого из них !. Как и в ответе Виллема, вы можете определить foldMap в терминах foldr, что означает, что foldr определяет способ разрушения вашей структуры. Viceversa также верно: вы можете определить foldr в терминах foldMap, и, вероятно, это ошибка !! если вы не определили foldr, универсального способа реализации foldMap не существует, это будет зависеть от вашей структуры данных. Итак, в качестве кода-sumary:

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m -- A default instance can be provided if you define foldr (a.k.a a way to collapse the structure)
  foldr   :: (a -> b -> b) -> b -> t a -> b  -- A default instance can be provided if you define foldMap (a.k.a a way to collapse the structure into a monoid element)
  -- but if you don't provide at least one, It'll be impossible to implement any
  -- because you aren't telling me how to collapse the structure!!

Answer 2

они объяснили это как «сопоставить каждый элемент структуры с моноидом и объединить результаты». но я не совсем понимаю, что это значит. Как мне сопоставить элемент со структурой моноида?

Мы делаем это с помощью функции с сигнатурой a -> m. Поэтому мы сами определяем функцию «отображения».

A моноид [wiki] - алгебраическая структура. По сути это 3-кортеж (S, ⊕, s ₀ ) , где S - набор значений, ⊕ :: S ×S → S является бинарным ассоциативным оператором, а s ₀ является единичным элементом, так что s ₀ ⊕ s = s ⊕ s ₀ = s .

Типы, являющиеся членами Foldable класса , являются даннымиструктуры, которые можно «сложить». Это означает, что, например, если у вас есть Tree, который содержит Int с, то есть Tree Int, такой, что вы для функции f :: Int -> Int -> Int и нейтрального элемента z, вы можете получить Int.

Используя foldMap, мы вызовем функцию f :: a -> m для этих элементов и используем моноидную функцию ⊕ , чтобы «сложить» значения. Для структур данных, которые также реализуют Functor, это, таким образом, более или менее эквивалентно foldMap f = foldr mappend mempty . fmap f.

Однако мы можем использовать f в самой функции foldr, например:

foldMap' :: (Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f x = foldr (\y -> mappend (f y)) mempty x

или короче:

foldMap' :: (Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f = foldr (mappend . f) mempty

Здесь мы, таким образом, сначала предварительно обрабатываем значения в структуре данных с помощью f, чтобы преобразовать их в моноидный объект, и мы называем mappend какфункция складывания на этих предметах.