1

I am a beginner and I am trying to understand the primitive function foldl/foldr. I read the documentation and tried some things. However, I just cannot grasp its behavior in this case:

(foldl expt 2 '(1 2 3 4))
>> 262144

I think the result should be the same as:

(expt (expt (expt (expt 2 1) 2) 3) 4)
>> 16777216

I can't trace foldl since the function is a primitive. I do not see how the procedure achieves this result. I am using Racket and Dr. Racket.

  • This post may also be helpful: http://stackoverflow.com/questions/39018163/expanded-form-of-fold-in-racket – rnso Nov 13 '16 at 00:53

1 Answers1

3

Your understanding of foldl has the argument order backwards (though that’s understandable, since the argument order of fold/reduce tends to vary somewhat arbitrarily between languages). The correct equivalency is as follows:

> (foldl expt 2 '(1 2 3 4))
262144
> (expt 4 (expt 3 (expt 2 (expt 1 2))))
262144

As a small aside, foldl is built-in to #lang racket/base, but it’s not a primitive in the sense that it is implemented in the runtime. If you are using DrRacket, you can right-click on a use of foldl and select “Open Defining File” to open the module where it’s implemented, which is racket/private/list in this case.

Community
  • 1
  • 1
Alexis King
  • 43,109
  • 15
  • 131
  • 205