[racket] question about foldl implementation

  _____  

From: users-bounces at racket-lang.org [mailto:users-bounces at racket-lang.org]
On Behalf Of Will Kurt
Sent: 13 August 2010 03:53
To: users at racket-lang.org
Subject: [racket] question about foldl implementation


For a presentation I'm working on I've been implementing various higher
order functions in javascript. 

When trying to work out the proper foldl implementation I came across
something interesting in Racket

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

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

However when I looked into various other implementations of foldl I came
across very different behavior
Haskell's foldl seems to be implemented like this:
;;haskell-like definition
(define (foldl-haskell func accum lst)
  (if (null? lst)
      accum
      (foldl-haskell func (func accum (car lst)) (cdr lst))))

and yields these results:
> (foldl-haskell cons '() '(1 2 3 4))
((((() . 1) . 2) . 3) . 4)
> (foldl-haskell - 0 '(1 2 3 4))
-10
> 

Unsure which was correct I broke out SICP which uses this definition:
;;sicp version
(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest)) 

or (op (car rest) result ) ,
which makes the difference.
DrRacket does according to its docs.
 
 
 
 

 
 
              (cdr rest))))
  (iter initial sequence))

with these results (same as the haskell-like version):
> (fold-left cons '() '(1 2 3 4))
((((() . 1) . 2) . 3) . 4)
> (fold-left - 0 '(1 2 3 4))
-10
> 

So which of these is the canonical implementation of a left fold? Why the
difference in Racket? 
For pure aesthetics I like the behavior of Racket in the case of cons, but
for '-' the others seems to make more sense.

Any insight into this is greatly appreciated!

Thanks!
--Will Kurt

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100813/3cb2b6b6/attachment.html>