Важна ли разница между foldr и foldl для карт и сетов?

Question

(Этот вопрос применяется более широко, чем к Haskell, но этот язык я буду использовать для его формулировки.)

Различие между foldl и foldr, похоже, зависит от того факта, что спискизаказаны.То есть foldl и foldl сворачивают список, применяя функцию к начальному значению и первому или последнему элементу, затем к результату первого приложения и второго или второго до последнего элемента, затем результатавторого приложения к третьему или третьему элементу и т. д.

Но библиотеки Data.Set и Data.Map для Haskell определяют свои собственные версии foldl и foldr.Например, для карт это:

foldr :: (a -> b -> b) -> b -> Map k a -> b
foldl :: (b -> a -> b) -> b -> Map k a -> b -- I've swapped `a` and `b`
  -- in the second type signature to clarify the correspondence.

Карты и наборы не упорядочены.Стоит ли ожидать различий в производительности между версиями foldl и foldr, определенными для наборов и карт, или же foldr f делает то же самое, что и foldl (flip f)?

Answer 1

Карты и наборы не упорядочены.Стоит ли ожидать различия в производительности между версиями foldl и foldr, определенными для наборов и карт

Если вы ссылаетесь на исходный код Data.Set или Data.Map, вы обнаружите, что их элементы организованы в двоичное дерево:

data Map k a  = Bin !Size !k a !(Map k a) !(Map k a)
              | Tip 

data Set a    = Bin !Size !a !(Set a) !(Set a)
              | Tip

и foldr из Set:

foldr f z = go z
  where
    go z' Tip           = z'
    go z' (Bin _ x l r) = go (f x (go z' r)) l

пересекают деревоиспользуя поиск в глубину с порядком вправо, ток, слева , поэтому, когда foldr (+) 0 применяется к следующему дереву:

                   1
                  / \
                 4   2
                      \
                       3

дает,

4 + (1 + (2 + (3 + 0)))

иfoldl

foldl f z = go z
  where
    go z' Tip           = z'
    go z' (Bin _ x l r) = go (f (go z' l) x) r

с заказом влево, ток, вправо при применении foldl (+) 0 к вышеприведенному дереву, дать:

((((0 + 4) + 1) + 2) + 3)

Это показывает, что foldr и foldl из набора, эквивалентного указанному, применяются к списку как:

foldr (+) 0 [4, 1, 2, 3] = 4 + (1 + (2 + (3 + 0)))
foldl (+) 0 [4, 1, 2, 3] = ((((0 + 4) + 1) + 2) + 3)

аналогично Data.Map и не повторяются здесь.

Более того, как мы знали, foldr может применяться к бесконечному списку (но foldl не может), например:

take 10 $ foldr ((:) . sum) [] $ chunksOf 3 [1..] = [6,15,24,33,42,51,60,69,78,87]

(здесь chunksOf группировать список как [[1,2,3], [4,5,6]...])

Но как насчеткогда путь к дереву бесконечен, например:

                   1
                  / \
                 4   2
                      \
                       3
                        \
                         ...  <- infinite path

Действует ли foldr из Set как список, как упомянуто выше?(Я думаю, ответ да, вы можете проверить это сами)

делает ли Foldr f то же самое, что и foldl (флип f)?

Нет , В качестве исходного кода, как показано выше:

foldr          = ... go (f x (go z' r)) l 

и

foldl (flip f) = ... go (f x (go z' l)) r

Порядок обхода дерева отличается, но общее отношение между foldr иfoldl можно найти в этом посте: Определение foldl в терминах foldr

Answer 2

На самом деле, наборы и карты упорядочены .Вот почему все функции set и map имеют ограничение Ord на тип ключа.Они автоматически упорядочиваются по естественному порядку типа элемента.Так что если ваш набор содержит {3, 5, 2, 1, 4}, то Haskell увидит его (в целях складывания) в следующем порядке: {1, 2, 3, 4, 5}.

Но давайте на минутку забудем об этом.Давайте предположим, что мы находимся в идеальном мире, где данные действительно неупорядочены.Даже тогда разница между foldl и foldr значительна.Предположим, у меня есть набор, как и раньше: {3, 5, 2, 1, 4}, и я хочу выполнить с ним некоторую операцию .*.

foldl (.*) 0 mySet = ((((0 .* 3) .* 5) .* 2) .* 1) .* 4
foldr (.*) 0 mySet = 3 .* (5 .* (2 .* (1 .* (4 .* 0))))

Так что, даже если операция оказывается ассоциативной, начальный элемент помещается впротивоположная сторона с foldl против foldr.Фактически, некоторые операции даже не будут работать , если реализованы с использованием неправильного сгиба.Рассмотрим toList, который определен в Data.Foldable для работы с любым Foldable объектом (включая списки, карты и наборы).Одна из возможных реализаций:

toList :: Foldable t => t a -> [a]
toList = foldr (:) []

Если бы мы попытались сделать foldl

definitelyWrong :: Foldable t => t a -> [a]
definitelyWrong = foldl (:) []

Тогда он даже не скомпилируется.

wrongfold.hs:5:25: error:
    • Occurs check: cannot construct the infinite type: a ~ [a]
      Expected type: [a] -> [a] -> [a]
        Actual type: a -> [a] -> [a]

Этоэто связано с тем, что складки связаны по-разному и могут работать даже с операциями накопления, которые принимают два аргумента разного типа, что также видно из сигнатур типа двух

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Обратите внимание, что первый аргумент не равен a -> a -> a но на самом деле имеет два разных типа, что указывает на то, что порядок определенно имеет значение.