Expanded форму складки в Ракетка

Question

Пример из 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)) 

Выход в Ракетка:

5 193/196 
5 193/196 

Что было бы в полной мере (расширенная) форма foldl и foldr в этом случае? Не следующее:

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

Edit: Я изменил выше вопрос, поскольку осуществление складки Ракетки против Haskell было объяснено в другом вопросе Why is foldl defined in a strange way in Racket?.

Edit: Если я правильно понял ответы ясно, расширенная форма может быть показана очень ясно с помощью модуля «потокового», где появляются заявления в порядке исполнения (_ указует выход из предыдущего оператора):

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 _)) 

выход в обоих случаях одинаков:

5 193/196 
5 193/196 

Это дает правильные ответы (которые различны для foldl и foldr) в следующем примере также:

; 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 

Выход:

2 
2 
-2 
-2 

В общем языке, кажется:

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. 

Answer 1

Haskell's foldr и foldl не являются точными эквивалент Ракету. Кроме того, div является целым делением, поэтому вы должны использовать quotient в Racket. Но даже тогда,

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

Вы можете внимательно прочитать документацию по foldl и foldr работы, но я хотел бы сослаться на документы для 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)) 

Таким образом, становится

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

Answer 2

В DrRacket нажмите правую кнопку мыши на foldl и выберите «Открыть определяющий файл». В списке обеспечения нажмите правой кнопкой мыши еще раз и выберите «Перейти к следующему связанному экрану». Вы увидите это:

(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))])) 

Однако, поскольку у вас есть только один список это первый член в случае лямбда, который является текущим и кулак строка проверяет аргументы и бросать исключения.Вы можете упростить его:

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

Использование правил замещения:

(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 

Я оставлю foldr один в качестве упражнения.

О складках и стандартах

Складки в #!racket является ракеткой специфична. В Scheme, точнее #!r6rs, у вас есть fold-left и fold-right и в отличие от #!racket порядок аргументов слева направо, что делает его более похожим на * новую версию Haskell.

Библиотека списков SRFI-1 использует имена fold и foldr и рассчитывает на тот же порядок аргументов для обоих, точно так же как #!racket. SRFI-1 также поддерживает разные списки длин и останавливается на самом коротком, поэтому он имеет большинство функций. SRFI-1 может быть включен как в #!racket с (require srfi/1), так и с #!r6rs. (import (rnrs :1))