Expanded form of fold in Racket

问题:

Example from http://www.cse.unsw.edu.au/~en1000/haskell/hof.html :

(foldr / 7 (list 34 56 12 4 23))
(foldl / 7 (list 34 56 12 4 23))

Output in Racket:

5 193/196
5 193/196

What would be the full (expanded) form of foldl and foldr in this case? It is not the following:

> (/ (/ (/ (/ (/ 7 34) 56) 12) 4) 23)
1/300288

Edit: I have modified above question since implementation of fold in Racket vs Haskell has been explained in another question Why is foldl defined in a strange way in Racket?.

Edit: If I understand the answers clearly, the expanded form can be shown very clearly using "threading" module, where statements appear in order of execution (_ indicates output of previous statement):

foldl:

(require threading)
; expanded form of (foldl / 7 (list 34 56 12 4 23))
; FROM LEFT TO RIGHT: 
(~> 7
    (/ 34 _)
    (/ 56 _)
    (/ 12 _)
    (/ 4  _)
    (/ 23 _) )

foldr:

; expanded form of (foldr / 7 (list 34 56 12 4 23))
; FROM RIGHT TO LEFT: 
(~> 7
    (/ 23 _)
    (/ 4  _)
    (/ 12 _)
    (/ 56 _)
    (/ 34 _) )

The output in both cases is same:

5 193/196
5 193/196

It gives correct answers (which are different for foldl and foldr) in following example also:

; FROM LEFT TO RIGHT:
(foldl - 0 '(1 2 3 4))
(~> 0
    (- 1 _)  ; 1-0=1
    (- 2 _)  ; 2-1=1
    (- 3 _)  ; 3-1=2
    (- 4 _)) ; 4-2=2

; FROM RIGHT TO LEFT: 
(foldr - 0 '(1 2 3 4))
(~> 0
    (- 4 _)  ; 4-0=4
    (- 3 _)  ; 3-4=-1
    (- 2 _)  ; 2-(-1)=3
    (- 1 _)) ; 1-3=-2

Output:

2
2
-2
-2

In common language, it seems:

The sent function takes 2 arguments, 

the first argument is from the list, one after the other 
(left to right or right to left depending on foldl and foldr), 

the second argument is init first and 
then the output of previous calculation.

回答1:

Haskell's foldr and foldl are not exactly equivalent to Racket's. Also, div is integer division, so you should use quotient in Racket. But even then,

(foldr quotient 7 (list 34 56 12 4 23)) => 8
(foldl quotient 7 (list 34 56 12 4 23)) => quotient: undefined for 0

You could read the documentation carefully on how foldl and foldr work, but I like to refer to the docs for the teaching languages:

(foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base))
(foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base))

So it becomes

(quotient 34 (quotient 56 (quotient 12 (quotient 4 (quotient 23 7)))))
(quotient 23 (quotient 4 (quotient 12 (quotient 56 (quotient 34 7)))))

回答2:

In DrRacket, press the right mouse button on foldl and choose "Open defining file" In the provide list right click again and choose "Jump to the next bound occurance". You'll see 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))]))

However since you only have one list it's the first term in case lambda that is the current and the fist line checks arguments and throw exceptions. You can simplify it to:

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

Using substitution rules:

(foldl / 7 '(34 56 12 4 23))                                  ;==>
(loop 7 '(34 56 12 4 23))                                     ;==>
(loop (/ (car '(34 56 12 4 23)) 7) (cdr '(34 56 12 4 23)))    ;==>
(loop (/ (car '(56 12 4 23)) (/ (car '(34 56 12 4 23)) 7)) (cdr '(56 12 4 23)))    ;==>
(loop (/ (car '(12 4 23)) (/ (car '(56 12 4 23)) (/ (car '(34 56 12 4 23)) 7))) (cdr '(12 4 23)))    ;==>
(loop (/ (car '(4 23)) (/ (car '(12 4 23)) (/ (car '(56 12 4 23)) (/ (car '(34 56 12 4 23)) 7)))) (cdr '(4 23)))    ;==>
(loop (/ (car '(23)) (/ (car '(4 23)) (/ (car '(12 4 23)) (/ (car '(56 12 4 23)) (/ (car '(34 56 12 4 23)) 7))))) (cdr '(23)))    ;==>
(/ (car '(23)) (/ (car '(4 23)) (/ (car '(12 4 23)) (/ (car '(56 12 4 23)) (/ (car '(34 56 12 4 23)) 7)))))    ;==>
(/ 23 (/ 4 (/ 12 (/ 56 (/ 34 7)))))    ;==>
5 193/196

I'll leave the foldr one as an exercise.

About folds and standards

The folds in #!racket are racket specific. In Scheme, more precisely #!r6rs you have fold-left and fold-right and unlike #!racket the argument order from a left to a right changes making it more similar to the *new Haskell version.

SRFI-1 list library uses the names fold and foldr and expect the same argument order for both, just like #!racket. SRFI-1 also supports different length lists and stops at the shortest one so it is the one with most features. SRFI-1 can be included in both #!racket with (require srfi/1)and with #!r6rs. (import (rnrs :1))