[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))
(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
<div>
<p>For a presentation I'm working on I've been implementing various higher order functions in javascript.</p>
<div><br></div>
<div>When trying to work out the proper foldl implementation I came across something interesting in Racket</div>
<div><br></div>
<div>
<div>> (foldl cons '() '(1 2 3 4))</div>
<div>(4 3 2 1)</div>
<div><br></div>
<div>> (foldl - 0 '(1 2 3 4))</div>
<div>2</div>
</div>
<div><br></div>
<div>However when I looked into various other implementations of foldl I came across very different behavior</div>
<div>Haskell's foldl seems to be implemented like this:</div>
<div>
<div>;;haskell-like definition</div>
<div>(define (foldl-haskell func accum lst)</div>
<div> (if (null? lst)</div>
<div> accum</div>
<div> (foldl-haskell func (func accum (car lst)) (cdr lst))))</div>
</div>
<div><br></div>
<div>and yields these results:</div>
<div>
<div>> (foldl-haskell cons '() '(1 2 3 4))</div>
<div>((((() . 1) . 2) . 3) . 4)</div>
<div>> (foldl-haskell - 0 '(1 2 3 4))</div>
<div>-10</div>
<div>> </div>
</div>
<div><br></div>
<div>Unsure which was correct I broke out SICP which uses this definition:</div>
<div>
<div>;;sicp version</div>
<div>(define (fold-left op initial sequence)</div>
<div> (define (iter result rest)</div>
<div> (if (null? rest)</div>
<div> result</div>
<div> (iter (op result (car rest))</div>
<div> (cdr rest))))</div>
<div> (iter initial sequence))</div>
</div>
<div><br></div>
<div>with these results (same as the haskell-like version):</div>
<div>
<div>> (fold-left cons '() '(1 2 3 4))</div>
<div>((((() . 1) . 2) . 3) . 4)</div>
<div>> (fold-left - 0 '(1 2 3 4))</div>
<div>-10</div>
<div>> </div>
</div>
<div><br></div>
<div>So which of these is the canonical implementation of a left fold? Why the difference in Racket? </div>
<div>For pure aesthetics I like the behavior of Racket in the case of cons, but for '-' the others seems to make more sense.</div>
<div><br></div>
<div>Any insight into this is greatly appreciated!</div>
<div><br></div>
<div>Thanks!</div>
<div>--Will Kurt</div>
</div>
RSS Feed