складной. foldr function composition - Haskell

Question

Итак, я действительно обжариваю свой мозг, пытаясь понять композицию foldl.foldr. Вот пример:

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

Результат есть 22, но что на самом деле здесь происходит?

Для меня это похоже на то, что происходит: foldl (+) 1 [6,15]. Мое сомнение связано с частью foldr. Не следует ли добавить 1 во все под-списки? Примерно так: foldr (+) 1 [1,2,3]. В моей голове 1 добавляется только один раз, правильно? (возможно, нет, но я хочу знать, как/почему!).

Я очень смущен (и, возможно, все замешательство, ха-ха). Спасибо!

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

становится

foldl (foldr (+)) 1 [[1,2,3],[4,5,6]] 

Таким образом, вы получите

foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]] 

после первого этапа foldl или

foldl (foldr (+)) 7 [[4,5,6]] 

если мы оценить нанесенный foldr (если только stric Анализатор tness умирает, она на самом деле остается невычисленным преобразователем, пока foldl не прошло весь список, но следующее выражение более читаемое с ним оцениваемым), и это становится

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) [] 

и, наконец,

foldl (foldr (+)) 22 [] 
~> 22 

Answer 2

Посмотрим foldl . foldr. Их типы

foldl :: (a -> b -> a) -> (a -> [b] -> a) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

Я намеренно использовал различные переменные типа, и я добавил круглые скобки так, что она становится все более очевидным, что мы рассматриваем их теперь как функции одного аргумента (и их результаты являются функциями). Рассматривая foldl, мы видим, что это своего рода функция подъема: если функция, которая производит a от a, используя b, мы поднимаем ее так, чтобы она работала на [b] (повторив вычисление). Функция foldr похожа, как раз с аргументами, противоположными.

Что произойдет, если мы применим foldl . foldr? Во-первых, давайте выведем тип: мы должны объединить переменные типа так, чтобы результат foldr соответствовал аргументу foldl. Таким образом, мы должны заменить: a = d, b = [c]:

foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

Таким образом мы получаем

foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d) 

И чем ее смысл? Сначала foldr поднимает аргумент типа c -> d -> d для работы над списками и отменяет его аргументы, чтобы мы получили d -> [c] -> d. Затем foldl снова активирует эту функцию для работы на [[c]] - списки [c].

В вашем случае операция, снятая (+), ассоциативна, поэтому мы не заботимся о порядке ее применения. Двойной подъем просто создает функцию, которая применяет операцию для всех вложенных элементов.

Если мы используем только foldl, эффект даже лучше: Мы можем поднять несколько раз, как в

foldl . foldl . foldl . foldl 
    :: (a -> b -> a) -> (a -> [[[[b]]]] -> a) 

Answer 3

На самом деле, (foldl.foldr) f z xs === foldr f z (concat $ reverse xs).

Даже если f является ассоциативной операцией, имеет значение правильная последовательность приложений, так как это может повлиять на производительность.

Мы начинаем с

(foldl.foldr) f z xs 
foldl (foldr f) z xs 

письменной форме с g = foldr f и [x1,x2,...,xn_1,xn] = xs на мгновение, это

(...((z `g` x1) `g` x2) ... `g` xn) 
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ...) 
foldr f z $ concat [xn,xn_1, ..., x1] 
foldr f z $ concat $ reverse xs 

Так что в вашем случае правильная последовательность редукция

(foldl.foldr) 1 [[1,2,3],[4,5,6]] 
4+(5+(6+( 1+(2+(3+ 1))))) 
22 

К остроумию ,

Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]] 
[7,8,4,5,6,1,2,3] 

---

Аналогично, (foldl.foldl) f z xs == foldl f z $ concat xs. С snoc a b = a++[b],

Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]] 
[1,2,3,4,5,6,7,8] 

Кроме того, (foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs) и т.д .:

Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[1,2,3,4,5,6,7,8] 
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,1,2,3,4,5,6] 
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,4,5,6,1,2,3]