using foldr which are implemented (with lambda - foldr1) vs. (withinout lambda - foldr2) in Scheme

Question

I have two version of foldr implementations

1) foldr1 implementation with lambda

[foldr1 implementation]
(define foldr1
  (lambda (func lst end)
    (if (null? lst)
    end
    (func (car lst)
        (foldr1 func (cdr lst) end)))))

2) foldr2 implementation without lambda

[foldr2 implementation]
 (define (foldr2 func end lst)
   (if (null? lst)
       end
       (func (car lst) 
         (foldr2 func end (cdr lst)))))

basically same behavior, but when implement myFunc using foldr, I have two version of myFunc

... myFunc2 using foldr2(foldr implemented without lambda)...
 (define (myFunc2 proced lst)                            
  (foldr2                                                     
   (lambda (acc x) (cons (proced acc) x))   
   '() 
   lst)
 )

=> works ok.

But myFunc1 (should behave same as myFunc2) :

...myFunc1 using foldr1 (foldr implemented with lambda)...
 (define (myFunc1 proced lst)
  (foldr1 
    (let ((acc x) x) (cons (proced acc)))
    '()
    lst)
  )

what exactly wrong in myFunc1 when using foldr1 which is implemented with lambda?

Answer 1

Actually, both versions of foldr"with lambda" and "without lambda" are the same, the version "without" is just syntactic sugar for the version "with", they're completely equivalent (except for the fact that the parameter's order changed, but that's nothing).

Now, the myFunc1 procedure is a different thing. You're passing the last two parameters in the wrong order, but that's the least of your problems - what you wrote is not equivalent, a let simply returns the value of the last expression and will be evaluated exactly once when foldr is called, whereas a lambda is an anonymous procedure that can receive parameters and will be executed multiple times inside foldr. Even more, the syntax in let is wrong and it won't compile. To put it another way: these two lines mean completely different things and the let version (after fixing the syntax error) will never work as a function parameter for foldr:

(lambda (acc x)  (cons (proced acc) x))    
(let ((acc x) x) (cons (proced acc)))

Perhaps you're confused because a let form can be expressed in terms of lambda, as demonstrated here. But the opposite is not true! you can not replace a lambda with a let... unless it happens to return a lambda, but that's precisely what you're trying to avoid.

Answer 2

So what is a procedure? We know foldr is a procedure but what makes it a procedure? The answer is a lambda form.

(define x 10)             ; second argument to define is 10, so x is 10
x                         ; ==> 10 (surprised?)

(define y (lambda () 10)) ; second argument to define is a lambda form
y                         ; ==> #<procedure:y> (it might vary from implementation to implementation)
(y)                       ; ==> 10

Both x and y are variables, but y is a procedure. That means you cannot call x like (x) since that will produce an error but you can call (y) and it will run whatever is in the body of the lambda.

Now Scheme has a simple way of writing the procedure y. You could just write:

(define (y) 10)           ; it's the same as the y above
y                         ; ==> #<procedure:y> 

Think of it as the simplifications of the English language. We say "It's" instead of "It is" but they mean the same. This is the case for the two ways to write procedures as well. I'll give you 3 more with alternative syntax:

(define sqrt (lambda (x) (* x x)))
(define (sqrt x) (* x x))
(sqrt 10)                  ; ==> 100

(define list (lambda l l))
(define (list . l) l)
(list 1 2 3 4)             ; ==> (1 2 3 4)

;; notice its fold1 as in number 1, not lowercase L
(define fold1 
  (lambda (fun acc lst)
    (let loop ((acc acc) (lst lst))
      (if (null? lst)
          acc
          (loop (fun (car lst) acc) (cdr lst))))))

(define (fold1 fun acc lst)
    (let loop ((acc acc) (lst lst))
      (if (null? lst)
          acc
          (loop (fun (car lst) acc) (cdr lst)))))

(fold1 cons '() '(1 2 3 4))    ; ==> (4 3 2 1)

Now foldr just like fold1 accepts a procedure as it's very first argument. That means you can write:

(foldr (let ()
         (define (my-add a b) (+ a b)) ; remember this is  too
         my-add) ; return my-add
       0 
       '(1 2 3 4 5)) ; ==> 15

But if you just are going to give the procedure name so that you can return it by name. Since the function part of my-add is (lambda (a b) (+ a b)) (do you see it?) why not just put that:

(foldr (lambda (a b) (+ a b)) ; PS: just + would suffice
       0 
       '(1 2 3 4 5)) ; ==> 15

Remember. It's not the lambda form that is sent to the foldr procedure since it is already evaluated and is a procedure. Just like when you evaluate a symbol representing a procedure after defining it. It's pretty much the same as fold1 don't get expressions with cons in it in the expression (fold1 + 0 (cons 1 (cons 2 (cons 3 '())))) since by the time fold1 is applied + is evaluated to #, 0 is evaluated to 0 (numbers self evaluate) and (cons 1 (cons 2 (cons 3 '()))) is evaluated to (1 2 3)