Как в Racket работают недвоичные Foldl и Foldr? - PullRequest
Новая
       68

Как в Racket работают недвоичные Foldl и Foldr?

1 голос
/ 27 февраля 2020

Я знаком с основными принципами работы и различиями foldl и foldr в одном списке. Однако в Racket вы можете использовать складки в нескольких списках. Например, вы можете найти разницу элементов в двух списках, написав 

; (mapMinus '(3 4) '(1 2)) => '(2 2)
(define (mapMinus lst0 lst1)
  (foldl (λ (hd0 hd1 acc) (cons (- hd0 hd1) acc)) '() lst0 lst1))

Как именно реализации Racket foldl и foldr работают для обработки нескольких списков? Исходный код Racket для foldl доступен на GitHub здесь , но я недостаточно хорошо знаю схему Chez, чтобы понять ее.

Ответы [ 2 ]

1 голос
/ 28 февраля 2020

Я думаю, что вы действительно спрашиваете, как создать функцию variadi c в Scheme / Racket. Ответ дается на https://docs.racket-lang.org/guide/define.html, но позвольте мне привести вам краткий пример: 

(define (foo a b . xs)
  (+ a b (length xs)))

будет эквивалентно 

def foo(a, b, *xs):
  return a + b + len(xs)

в Python. xs здесь это значение списка, содержащее остальные аргументы.

Второй кусок головоломки - как применить функцию variadi c со значением списка. Для этого вы можете использовать apply. Узнайте больше на https://docs.racket-lang.org/guide/application.html#% 28part._apply% 29 . Опять же, вот краткий пример: 

(define (foo a b c) (+ a b c))
(apply foo 1 '(2 3))
;; equivalent to (foo 1 2 3)

будет эквивалентно 

def foo(a, b, c): return a + b + c
foo(1, *[2, 3]) ;; equivalent to foo(1, 2, 3)

С этим создание сгиба, который принимает несколько аргументов, является всего лишь упражнением в программировании: 

(define (my-fold proc accum required-first-list . list-of-optional-lists)
  ... IMPLEMENT FOLD HERE ...)

Обратите внимание, что если вы прочитаете исходный код Racket (который использует схему Chez), вы увидите, что он использует case-lambda вместо непосредственного определения функции. case-lambda - это просто способ сделать код более эффективным для обычного использования свертывания (т. Е. Сворачивания только с одним списком).

1 голос
/ 28 февраля 2020

A fold, работающий с несколькими списками, просто применяет его lambda поэлементно ко всем спискам одновременно. Возможно, его упрощенная реализация (без проверки ошибок и т. Д. c.) Прояснит ситуацию; давайте сравним стандартную реализацию foldr (которую, IMHO, немного проще понять, чем foldl): 

(define (foldr proc init lst)
  (if (null? lst)
      init
      (proc (car lst)
            (foldr proc init (cdr lst)))))

С реализацией, которая принимает несколько списков: 

(define (foldr proc init . lst) ; lst is a list of lists
  (if (null? (car lst)) ; all lists assumed to be of same length
      init
      ; use apply because proc can have any number of args
      (apply proc
             ; append, list are required for building the parameter list
             ; in the right way so it can be passed to (apply proc ...)
             (append (map car lst)
                     ; use apply again because it's a variadic procedure
                     (list (apply foldr proc init (map cdr lst)))))))

Все дополнительный код в версии с несколькими списками предназначен для одновременного применения proc к нескольким элементам, получения текущего элемента каждого списка (map car lst) и продвижения по всем спискам (map cdr lst).

Также реализация должна учитывать, что процедура работает с переменным числом списков, предполагая, что предоставленный lambda получает правильное количество аргументов (количество входных списков + 1). Работает как положено: 

(foldr (lambda (e1 e2 acc)
         (cons (list e1 e2) acc))
       '()
       '(1 2 3)
       '(4 5 6))

=> '((1 4) (2 5) (3 6))
...