Currently I’m sitting the FP101x from edX. A portion of the homework was on foldr and foldl (i.e. right fold and left fold). This got me thinking how I might think about these ideas.

Lets firstly compare the two.

Prelude > foldr (-) 0 [1..4]
-2
Prelude > foldl (-) 0 [1..4]
-10

Why are they different? How do they work?

foldl is probably the intuitive one. It simply “inserts” the function between the elements.

foldl (-) 0 [1..4] -- 0-1-2-3-4 or with parenthesis ((((0-1)-2)-3)-4)

Whilst foldr starts from the right side.

foldr (-) 0 [1..4] -- 1-(2-(3-(4-0)))

J

Now what about in another language, say J

left fold

   -~/|.0,(1+i.4)
_10

right fold

   -/(1+i.4),0
_2

Unpacking J

Lets firstly consider right fold in J since that one is the easier to understand. Reading from right to left we have

    (1+i.4),0
1 2 3 4 0

This creates the array [1..4] append 0 to the end. Next we insert (/) the negative sign (-) between each element of the array, which is actually the right fold as above. i.e.

   -/1 2 3 4 0
_2
   1-(2-(3-(4-0)))
_2

So then what is the left fold doing? We have seen this bit from above 0,(1_i.4), and then we have |. which is the reverse verb.

   |.0,(1+i.4)
4 3 2 1 0

Next we have ~ which to my (extremely poor) understanding in this context is the reflection adverb (this is already doing my head in, someone please correct me if I’m totally wrong). For example:

   -/1 2 3
2

This is interpreted to be as follows:

-/1 2 3

1-(2-3)

On the other hand:

   -~/1 2 3
0

Which would be

-~/1 2 3

((3-2)-1)

Putting this all together yields:

   -~/|.0,(1+i.4)
_10
   ((((0-1)-2)-3)-4)
_10

It is always interesting to examine how different programming languages express the same ideas.