Определить функции с foldl foldr

Question

Я понимаю определения foldl, foldr, но у меня проблемы с функциями, определенными ими.

Например карта с foldr:

map f []  = [] 
map f l = foldr (\x xs -> f x : xs) [] l 

Я не понимаю (\x xs -> f x : xs). Это функция отображения, которую занимает foldr? Но не должно быть (\x xs -> f x : f xs), потому что map f (x:xs) = f x : map f xs?

Пример с foldl:

concat (x:xs) = x ++ concat xs 

concat' xs = foldl (++) [] xs 
concat'' xs = foldl (\ys y -> ys ++ y) [] xs 

Конечно, я понимаю (++), но что логика (\ys y -> ys ++ y)? Это ys = [] и y = xs? Таким образом, функция принимает [] как ys и y является первым элементом xs и составляет [] с y? Конкретный пример:

concat'' [1,2,3] = foldl (\ys y -> ys ++ y) [] [1,2,3] 
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [] [1]) [2,3] 
=> foldl (\ys y -> ys ++ y) [1] [2,3] 
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1] [2]) [3] 
=> foldl (\ys y -> ys ++ y) [1,2] [3] 
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1,2] [3]) [] 
=> foldl (\ys y -> ys ++ y) [1,2,3] [] 
=> [1,2,3] 

Другое дело: concat занимает всего 1 список xs, так что если я хочу Concat 2 списка?

concat (x:xs) ys = x ++ concat xs ys 
concat [1,2,3] [4,5,6] with foldl? 

Реверс:

reverse (x:xs) = reverse xs ++ [x] 

reverse' l = foldl (\xs x -> [x] : xs) [] l 
reverse'' l = foldr (\x xs -> xs ++ [x]) [] l 

foldr интуитивно понятно (с вопросами из выше), но то, что за обратным порядком в foldl (\xs x -> [x] : xs)? Это будет foldl (\x xs -> xs ++ [x]) [] l, не так ли?

Большое спасибо!

Answer 1

Код

foldr (\x xs -> ...) end list 

можно прочитать, грубо говоря, следующим

• сканировать весь list
• , если он пустой, просто вернуть конец end
• иначе:
  • пусть x быть элемент под рукой
  • пусть xs будет остальная часть списка, после того, как были обработаны
  • применить операцию ...

подчеркнутая часть имеет решающее значение. xsне остальная часть списка, но результат «рекурсивного вызова» на нем.

Действительно, xs является плохим именем для этого. В общем случае это даже не список! Например.один никогда не будет писать (глупый пример)

foldr (\x xs -> x + xs) 0 [1..100] -- sum 1..100 

а предпочитают что-то вроде

foldr (\x partialSum -> x + partialSum) 0 [1..100] -- sum 1..100 

(На самом деле, один не просуммировать с помощью foldr, но давайте оставим это в стороне.)

Итак, просто прочитайте его так:

map f l = foldr (\x mappedTail -> f x : mappedTail) [] l