Understanding fold-left and fold-right in Scheme

Question

So my task is to implement the most basic version of the 'map' function and the 'filter' functions in Scheme using fold-left or fold-right. I am having a really hard time understanding what exactly these functions are doing. Here is what I have:

(define (myMap f l)
    (fold-left (lambda (f a) (f a)) '() l))

(define (myFilter f l)
    (fold-left f '() l))

The bottom one is what I intuitively thought it should be. Apply a filter (say number? to every element of l and put the result in the null list). The top is just completely wrong but I feel like that is more on the right track. Using some kind of lambda function to apply the function to a number?

Here is an example of the output I am looking for:

(myMap sqrt '(4 9 16 25)) ; (2 3 4 5)
(myFilter odd? '(1 2 3 4 5)) ; (1 3 5)

Answer 1

Both fold-left and fold-right reduces one or more list with a reducing procedure from first to last element, but the order it is applied is kept in fold-right while it is reversed in fold-left. It's easily shown if you do the following:

#!r6rs
(import (rnrs))

;; helper for R6RS fold-left since argument order is swapped
(define (xcons d a) 
  (cons a d))

(fold-left xcons '() '(1 2 3 4)) ; ==> (4 3 2 1)
(fold-right cons '() '(1 2 3 4)) ; ==> (1 2 3 4)

The reason I made xcons is that for left-fold the accumulator is the first argument. In SRFI-1 List library fold-left equvivalent is just called fold and has the same argument order as fold-right:

(import (rnrs base)
        (only (srfi :1) fold fold-left))

(fold cons '() '(1 2 3 4))       ; ==> (4 3 2 1)
(fold-right cons '() '(1 2 3 4)) ; ==> (1 2 3 4)

A left fold is tail recursive since it processes the first element and it becomes the accumulator for the next iteration. A right fold need to cons the last element to the accumulator before consing the second last all the way to the first. This means a right fold should be avoided if possible and in many cases where the order of the result or you fold down to a single value (eg. finding max element) a left fold is ok.

In the case of map and filter you expect the result to be in the same order so you need to always use a fold-right.

For a map you need to make a procedure that cons the result of applying the supplied procedure to an element with the accumulator. This is what fold-right needs to get a list in the end. Your current solution doesn't have any cons so you won't get a list.

For a filter you need to make a procedure that cons the original element to the accumulator if the result of the predicate is a true value and just evaluate the accumulator if it isn't.

Since I think this is homework I'll leave you to do the actual implementation. Happy hacking.

Answer 2

Consider the meaning of a fold function: it gets a two argument function, let's call it “iterator”, and a list, and applies repeatedly the iterator to the elements of the list, in this way: at the generic step, the function is called with the current element of the list, and the results of the previous application of the iterator (at the first step the previous result is simply the third parameter of fold).

So, for instance, the fold-right starts from the end of the list and at each “step” iterator is applied in this way:

(iterator current-element previous-result) ;; produces: next result

to produce the result to be “feed” to the next application as right argument. Analogously for the fold-left, the difference is that the function is applied starting from the head of the list, and using the previous result as left argument.

So, if you have to define a map in this way, consider that you have to build a function “iterator” that must be applied in the way described above. That is, the function must apply f to the current element and produce the result which will be used in the next iteration. Since we want to build the list of the results of this application, the body of the iterator could be simply:

(cons (f current-element) previous-result)

and the whole function becomes:

(define (myMap f lst)
  (define (iterator current-element previous-result)
    (cons (f current-element) previous-result))
  (fold-rigth iterator '() lst))

And since this is an exercise, I will left to you the definition of myFilter: this time you must find a suitable body of the iterator such that the current-element is “inserted” in the result only if the function applied to it returns true, otherwise it must be ignored.

Another interesting exercise is to use the fold-left for the two functions. The functions are sligthly more complex given the different order of application of the iterator.

Answer 3

Folds express a preset pattern of recursion. Left fold goes over all elements of a list, left-to-right, transforming the accumulator using a function which combines a current element, and current accumulator, to produce the next value of the accumulator which will be used in the next call to the combining function, like

(fold-left <+> [a,b,c..,n] z) === (n <+> (... <+> (c <+> (b <+> (a <+> z)))...))

Hence,

(define (myMap-lt f lst)
  (fold-left 
    (lambda (elem     ; list's element
             accum    ; accumulator so far
             )
         ( ... (f elem)    ; map applies f on each elem
              ... accum    ; accum holds list-of-results-so-far
                   ... )   ; need to extend it with this elem's result
       ) 
    '()               ; initial value of the accumulator
    lst))

The right fold is similar, though it combines the current element with the result of the recursive processing from the right,

(fold-right <+> [a,b,c..,n] z) === (a <+> (b <+> (c <+> (... <+> (n <+> z)...))))

In both cases the combining function is actually the same here, the functional composition of a cons operation and the f function itself. But one of them will produce the result reversed (which one?). You can address this by a post-processing step of calling reverse.