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

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.