Understanding the work of foldr and unfoldr

Question

I have hard time understanding how these bits of code work.

"Map" function must apply the function to all elements in given list, and generate list consist of results of applying. So we are giving our function f and some list, then in lambda expression our list transforms into head "x" and tail "xs", we applying function "f" to x and append it to "xs". But what happens next? How and what exactly foldr takes for its second argument (which must be some starting value usually). And for what purpose empty list? And function "rangeTo" : we are creating lambda expression, where we are checking that we are over the end of range, end if we are than we are giving Nothing, or if we are not at end, we are giving pair where first number append to resulting list, and second number used as next value for "from". Is it all what happens in this function, or I'm missing something?

--custom map function through foldr
map :: (a -> b) -> [a] -> [b]
map f = foldr (\x xs -> f x : xs) []
--function to create list with numbers from first argument till second and step "step"
rangeTo :: Integer -> Integer -> Integer -> [Integer]
rangeTo from to step =  unfoldr (\from -> if from >= to then Nothing else Just (from, from+step)) from

Answer 1

To understand How foldr operates on a list. It is better to write down the definition of foldr as

foldr step z xs 
= x1 `step` foldr step z xs1                                -- where xs = x:xs1
= x1 `step` (x2 `step` foldr step z xs2)                    -- where xs = x1:x2:xs2
= x1 `step` (x2 `step` ... (xn `step` foldr step z [])...)  -- where xs = x1:x2...xn:[]

and

foldr step z [] = z

For your case:

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

where

step = (\x xs -> f x : xs)
z = []

From the definition of foldr, the innermost expression

(xn `step` foldr step z []) 

is evaluated first, that is

xn `step` foldr step z []
= step xn (foldr step z [])
= step xn z
= step xn []  -- z = []
= f xn : []   -- step = (\x xs -> f x : xs)
= [f xn]

what happens next? The evaluation going on as

x(n-1) `step` (xn `step` foldr step z [])
= step x(n-1) [f xn]
= f x(n-1) : [f xn]
= [f x(n-1), f xn]

untill:

x1 `step` (x2 ...
= step x1 [f x2, ..., f xn]
= [f x1, f x2, ... f xn]

Answer 2

So we are giving our function f and some list, then in lambda expression our list transforms into head "x" and tail "xs", we applying function "f" to x and append it to "xs".

This is not the case. Look closely at the implementation:

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

There is an implied variable here, we can add it back in:

map :: (a -> b) -> [a] -> [b]
map f ls = foldr (\x xs -> f x : xs) [] ls

map takes two arguments, a function f and a list ls. It passes ls to foldr as the list to fold over, and it passes [] as the starting accumulator value. The lambda takes a list element x and an accumulator xs (initially []), and returns a new accumulator f x : xs. It does not perform a head or tail anywhere; x and xs were never part of the same list.

Let's step through the evaluation to see how this function works:

map (1+) [2, 4, 8]

foldr (\x xs -> (1+) x : xs) [] [2, 4, 8] -- x = 8, xs = []
foldr (\x xs -> (1+) x : xs) [9] [2, 4]   -- x = 4, xs = [9]
foldr (\x xs -> (1+) x : xs) [5, 9] [2]   -- x = 2, xs = [5, 9]
foldr (\x xs -> (1+) x : xs) [3, 5, 9] [] --        xs = [3, 5, 9]

map (1+) [2, 4, 8] == [3, 5, 9]

The empty list accumulates values passed through f, starting from the right end of the input list.

---

And function "rangeTo" : we are creating lambda expression, where we are checking that we are over the end of range, end if we are than we are giving Nothing, or if we are not at end, we are giving pair where first number append to resulting list, and second number used as next value for "from". Is it all what happens in this function, or I'm missing something?

Yes, that's exactly what's going on. The lambda takes an accumulator, and returns the next value to put in the list and a new accumulator, or Nothing if the list should end. The accumulator in this case is the current value in the list. The list should end if that value is past the end of the range. Otherwise it calculates the next accumulator by adding the step.

Again, we can step through the evaluation:

rangeTo 3 11 2 -- from = 3, to = 11, step = 2

Just (3, 5)    -- from = 3
Just (5, 7)    -- from = 3 + step = 5
Just (7, 9)    -- from = 5 + step = 7
Just (9, 11)   -- from = 7 + step = 9
Nothing        -- from = 9 + step = 11, 11 >= to

rangeTo 3 11 2 == [3, 5, 7, 9]