Defining foldl in terms of foldr in Standard ML

Question

The defined code is

fun foldl f e l = let
    fun g(x, f'') = fn y => f''(f(x, y)) 
    in foldr g (fn x => x) l e end

I don't understand how this works; what is the purpose of g(x, f'')?

I also find a similar example in Haskell, the definition is quite short

myFoldl f z xs = foldr step id xs z
    where
        step x g a = g (f a x)

Answer 1

Let's dissect the Haskell implementation of myFoldl and then take a look at the ocaml SML code. First, we'll look at some type signatures:

foldr :: (a -> b -> b) -- the step function
      -> b             -- the initial value of the accumulator
      -> [a]           -- the list to fold
      -> b             -- the result

It should be noted that although the foldr function accepts only three arguments we are applying it two four arguments:

foldr step id xs z

However, as you can see the second argument to foldr (i.e. the inital value of the accumulator) is id which is a function of the type x -> x. Therefore, the result is also of the type x -> x. Hence, it accepts four arguments.

Similarly, the step function is now of the type a -> (x -> x) -> x -> x. Hence, it accepts three arguments instead of two. The accumulator is an endofunction (i.e. a function whose domain and codomain is the same).

Endofunctions have a special property, they are composed from left to right instead of from right to left. For example, let's compose a bunch of Int -> Int functions:

inc :: Int -> Int
inc n = n + 1

dbl :: Int -> Int
dbl n = n * 2

The normal way to compose these functions is to use the function composition operator as follows:

incDbl :: Int -> Int
incDbl = inc . dbl

The incDbl function first doubles a number and then increments it. Note that this reads from right to left.

Another way to compose them is to use continuations (denoted by k):

inc' :: (Int -> Int) -> Int -> Int
inc' k n = k (n + 1)

dbl' :: (Int -> Int) -> Int -> Int
dbl' k n = k (n * 2)

Notice that the first argument is a continuation. If we want to recover the original functions then we can do:

inc :: Int -> Int
inc = inc' id

dbl :: Int -> Int
dbl = dbl' id

However, if we want to compose them then we do it as follows:

incDbl' :: (Int -> Int) -> Int -> Int
incDbl' = dbl' . inc'

incDbl :: Int -> Int
incDbl = incDbl' id

Notice that although we are still using the dot operator to compose the functions, it now reads from left to right.

This is the key behind making foldr behave as foldl. We fold the list from right to left but instead of folding it into a value, we fold it into an endofunction which when applied to an initial accumulator value actually folds the list from left to right.

Consider our incDbl function:

incDbl = incDbl' id
       = (dbl' . inc') id
       =  dbl' (inc' id)

Now consider the definition of foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _   acc []     = acc
foldr fun acc (y:ys) = fun y (foldr fun acc ys)

In the basis case we simply return the accumulated value. However, in the inductive case we return fun y (foldr fun acc ys). Our step function is defined as follows:

step :: a -> (x -> x) -> x -> x
step x g a = g (f a x)

Here f is the reducer function of foldl and is of the type x -> a -> x. Notice that step x is an endofunction of the type (x -> x) -> x -> x which we know can be composed left to right.

Hence the folding operation (i.e. foldr step id) on a list [y1,y2..yn] looks like:

step y1 (step y2 (... (step yn id)))

-- or

(step y1 . step y2 . {dots} . step yn) id

Each step yx is an endofunction. Hence, this is equivalent to composing the endofunctions from left to right.

When this result is applied to an initial accumulator value then the list folds from left to right. Hence, myFoldl f z xs = foldr step id xs z.

---

Now consider the foldl function (which is written in Standard ML and not OCaml). It is defined as:

fun foldl f e l = let fun g (x, f'') = fn y => f'' (f (x, y))
                  in  foldr g (fn x => x) l e end

The biggest difference between the foldr functions of Haskell and SML are:

1. In Haskell the reducer function has the type a -> b -> b.
2. In SML the reducer function has the type (a, b) -> b.

