Понимание примитивного «foldl» в Racket

Question

Я начинаю, и я пытаюсь понять примитивную функцию foldl/foldr. Я прочитал documentation и попробовал кое-что. Однако, я просто не могу понять его поведение в этом случае:

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

Я думаю, что результат должен быть таким же, как:

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

Я не могу проследить foldl, так как функция является примитивным. Я не вижу, как процедура достигает этого результата. Я использую Racket и Dr. Racket.

Answer 1

Ваше понимание foldl имеет порядок аргументов назад (хотя это понятно, так как порядок аргументов fold/reduce имеет тенденцию vary somewhat arbitrarily between languages). Правильная эквивалентность заключается в следующем:

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

В небольшой стороне, foldlявляется встроенная в #lang racket/base, но это не примитивным в том смысле, что она реализуется в среде выполнения. Если вы используете DrRacket, вы можете щелкнуть правой кнопкой мыши по использованию foldl и выбрать «Open Defining File», чтобы открыть модуль, где он реализован, который в этом случае равен racket/private/list.