Maybe it helps to visualize it like this. Instead of computing the sum by using a fold with (+), we just construct data:<div><div><br></div><div><div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">data Expr = N Int</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">          | Expr :+: Expr</span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">          deriving Show</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;"><br></span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">ns :: [Expr]</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">ns = map N [1..3]</span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;"><br>
</span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">lf :: Expr</span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">lf = foldl1 (:+:) ns</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;"><br></span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">rf :: Expr</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><span class="Apple-style-span" style="font-size: small;">rf = foldr1 (:+:) ns</span></span></div><div><br></div><div>For simplicity Iused foldl1 and foldr1, which only work on non-empty lists.<br>
</div><div><br></div><div>(regarding the weird :+: well in Haskell, you can use operators for data constructors when they start with a colon)</div><div><br></div><div>Run this with GHCi, and evaluate lf and rf. You should get</div>
<div><br></div><div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">*Main&gt; lf</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">(N 1 :+: N 2) :+: N 3</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">*Main&gt; rf</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">N 1 :+: (N 2 :+: N 3)</span></div>
</div></div><div><br></div><div>So really, foldl &quot;folds on the left&quot;, because the parentheses are on the left side. Similarly for foldr.</div><div><br></div><div>Does this help?<br></div><div><br></div><div class="gmail_quote">
On Mon, Mar 9, 2009 at 5:46 PM, 7stud <span dir="ltr">&lt;<a href="mailto:bbxx789_05ss@yahoo.com">bbxx789_05ss@yahoo.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
This is an example that shows how foldl and foldr work (from RWH p.93-94):<br>
<br>
foldl (+) 0 (1:2:3:[])<br>
== foldl (+) (0 + 1)             (2:3:[])<br>
== foldl (+) ((0 + 1) + 2)       (3:[])<br>
== foldl (+) (((0 + 1) + 2) + 3) []<br>
==           (((0 + 1) + 2) + 3)<br>
<br>
<br>
foldr (+) 0 (1:2:3:[])<br>
==  1 +           foldr (+) 0 (2:3:[])<br>
==  1 + (2 +      foldr (+) 0 (3:[])<br>
==  1 + (2 + (3 + foldr (+) 0 []))<br>
==  1 + (2 + (3 + 0))<br>
<br>
The book says on p.94:<br>
<br>
-----<br>
The difference between foldl and foldr should be clear from looking at where<br>
the parentheses and the empty list elements show up.  With foldl, the empty<br>
list element is on the left, and all the parentheses group to the left.<br>
With foldr, the zero value is on the right, and the parentheses group to the<br>
right.<br>
----<br>
<br>
Huh?  With foldl, the only empty list element I see is on the right.<br>
<br>
Initially, it looked to me ike they did the same thing, and that the only<br>
difference was the way they called step.  I think &quot;step&quot; is a horrible,<br>
non-descriptive name, so I&#39;m going to use &quot;accFunc&quot; instead:<br>
<br>
foldl calls: accFunc acc x<br>
<br>
foldr calls: accFunc x acc<br>
<br>
So it looks like you can define a function using either one and get the<br>
same result.  Here is a test:<br>
<br>
--I am going to use odd for pfunc and [1, 2, 3] for xs:<br>
<br>
myFilter1 pfunc xs = foldl accFunc [] xs<br>
where accFunc acc x<br>
| pfunc x       = acc ++ [x]<br>
| otherwise     = acc<br>
<br>
myFilter2 pfunc xs = foldr accFunc [] xs<br>
where accFunc x acc<br>
| pfunc x       = acc ++ [x]<br>
| otherwise     = acc<br>
<br>
<br>
*Main&gt; myFilter1 odd [1, 2, 3]<br>
[1,3]<br>
*Main&gt; myFilter2 odd [1, 2, 3]<br>
[3,1]<br>
<br>
Hmmm.  So there is a difference.  foldr appears to grab elements from<br>
the end of the list.  Therefore, to get the same result from the function<br>
that uses foldr, I did this:<br>
<br>
<br>
myFilter3 pfunc xs = foldr accFunc [] xs<br>
where accFunc x acc<br>
| pfunc x       = x : acc<br>
| otherwise     = acc<br>
<br>
<br>
*Main&gt; myFilter3 odd [1, 2, 3]<br>
[1,3]<br>
<br>
But then RWH explains that you would never use foldl in practice because it<br>
thunks the result, which for large lists can overwhelm the maximum memory<br>
alloted for a thunk.  But it appears to me the same thunk problem would<br>
occur with foldr.  So why is foldr used in practice but not foldl?<br>
<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Beginners mailing list<br>