Почему foldl и foldr — не «слева» и «справа»: ассоциативность меняет всё
Differences Between `Foldl` and `Foldr`
Alexis King объясняет, что foldl и foldr различаются не направлением обхода, а ассоциативностью: foldl группирует слева, foldr — справа. В строгих языках foldl хвостово-рекурсивен и работает в константной памяти, а foldr требует n стековых фреймов. В ленивом Haskell foldl строит огромные thunk-и, поэтому нужен строгий foldl', а ленивый foldr позволяет обрабатывать бесконечные списки и экономить вычисления. Практическое правило: для строгих функций — foldl', для ленивых по второму аргументу — foldr, а foldl и foldr' на списках лучше не использовать.
В обоих выражениях элементы списка появляются в одном и том же порядке — слева направо, — но группировка меняется. С foldl применения (⨂) лево-ассоциативны, а с foldr — право-ассоциативны.