[plt-scheme] implementation of foldl

From: keydana at gmx.de (keydana at gmx.de)
Date: Tue Apr 28 16:09:25 EDT 2009

Hi all,

I am wondering whether the order in which foldl applies the "init"  
argument and the "car" argument to the given combining function is to  
be regarded as specified or as an implementation detail (such that you  
should not rely on it).

Just as an exercise, I was writing reverse with foldl and foldr, and  
noticed that with "my own" _foldr, defined as

(define _foldl
   (lambda (proc initial lst)
     (if (null? lst)
         initial
        (_foldl proc (proc initial (car lst)) (cdr lst)))))


it worked as

(define reverse-fl-1
   (lambda (lst)
     (_foldl (lambda (x y) (cons y x)) '() lst)))


whereas for the PLT version of foldl I need

(define reverse-fl-2
   (lambda (lst)
     (foldl (lambda (x y) (cons x y)) '() lst)))


The documentation for foldl says

"The proc is initially invoked with the first item of each list, and  
the final argument is init."

so the order seems to be specified for PLT scheme (also one example in  
the docs is relying on this); on the other hand I see that in Haskell  
it's the other way round. So now I'm wondering a bit how foldl is to  
be considered, somehow it seems less "universal" than foldr as it  
makes a big difference how it's implemented in a programming language.  
(I was also starting/trying to read "A tutorial on the universality  
and expressiveness of fold" by Graham Hutton, which by fold  
automatically seems to mean foldr.)
I hope my question is not too unclear or chaotic :-)

Thanks for any information,
Sigrid


Posted on the users mailing list.