Почему Monoid не является требованием для складного/складного?

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

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 различаются в одном списке?

Не должен ли складной экземпляр обернуть моноидальное значение? Или Складная более общая?

источник

2016-06-22 zeronone

Посмотрите на типы первых функций 'foldr' и' foldl'. Моноид не подходит. – pdexter

@pdexter Nah, Monoid - единственное, что действительно имеет смысл для стандартных складок, потому что все рассматривается как «вид списка». Везде, где типы рассматриваются как имеющие более сложную структуру, «левое» и «право» в названии перестают иметь смысл. Если вы хотите сбросить все, что не является списком, вам действительно нужно предоставить более сложную алгебру. –

функциональная композиция * является ассоциативной: 'foldr :: (a -> b -> b) -> b -> ta -> b',' foldr (c :: (a -> b -> b)) :: b -> ta -> b', ** 'c (x :: a) :: b -> b' **, поэтому мы собираемся составлять' c x1', 'c x2', ...,' c xn' в любом порядке, который нам нравится, поскольку/IOW endofunctions * do * образуют моноид, «Endo b», все сами по себе. С помощью, например, list, '(x :) == ([x] ++)', то есть мы можем представить 'c' как' c x = (f x <>) 'с некоторыми подходящими' f' и 'c x. c y ~ = f x <> f y'. (или что-то типа того). –

Для результатов 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.

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

Для получения дополнительной информации я отсылаю вас к бумаге, которая начала все, Applicative Programming with Effects.

источник

2016-06-22 16:58:31 hao

Почему Monoid не является требованием для складного/складного?

ответ

Смежные вопросы