Почему Monoid не является обязательным условием для foldr/foldl?

Question

Я смотрю на Foldable класс в Хаскеле. Два из методов fold, foldMap требуется экземпляр Monoid. Но foldr или же foldl нет такого ограничения.

fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b

По результатам foldr/foldl чтобы быть эквивалентным, не должно ли оно ограничить данную функцию свертывания быть ассоциативной? Есть ли примеры, когда результаты foldr/foldl различаются в одном и том же списке?

Разве Foldable не должен оборачивать моноидальное значение? Или складной является более общим?

Answer 1

По результатам foldr/foldl чтобы быть эквивалентным, не должно ли оно ограничить данную функцию свертывания быть ассоциативной? Есть ли примеры, когда результаты foldr/foldl отличаются в одном списке?

Да. Если вы передаете неассоциативную функцию (например, вычитание (-)) вы получите абсолютно разные результаты. И, как вы правильно заметили, нет Monoid экземпляр, который соответствует что-то вроде (-),

Но это по замыслу. Там нет такого ограничения на Foldable случаи, которые foldr а также foldl должны принимать ассоциативные функции. Есть ситуации, когда вам может понадобиться сложить что-то вроде вычитания. Экземпляр Foldable f более заинтересован в ограничении того, что f сможет сделать. В частности, законы:

foldr f z t = appEndo (foldMap (Endo . f) t ) z
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
fold = foldMap id

-- if f is a Functor
foldMap f = fold . fmap f
foldMap f . fmap g = foldMap (f . g)

Вы можете увидеть в источниках, что foldr по умолчанию делает что-то умное с newtype Endo a = Endo (a -> a) моноид эндоморфизма:

-- | Right-associative fold of a structure.
--
-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z

построить моноидальную складку из, возможно, немоноидальной f а также z,

Таким образом, в конечном итоге ответ на вопрос "Почему Monoid не является обязательным требованием?" это очень скучно "потому что это более практично и, в конце концов, не нужно".

Для получения дополнительной информации я отсылаю вас к статье, которая начала все это, " Прикладное программирование с эффектами".