Reading R Code. The function Reduce. Folds

Among the essential higher-order functions in functional programming (we have already seen map and filter) reduce (aka. fold) is probably the most amazing and powerful. It is the Swiss-Army-knife in functional programmers' hands, sort of. I highly recommend this excellent exposition, about the power and flexibility of fold:

http://www.cs.nott.ac.uk/~pszgmh/fold.pdf

What is fold?

Although fold deserves and probably requires several blog posts, I'll try an elementary presentation suitable to our purposes.

fold is essentially the functional abstraction that corresponds to the very structure of lists.

A list of whatever kind of values, say, type X, is either the empty list or a list constructed from an X and a list of Xs, where by construction I mean the operation of consing X and a list of Xs. For instance (in Lisp):

[1]> (cons 1 (list 2 3))
(1 2 3)

or in Haskell, where : is the Haskell equivalent to the Lispier cons:

Prelude> 1 : [2, 3]
[1,2,3]

Note the self-referential nature of the type description for lists. Any function over lists relies on this self-referential structure, and it will have a natural form, where the recursive call emanates naturally from the type description. So the sketch or template of a function for list of X looks like this [written now in Racket]:

(define (f-for-lox lox)
  (cond [(empty? lox) (...)]
        [else
          (... (first lox)
               (f-for-lox (rest lox)))]))
       

On the other hand, and by stack space efficiency reasons, functions over lists can be written in such a way that the recursive call is in tail position (in a position that ensures that is the last call in the procedure). Observe that f-for-lox, the recursive call in the template above, is not in tail position; instead, the function ending up in place of the last three dots in that template will be in tail position.

I heartily recommend to watch these excellent videos, on which this exposition is mostly based, for a better understanding:

1. https://www.youtube.com/watch?v=Z7qXdkt7yOE
2. https://www.youtube.com/watch?v=nx8BALSH3nY
3. https://www.youtube.com/watch?v=fMqbMiGuQ9c
4. https://www.youtube.com/watch?v=6NyPb8jQROs

Such functions where the recursive call is in tail positions are known as tail-recursive functions and normally written with the aid of a local function that supplies an accumulator. A tail-recursive template for lists has this form:

(define (f-for-lox lox0)
  (local [(define (f-for-lox-acc acc lox)
            (cond [(empty? lox) (... acc)]
                  [else
                    (f-for-lox-acc (... acc (first lox))
                                   (rest lox))]))]
    (f-for-lox-acc ... lox0)))

Or this one, if we change the order of components in the recursive call:

(define (f-for-lox lox0)
  (local [(define (f-for-lox-acc acc lox)
            (cond [(empty? lox) (... acc)]
                  [else
                    (f-for-lox-acc (... (first lox) acc)
                                   (rest lox))]))]
    (f-for-lox-acc ... lox0)))

fold is the function that capture these two abstractions. Accordingly, there are two possible fold functions (the last one with two variants), fold-right that captures the structural recursive procedure, and fold-left that captures the tail-recursive one.

Let's see this. If we fill those templates with more meaningful placeholders, i standing for the initial value, and f standing for a function to combine the contribution of the first element and the contribution of the recursion, and we add them as parameters to the functions, we have this function for the natural recursive template:

(define (fold-right f i lox)
  (cond [(empty? lox) i]
        [else
          (f (first lox)
             (f-for-lox (rest lox)))]))

and this two variants for the two tail-recursive templates:

(define (fold-left-1 f i lox0)
  (local [(define (f-for-lox-acc acc lox)
            (cond [(empty? lox) acc]
                  [else
                    (f-for-lox-acc (f acc (first lox))
                                   (rest lox))]))]
    (f-for-lox-acc i lox0)))


(define (fold-left-2 f i lox0)
  (local [(define (f-for-lox-acc acc lox)
            (cond [(empty? lox) acc]
                  [else
                    (f-for-lox-acc (f (first lox) acc)
                                   (rest lox))]))]
    (f-for-lox-acc i lox0)))

that are precisely fold-right and fold-left, with two variants, respectively.

A careful analysis of those functions enable us to infer their respective signatures.

;; fold-right                :: (X Y -> Y) Y (listof X) -> Y
;; fold-left-1 (1st variant) :: (Y X -> Y) Y (listof X) -> Y
;; fold-left-2 (2nd variant) :: (X Y -> Y) Y (listof X) -> Y

Note, in particular, that fold-right and the second variant of fold-left share the same signature, while the signature for the first variant of fold-left differs due to the different order of arguments in the call to f.

fold-right is basically the same in all functional programming languages, while different languages pick the first version of fold-left (Lisp, Haskell, OCaml, ...) or the second one (SML, Racket, ...) for its implementation of this function.

The difference between the two variants of fold-left have an impact in many cases. Just choose as f a function for which the order of operands matters (a non-commutative function). For instance if f is + the order doesn't matter but if it is - it absolutely matters. Let's consider this for - in all the languages we have mentioned:

# Lisp [reduce is fold-left by default]
[1]> (reduce #'- '(1 2 3 4) :initial-value 0)
-10

# Haskell
Prelude> foldl (-) 0 [1, 2, 3, 4]
-10

# OCaml
# List.fold_left (-) 0 [1; 2; 3; 4] ;;
- : int = -10

While:

# Racket
> (foldl - 0 '(1 2 3 4))
2

# SML
- List.foldl op- 0 [1, 2, 3, 4] ;
val it = 2 : int

[The R's Reduce will be the subject of the next post.]