Складывание без моноидного экземпляра

Question

У меня простая структура дерева:

data Tree a = Leaf | Node a (Tree a) (Tree a)

И Складывается реализация:

import qualified Data.Foldable as F

instance F.Foldable Tree where
  foldMap f Leaf         = mempty
  foldMap f (Node x l r) = F.foldMap f l `mappend`
                           f x           `mappend`
                           F.foldMap f r

И это работает, даже если нет реализации для Monoid И я не могу ни то, ни другого mappend ни mempty в моем коде. Тогда как это Foldable работа внедрения?

Answer 1

Если вы изучите тип для foldMap

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

Вы увидите, что у него есть несвязанный тип m. Анкет Обычно, когда это происходит, это означает, что m может быть что-либо, но здесь это также ограничивает m с Monoid m. Анкет Это есть Monoid происходит от.

Стоит отметить, что если у нас не было Monoid Тест, тогда довольно сложно определить функцию, которая возвращает значение, которое «может быть чем угодно». Если вы попробуете это, вы обнаружите, что это практически невозможно (без «обмана»).

impossible :: Int -> b -- no constraints on `b` at all!
impossible i = ...?

Но это довольно легко, если мы немного знаем о типе

veryPossible  :: Num b => Int -> b
veryPossible  i = fromIntegral i
-- or
veryPossible2 i = fromIntegral (i * i) + fromIntegral i

---

В качестве другого примера рассмотрим тип выражения

expr m = mconcat [m <> m <> mempty, mempty <> m]

Поскольку это выражение создано на основе некоторой неизвестной ценности m и использует Только функции в Monoid Класс или их производные, это тип отражает это. Самый общий тип expr является

expr :: Monoid m => m -> m

Снова здесь, m Является ли переменная свободного типа, чтобы быть немного Monoid.

---

Причина foldMap Позволяет использовать Monoid функции связаны с тем, что он явно ограничивает виды вещей, которые m В его типе подпись может быть. Установив там ограничения, мы получаем больше силы, чтобы манипулировать ими.