Ответ 1
Короткий ответ: это ограничение типа в сигнатуре foldMap.
Если мы посмотрим на исходный код Foldable (более конкретно foldMap), мы увидим:
class Foldable (t :: * -> *) where
...
foldMap :: Monoid m => (a -> m) -> t a -> mТаким образом, если мы объявляем Tree членом Foldable (не то, что Tree имеет вид * -> *), это означает, что a foldMap определено над этим деревом, так что: foldMap :: Monoid m => (a -> m) -> Tree a -> m. Таким образом, это означает, что тип результата (и результат функции, переданной в foldMap) m должен быть Monoid.
Haskell статически типизирован: после компиляции Haskell точно знает типы, которые передаются из каждого экземпляра функции. Таким образом, это означает, что он знает, например, тип вывода, и, следовательно, как его обрабатывать.
Теперь Int не является экземпляром Monoid. Вы здесь используете F.foldl (+) 0 testTree, так что это означает, что вы более или менее создали "ad hoc" моноид. Это работает, если мы посмотрим на исходный код foldl:
foldl :: (b -> a -> b) -> b -> t a -> b foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
У этого есть много логики, окружающих параметры f, z и t. Итак, давайте сначала сломаем это.
Давайте сначала посмотрим на Dual . Endo . flip f. Это сокращение для:
helper = \x -> Dual (Endo (\y -> f y x))
Dual и Endo - это типы с каждым конструктором, который принимает один параметр. Поэтому мы завершаем результат f y x в конструкторах Dual (Endo ...).
Мы будем использовать это как функцию foldMap. Если наш f имеет тип a -> b -> a, то эта функция имеет тип b -> Dual (Endo a). Таким образом, тип вывода функции, переданной в foldMap, имеет тип вывода Dual (Endo a). Теперь, если мы проверим исходный код, мы увидим две интересные вещи:
instance Monoid (Endo a) where mempty = Endo id Endo f `mappend` Endo g = Endo (f . g) instance Monoid a => Monoid (Dual a) where mempty = Dual mempty Dual x `mappend` Dual y = Dual (y `mappend` x)
(обратите внимание, что это y `mappend` x, а не x `mappend` y).
Так что здесь происходит, что mempty, который используется в foldMap, это mempty = Dual mempty = Dual (Endo id). Итак, Dual (Endo ...), который инкапсулирует идентификационную функцию.
Кроме того, mappend двух дуальностей сводится к функциональному составу значений в Endo. Итак:
mempty = Dual (Endo id)
mappend (Dual (Endo f)) (Dual (Endo g)) = Dual (Endo (g . f))
Таким образом, это означает, что если мы сложим по дереву, то в случае, если мы увидим Empty (лист), мы вернемся mempty, и в случае, если мы увидим a Node x l r, мы выполним mappend как описано выше. Итак, "специализированный" foldMap будет выглядеть следующим образом:
-- specialized foldMap
foldMap f Empty = Dual (Endo id)
foldMap f (Node x l r) = Dual (Endo (c . b . a))
where Dual (Endo a) = foldMap f l
Dual (Endo b) = helper x
Dual (Endo c) = foldMap f l
Итак, для каждого Node мы создаем композицию функции справа налево над дочерними элементами и элементом node. a и c могут быть композициями дерева (так как это рекурсивные вызовы). В случае a Leaf мы ничего не делаем (мы возвращаем id, но композиция над id является no-op).
Таким образом, это означает, что если у нас есть дерево:
5
|- 3
| |- 1
| `- 6
`- 9
|- 8
`- 10
Это приведет к функции:
(Dual (Endo ( (\x -> f x 10) .
(\x -> f x 9) .
(\x -> f x 8) .
(\x -> f x 5) .
(\x -> f x 6) .
(\x -> f x 3) .
(\x -> f x 1)
)
)
)
(опустил идентификаторы, чтобы сделать его чище). Это результат getDual (foldMap (Dual . Endo . flip f)). Но теперь нам нужно опубликовать этот результат. С getDual мы получаем содержимое, заключенное в конструктор Dual. Итак, теперь мы имеем:
Endo ( (\x -> f x 10) .
(\x -> f x 9) .
(\x -> f x 8) .
(\x -> f x 5) .
(\x -> f x 6) .
(\x -> f x 3) .
(\x -> f x 1)
)
и appEndo, мы получим функцию, заключенную в Endo, поэтому:
( (\x -> f x 10) .
(\x -> f x 9) .
(\x -> f x 8) .
(\x -> f x 5) .
(\x -> f x 6) .
(\x -> f x 3) .
(\x -> f x 1)
)
а затем применим это к z "начальному" значению. Это означает, что мы будем обрабатывать цепочку, начинающуюся с z (начальный элемент), и применяем ее как:
f (f (f (f (f (f (f z 1) 3) 6) 5) 8) 9) 10
Итак, мы построили некоторый вид моноида, где mappend заменяется на f и mempty как нет-op (функция тождества).