<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content="text/html; charset=us-ascii" http-equiv=Content-Type> <META name=GENERATOR content="MSHTML 8.00.7600.16625"></HEAD> <BODY> <DIV dir=ltr align=left><FONT color=#0000ff size=2 face=Arial></FONT> </DIV><BR> <BLOCKQUOTE style="BORDER-LEFT: #0000ff 2px solid; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px" dir=ltr> <DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left> <HR tabIndex=-1> <FONT size=2 face=Tahoma><B>From:</B> users-bounces@racket-lang.org [mailto:users-bounces@racket-lang.org] <B>On Behalf Of </B>Will Kurt<BR><B>Sent:</B> 13 August 2010 03:53<BR><B>To:</B> users@racket-lang.org<BR><B>Subject:</B> [racket] question about foldl implementation<BR></FONT><BR></DIV> <DIV></DIV>For a presentation I'm working on I've been implementing various higher order functions in javascript. <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))<SPAN class=700305406-13082010><FONT color=#0000ff size=2 face=Arial> </FONT></SPAN></DIV></DIV></BLOCKQUOTE> <DIV dir=ltr><FONT face=Arial><FONT size=2><FONT color=#0000ff><SPAN class=700305406-13082010>or <FONT color=#000000 size=3 face="Times New Roman">(op (car rest) result )</FONT><SPAN class=700305406-13082010><FONT color=#0000ff size=2 face=Arial> <FONT color=#000000 size=3 face="Times New Roman">,</FONT></FONT></SPAN></SPAN></FONT></FONT></FONT></DIV> <DIV dir=ltr><SPAN class=700305406-13082010><SPAN class=700305406-13082010>which makes the difference.</SPAN></SPAN></DIV> <DIV dir=ltr><SPAN class=700305406-13082010><SPAN class=700305406-13082010>DrRacket does according to its docs.</SPAN></SPAN></DIV> <DIV dir=ltr><FONT face=Arial><FONT size=2><FONT color=#0000ff><SPAN class=700305406-13082010><FONT color=#0000ff size=2 face=Arial></FONT></SPAN></FONT></FONT></FONT> </DIV> <DIV dir=ltr><FONT face=Arial><FONT size=2><FONT color=#0000ff><SPAN class=700305406-13082010><FONT color=#0000ff size=2 face=Arial></FONT></SPAN></FONT></FONT></FONT> </DIV> <DIV dir=ltr><FONT face=Arial><FONT size=2><FONT color=#0000ff><SPAN class=700305406-13082010><FONT color=#0000ff size=2 face=Arial></FONT></SPAN></FONT></FONT></FONT> </DIV> <DIV dir=ltr><FONT face=Arial><FONT size=2><FONT color=#0000ff><SPAN class=700305406-13082010><FONT color=#0000ff size=2 face=Arial></FONT></SPAN></FONT></FONT></FONT> </DIV> <BLOCKQUOTE style="BORDER-LEFT: #0000ff 2px solid; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px" dir=ltr> <DIV> <DIV><SPAN class=700305406-13082010></SPAN> </DIV> <DIV><SPAN class=700305406-13082010> </SPAN></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></BLOCKQUOTE></BODY></HTML>