Haskell foldl implementation with foldr

Question

I have troubles understanding the implementation of the foldl function using foldr. I have read this question (Writing foldl using foldr) and I still have some things I don't understand in the following example:

fun :: [Int] -> [Int]
fun l = foldr g (const []) l 1
    where g x f lst = if gcd x lst == 1 then x : f x else f lst

The function takes a list as parameter and return another list where gcd(l[i], l[i + 1] = 1.

My questions are the following:
1. Who are x, f and lst
2. What is const[] and why I can't use the id function?

Answer 1

foldr is one of those weird tools like bicycles that are really easy to use once you get the hang of them but hard to learn from the start. After several years of experience, I've gotten really good at spotting problems I can solve with foldr, and solving them with it immediately and correctly, but it could easily take me a while to figure out what just what I've done in enough detail to explain!

From a practical standpoint, I usually think of foldr in vaguely continuation-passing language. Ignoring the "simple" case where foldr is only applied to three arguments, an application of foldr looks like this:

foldr go finish xs acc1 acc2 ... where
  finish acc1 acc2 ... = ?
  go x cont acc1 acc2 ... = ?

acc1, etc., are accumulators passed "from left to right". The result consists, conceptually, of a single value passed "from right to left".

finish gets the final values of the accumulators and produces something of the result type. It's usually the easiest part to write because

foldr go finish [] acc1 acc2 ...
=
finish acc1 acc2 ...

So once you figure out just what you want your fold to produce, writing finish is fairly mechanical.

go gets a single container element, a "continuation", and the accumulators. It passes modified values if those accumulators "forward" to the continuation to get a result, and uses that result to construct its own.

foldl is a particularly simple case because its go function just returns the result it gets from folding the rest of the container with a new accumulator argument. I think it's a bit more instructive to look at an example that does a bit more. Here's one that takes a container of numbers and produces a list of pairs representing a running sum and a running product.

sumsProducts :: (Num n, Foldable f) => f n -> [(n, n)]
sumsProducts xs = foldr go finish xs 0 1
  where
    finish total prod = [(total, prod)]
    go x cont total prod =
      (total, prod) : cont (x + total) (x * prod) 

Answer 2

foldr's type signature is this

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

This means your foldr applied to its 3 arguments must return a function that takes the 1 as an argument.

So you can specialise your foldr to this

foldr :: (Int -> (Int -> [Int]) -> (Int -> [Int])) 
        -> (Int -> [Int]) 
        -> [Int]
        -> (Int -> [Int])

This means your g function must have the following type

g :: Int -> (Int -> [Int]) -> Int -> [Int] 

So your parameters have the type

x   :: Int
f    :: Int -> [Int]
lst :: Int

And foldr in its 2nd argument requires a Int -> [Int] instead of just an Int, so you can't pass it the value [].

Fortunately const returns a function that ignores its argument and just always return a constant expression

const [] :: a -> [b]

In your case f is indeed some kind of accumulator. But instead of reducing e.g. a list of values to some number, you are chaining functions here. By passing 1 to this function chain in the end, it gets evaluated and is then building the actual list you return in fun.