Learning Scheme, trying to implement map

Question

I try to implement map using with fold in Scheme. I referenced this site: [ref1] http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Towards_a_Standard_Library The way I understand about fold => left-associate fold (foldl) folds/iterates from the first element. (forwards) right-associate fold (foldr) folds/iterates from the last element. (backwards) [Q1] Do I understand correctly?

From ref1 : the implementation of foldl, foldr

 `1) foldl (left-associate fold)`
  (define (foldl func accum lst)
   (if (null? lst)
        accum
        (foldl func (func accum (car lst)) (cdr lst))))

2) foldr (right-associate fold)
 (define (foldr func end lst)
   (if (null? lst)
      end
      (func (car lst) (foldr func end (cdr lst)))))

[=>] implement map using fold, ref1 also has map with foldr code, so that's it..

1) map implementation using foldr from ref1.
  (define (map func lst)      
     (foldr (lambda (x y) (cons (func x) y)) '() lst))

**[Q2] map impelementation using foldl from myself** 
  (define (fold-map-left pr list)
    (foldl 
       (lambda (sublist element) (cons (pr element) sublist))
       '() 
       list)
  what I get as the output...
  e.g. (fold-map-left (lambda(n) (expt n n)) '(1 2 3 4)) 
       output => (256 27 4 1): backwards 

• I know that left associate fold folds/iterates backwards, so it will take the last first and put it into output..., then what can I do to make the output in right order ? and Is there anything else wrong in my code?

Answer 1

First things first, I believe your foldl implementation is a bit off, the usual way to implement it in Scheme would be (but make sure to read @JoshuaTaylor's comment to understand the consequences):

(define (foldl func accum lst)
  (if (null? lst)
      accum
      (foldl func
             (func (car lst) accum) ; here's the change
             (cdr lst))))

About the first question: both folds consume the input list from left-to-right, but they differ in the way that the output result is built: foldl accumulates the first input element at the beginning, and then accumulates the second element on top of the result, and so on; if we were building a list as output then the first element would be the last (and test your own implementation of foldl with this example, to see why I say it's a bit off):

(foldl cons '() '(1 2 3 4 5))
=> '(5 4 3 2 1)

On the other hand, foldr advances recursively until it reaches the empty list and then, as the recursion starts unwinding the last element gets accumulated first, and then the second-to-last on top of the result, and so on - thus preserving the same order of the input:

(foldr cons '() '(1 2 3 4 5))
=> '(1 2 3 4 5)

Regarding the second question: It'll be simpler to implement map in terms of foldr, because as we saw before it preserves input order. This is the same as yours, but with better formatting and variable names:

(define (map func lst)
  (foldr (lambda (ele acc)
           (cons (func ele) acc))
         '()
         lst))

But of course, we could use foldl and reverse the result at the end (or alternatively: reverse the list before passing it to foldl):

(define (map func lst)
  (reverse
   (foldl (lambda (ele acc)
            (cons (func ele) acc))
          '()
          lst)))

What's the idea of having both foldl and foldr? It's a trade-off (and make sure to read @ChrisJester-Young's comments for a discussion of the implementation concerns from a performance point of view). foldr will preserve the same order as the input when building the output, but it'll generate a recursive process that runs in space proportional to the size of the input: notice that func is executed after invoking the recursive call.

On the other hand foldl will build the output in reverse order, but it'll generate an iterative process that runs in constant space: notice that there is nothing left to do after invoking the recursive call, so it's tail-recursive and Scheme is optimized for efficiently handling this kind of recursion.