Возможно ли реализовать foldl/foldr, используя нечеткую складку?

Question

По нестойкой складке я имею в виду гипотетическую операцию примитивного сгиба для ассоциативных операторов, которая не гарантирует никакого упорядочения. То есть (fold + 0 [a b c d]) может быть (+ (+ a b) (+ c d)) или (+ (+ (+ a b) c) d).

Учитывая, что эта операция является сплавируемой, высокопараллелизуемой и универсальной, я думал, что она включает вместе с map и concat в качестве единственных примитивов списка для моего нерекурсивного минималистического языка. Мне удалось реализовать с ним большинство функций списка, но не сторонние складки foldl/foldr. Является ли это возможным?

Answer 1

Если у вас есть fold и map, что является универсальным. Лозунг здесь foldr is made of monoids На самом деле, стандарт Haskell реализует класс типов Foldablefoldr и foldlin just this way

Хитрость заключается в том, что множество эндоморфизмов над множеством форм Моноид под функцией композиции с функцией идентичности как личности.

Обратите внимание, что foldr и foldl являются неотъемлемо последовательными. Таким образом, этот трюк должен отказаться от любого параллелизма, который у вас есть при реализации fold и map. По сути, кодирование foldr в foldMap является кодированием отложенного последовательного вычисления в потенциально неупорядоченный. Вот почему я рекомендую использовать foldMap по сравнению с foldr, когда это возможно - он поддерживает неявный параллизм, когда это возможно, но эквивалентно выразительной мощности.

EDIT: Сложив все в одном месте

Определит множество эндо морфизмов над a

newtype Endo a = Endo { appEndo :: a -> a } 

instance Monoid (Endo a) where 
    mempty = Endo id 
    Endo f `mappend` Endo g = Endo (f . g) 

затем в складном, мы видим определение foldr

foldr f z t = appEndo (foldMap (Endo . f) t) z 

этом используется foldMap, который имеет тип Monoid m => (a -> m) -> t a -> m (где t - это коллекция, которую мы складываем ING более, мы можем делать вид, что список теперь дает Monoid m => (a -> m) -> [a] -> m и эквивалентен

foldMap f ls = fold (map f ls) 

где fold находится в моноидный раз. Если у вас есть неупорядоченная складка под названием fold' :: (a -> a -> a) -> a -> [a] -> a то, что это просто

fold = fold' mappend mempty 

так

foldr f z t = appEndo (foldMap (Endo . f) t) z 
= appEndo (fold (map (Endo . f) t)) z 
= appEndo (fold' mappend mempty (map (Endo . f) t)) z 
= appEndo (fold' (\(Endo f) (Endo g) -> Endo (f . g) (Endo id) (map (Endo . f) t)) z 

, которые могут быть еще более упрощен до

foldr f z t = (fold' (.) id (map f t)) z 

и сбросив ненужный Паренс

foldr f z t = fold' (.) id (map f t) z 

, что дал Даниэль Вагнер в качестве ответа. Вы можете реализовать foldl аналогичным образом или через foldr.

Answer 2

foldr f z xs = fold (.) id (map f xs) z 

Например, в GHCI:

*Dmwit Debug.SimpleReflect> let foldr' f z xs = foldb (.) id (map f xs) z 
*Dmwit Debug.SimpleReflect> foldr' f z [w,x,y] 
f w (f x (f y z)) 
*Dmwit Debug.SimpleReflect> foldr f z [w,x,y] 
f w (f x (f y z))