0

Taking definition of foldl from Expanded form of fold in Racket , is there any advantage of the first over the second function: 

(define (oldfoldl f init l)
  (let loop ([init init] [l l])   
    (if (null? l)  init
        (loop (f (car l) init) (cdr l)))))

(define (myfoldl f init l)
  (if (null? l) init
      (myfoldl f (f (car l) init) (cdr l)) ))

In other words, are there any advantages of using an inner sub-function? Both give same result: 

(oldfoldl + 0 '(1 2 3 4))
(myfoldl + 0 '(1 2 3 4))

Output: 

10
10

Edit: a third version which uses define instead of let follows. Will it be different: 

(define (myfoldl2 f init l)
  (define (loop [init init] [l l])   
    (if (null? l)  init
        (loop (f (car l) init) (cdr l)) ))
  (loop init l) )
Community
  • 1
  • 1
rnso
  • 23,686
  • 25
  • 112
  • 234
  • Nope, 2nd will probably be faster as `f` is not 'free' (but will probably not be after optimizations). 98% chance both will produce the same optimized code (it will be quite different for debuggable code). – leppie Aug 18 '16 at 17:03
  • As an after-thought I have added another version in edit. – rnso Aug 18 '16 at 17:07
  • @mso: that might or might not generate the same code. A good compiler should easily inline it. Edit: the `define` version expands to a `letrec`, so does the named `let`, so even a shitty compiler should be able to do it. – leppie Aug 18 '16 at 19:13

2 Answers2

3

For the simplified definition you describe, the two forms are effectively completely equivalent. The only difference is that the one that uses direct recursion passes f, init, and l upon each iteration, while the one using named let only passes init and l. However, I would imagine this difference is completely negligible.

However, that simplified version is not the actual foldl function that’s mentioned at the top of the answer, which looks like this:

(define foldl
  (case-lambda
    [(f init l)
     (check-fold 'foldl f init l null)
     (let loop ([init init] [l l])
       (if (null? l) init (loop (f (car l) init) (cdr l))))]
    [(f init l . ls)
     (check-fold 'foldl f init l ls)
     (let loop ([init init] [ls (cons l ls)])
       (if (pair? (car ls)) ; `check-fold' ensures all lists have equal length
           (loop (apply f (mapadd car ls init)) (map cdr ls))
           init))]))

This uses case-lambda, which performs dispatch on argument count, and an internal function called check-fold, which performs argument type checking. Using named let instead of calling foldl recursively avoids performing dispatch and runtime checks upon each iteration, which have much more significant overhead.

Alexis King
  • 43,109
  • 15
  • 131
  • 205
2

Yes. By keeping the variables that doesn't change from consecutive recursions your eyes rest on the ones that matter at the particular line you are looking at.

Using a named let is just a nice way to defining a procedure and then using it, but with the variable and value at the top. That makes is easier to see how it's initialized.

In your examples all of them look ok to me and even the first when a non changing variable gets passed on in consecutive recursions, but for a more complex procedure removing non changing bindings and creating helper procedures help making it easier to understand.

closures/lambdas should be fairly cheap so wrapping an expression in a let/procedure shouldn't have much impact on the speed in most cases.

Language internals usually look a bit more cryptic so I was quite surprised the implementations was so easy. I bet the real work is in rackets optimizer, which benefits our user code as well. The three versions might become indistinguishable in byte code.

Sylwester
  • 47,942
  • 4
  • 47
  • 79