[racket] question about foldl implementation

[Will Kurt]

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))

              (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

[Jos Koot]

 

---

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

or (op (car rest) result ) ,

which makes the difference.

DrRacket does according to its docs.

[Noel Welsh]

On Fri, Aug 13, 2010 at 2:53 AM, Will Kurt <wck...@gmail.com> wrote:
> 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.

I don't think there is a canonical implementation. In Racket is seen
as the same function as right fold; it just happens to process the
list in a different order and so can be tail recursive. Hence it has
the same interface. Racket values consistency and clarity in code.

In Haskell left fold is seen as a different function to right fold,
and hence has a different interface. Haskell values confusing code so
Haskell programmers appreciate having different interfaces for very
similar functions (and the type system will catch some errors).

HTH,
N.

PS: Some of the above is not to be taken seriously.
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users

[Will M. Farr]

On Aug 13, 2010, at 4:42 AM, Noel Welsh wrote:

> In Haskell left fold is seen as a different function to right fold,
> and hence has a different interface. Haskell values confusing code so
> Haskell programmers appreciate having different interfaces for very
> similar functions (and the type system will catch some errors).

In seriousness, in Haskell the functions are really different regarding how strict they are, so it maybe makes more sense for them to have different interfaces. (Though, of course, in Racket, they differ in space usage, as Noel pointed out, so the same logic could apply.)

Will

[Joe Marshall]

It seems to me that the Haskell version is better.
The arguments to foldl are these: (procedure accumulator list1 list2 ...)
so it makes sense that the call to procedure take the arguments
in the same order. That is, you end up calling
(procedure accumulator (car list1) (car list2) ...)

rather than
(procedure (car list1) (car list2) ... accumulator)

This means that reverse cannot be defined as (foldl cons '() list),
but rather (foldl rcons '() list) where rcons = (lambda (cdr car)
(cons car cdr))

I think the consistency of keeping the argument list in the same order
trumps the cleverness of a hack definition of reverse (which definition
wouldn't be used anyway). Also, it is more common to see accumulator
arguments earlier in the argument list than the thing being accumulated.

--
~jrm

[Sam Tobin-Hochstadt]

On Fri, Aug 13, 2010 at 3:11 PM, Joe Marshall <jmar...@alum.mit.edu> wrote:
> It seems to me that the Haskell version is better.

The Haskell ordering also has the advantage of fitting with the Typed
Racket type system for variable-arity functions.
--
sam th
sa...@ccs.neu.edu

[Matthias Felleisen]

I privately +1ed Joe, and I all supportive of introducing new folds and phasing out the old ones.

[Jos Koot]

+1,
jos

[Will M. Farr]

+1 from me, too. I always have to check myself to remember that the foldl accumulator argument comes in on the *right*. FWIW, OCaml also does it the Haskell way (foldl accumulator on the left, foldr accumulator on the right).

This also makes the obvious many-argument version more efficient:

(define (foldl kons knil . lists)
(if (ormap null? lists)
knil
(apply foldl kons (apply kons knil (map car lists)) (map cdr lists))))

as opposed to

(define (foldl* kons knil . lists)
(if (ormap null? lists)
knil
(apply foldl* kons (apply kons (append (map car lists) (list knil))) (map cdr lists))))

The extra append is kinda annoying in the foldl* version....

Will

[Will Kurt]

I just wanted to thank all of you for your insightful responses. This has been very useful!

--Will K.