Both are correct. It's only a matter of preference. In SML instead of passing two separate arguments, you pass one single tuple which contains both arguments.

Now, the similarities:

1. The id function in Haskell is the anonymous fn x => x function in SML.
2. The step function in Haskell is the function g in SML which takes a tuple containing the first two arguments.
3. The step function is Haskell step x g a has been split into two functions in SML g (x, f'') = fn y => f'' (f (x, y)) for more clarity.

If we rewrite the SML function to use the same names as in Haskell then we have:

fun myFoldl f z xs = let step (x, g) = fn a => g (f (a, x))
                     in foldr step (fn x => x) xs z end

Hence, they are exactly the same function. The expression g (x, f'') simply applies the function g to the tuple (x, f''). Here f'' is a valid identifier.

Answer 2

Intuition

The foldl function traverses the list head to tail while operating elements with an accumulator:

(...(a⊗x₁)⊗...⊗x_n-1)⊗x_n

And you want to define it via a foldr:

x₁⊕(x₂⊕...⊕(x_n⊕e)...)

Rather unintuitive. The trick is that your foldr will not produce a value, but rather a function. The list traversal will operate the elements as to produce a function that, when applied to the accumulator, performs the computation you desire.

Lets see a simple example to illustrate how this works. Consider sum foldl (+) 0 [1,2,3] = ((0+1)+2)+3. We may calculate it via foldr as follows.

   foldr ⊕ [1,2,3] id 
-> 1⊕(2⊕(3⊕id))
-> 1⊕(2⊕(id.(+3))
-> 1⊕(id.(+3).(+2))
-> (id.(+3).(+2).(+1))

So when we apply this function to 0 we get

   (id.(+3).(+2).(+1)) 0
=  ((0+1)+2)+3

We began with the identity function and successively changed it as we traversed the list, using ⊕ where,

n ⊕ g = g . (+n)   

Using this intuition, it isn't hard to define a sum with an accumulator via foldr. We built the computation for a given list via foldr ⊕ id xs. Then to calculate the sum we applied it to 0, foldr ⊕ id xs 0. So we have,

foldl (+) 0 xs = foldr ⊕ id xs 0 
               where n ⊕ g = g . (+n)   

or equivalently, denoting n ⊕ g in prefix form by (⊕) n g and noting that (⊕) n g a = (g . (+n)) a = g (a+n),

foldl (+) 0 xs = foldr ⊕ id xs 0
               where (⊕) n g a = g (a+n)   

Note that the ⊕ is your step function, and that you can obtain the generic result you're looking for by substituting a function f for +, and accumulator a for 0.

Next let us show that the above really is correct.

Formal derivation

Moving on to a more formal approach. It is useful, for simplicity, to be aware of the following universal property of foldr.

h []     = e
h (x:xs) = f x (h xs)

      iff 

h = foldr f e

This means that rather than defining foldr directly, we may instead and more simply define a function h in the form above.

We want to define such an h so that,

h xs a = foldl f a xs

or equivalently,

h xs = \a -> foldl f a xs

So lets determine h. The empty case is simple:

h [] = \a -> foldl f a []
     = \a -> a
     = id

The non-empty case results in:

h (x:xs) = \a -> foldl f a (x:xs)
         = \a -> foldl f (f a x) xs
         = \a -> h xs (f a x)
         = step x (h xs)   where step x g = \a -> g (f a x) 
         = step x (h xs)   where step x g a = g (f a x) 

So we conclude that,

h []     = id
h (x:xs) = step x (h xs) where step x g a = g (f a x) 

satisfies h xs a = foldl f a xs

And by the universal property above (noting that the f in the universal property formula corresponds to step here, and e to id) we know that h = foldr step id. Therefore,

h      = foldr step id
h xs a = foldl f a xs
-----------------------
foldl f a xs = foldr step id xs a  
             where step x g a = g (f a x)