Как написать распаковать с помощью Foldr в схеме?

Question

Это код для unzip функции, закодированной в Схеме

(define (unzip lst)
  (define (firsts lst)
    (if (null? lst)
        '()
        (cons (caar lst)
              (firsts (cdr lst)))))
  (define (seconds lst)
    (if (null? lst)
        '()
        (cons (cdar lst)
              (seconds (cdr lst)))))
  (list (firsts lst) (seconds lst)))

даст нам вывод, подобный этому:

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

Но мне любопытно, как я мог бы реализоватьта же функция unzip с использованием функции Scheme foldr, кто-нибудь может помочь?Действительно заранее спасибо.

Answer 1

Опираясь на ответ Лейфа, в Racket есть больше форм, таких как for/fold, которые обрабатывают некоторые части накопления за вас.Например:

#lang racket

(define (unzip lst)
  (define-values (firsts seconds)
    (for/lists (firsts seconds)
               ([pr (in-list lst)])
      (values (car pr) (cdr pr))))
  (list firsts seconds))

(unzip '((1 . 2) (3 . 4) (5 . 6)))

Answer 2

Самое красивое решение - но без foldr/l

(define (unzip al) (list (map car al) (map cdr al)))

Решение 1 - с foldr

(define (unzip lst)
  (foldr (lambda (next-pair acc) (list (cons (car next-pair)
                                             (car acc))
                                       (cons (cdr next-pair) 
                                             (cadr acc))))
         '(() ())
         lst))

Примечание: В foldr - хотя и не интуитивно - Второй аргумент (и не первый) - это накопленный результат (таким образом теперь переименованный в acc) - который является первым и вторым списком в списке конечных результатов - и p следующая пара в списке.Таким образом, первое в списке результатов - (car acc), а второе - (cadr acc).Я сам неправильно понял это, назвав аргументы функций lambda p1 и p2, думая, что foldr действует на первую и последнюю пару lst.Таким образом, решая ваш вопрос, я лучше понял, что на самом деле означают два аргумента внутренней lambda функции foldr - один - это накопленный результат, а другой - следующий элемент в списке ввода.Однако теперь попробовал foldl: внутренние аргументы lambda находятся в том же порядке, что и в foldr - сначала следующая пара, а затем накопленный результат.

Решение сfoldl

(define (unzip lst)
  (foldl (lambda (p acc) (list (append (car acc) (list (car p)))
                               (append (cadr acc) (list (cdr p)))))
         '(() ())
         lst))

Несколько более эффективное foldl решение

(define (unzip lst)
  (let ((res (foldl (lambda (p acc) (list (cons (car p) (car acc))
                                          (cons (cdr p) (cadr acc))))
                    '(() ())
                    lst)))
    (map reverse res)))

Вместо append, cons поют результати в конце reverse формирование получаемых внутренних списков.

Решение 2 - с foldr

Неэффективно, но помогло найти решение 1 (flatten (list x y)) -> (cons x y):

(define (unzip lst)
  (foldr (lambda (next acc) (list (flatten (list (car next)
                                              (car acc)))
                               (flatten (list (cdr next) 
                                              (cdr acc)))))
         '(() ())
         lst))

Решение 3 - с foldr

Еще более неэффективно - но помогло добраться до решения 2 (append (list x) (list y)) -> (list x y):

(define (unzip lst)
  (foldr (lambda (next acc) (list (flatten (append (list (car next)) 
                                                (list (car acc))))
                               (flatten (append (list (cdr next)
                                                      (cdr acc))))))
         '(() ())
         lst))

хвостовой рекурсивный раствор без foldr/l

(define (unzip alist)    
    (define (.unzip l acc) ; even numbered l as a given
      (cond ((null? l) (map reverse acc)) ; reverse both inner lists
            (else (.unzip (cddr l) (list (cons (car l) (car acc))
                                         (cons (cadr l) (cadr acc)))))))
    (.unzip (flatten alist) '(() ())))

Все дают:

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

Answer 3

Эта простая реализация не использует fold*, map, reverse, flatten или append - и использует хвостовой вызов

(define (unzip xs (return list))
  (if (empty? xs)
      (return empty empty)
      (unzip (cdr xs)
             (lambda (l r)
               (return (cons (caar xs) l)
                       (cons (cdar xs) r))))))

(unzip '((1 . 2) (3 . 4) (5 . 6)))
;; '((1 3 5) (2 4 6))

Answer 4

Поскольку вы использовали тег racket, я дам ответ, используя for/fold, синтаксис которого намного лучше, чем foldr или foldl. ¹

Синтаксис для for/fold примерно такой:

(for/fold <accumulators>
          <iterators>
  <body>)

Мы можем использовать два аккумулятора ret1 и ret2 для хранения каждого из двух списков, а затем собрать их вместе ваккумуляторы #:result форма:

([ret1 '()]
 [ret2 '()]
 #:result (list (reverse ret1) (reverse ret2)))

Итераторы довольно просты:

 ([i (in-list lst)])

И, наконец, организму просто нужно разбить каждую пару и добавить ее в аккумулятор:

(values (cons (car i) ret1)
        (cons (cdr i) ret2))

Итак, все это вместе дает:

(define (unzip lst)
  (for/fold ([ret1 '()]
             [ret2 '()]
             #:result (list (reverse ret1) (reverse ret2)))
            ([i (in-list lst)])
    (values (cons (car i) ret1)
            (cons (cdr i) ret2))))

Как и ожидалось:

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

_{¹ Как минимумна мой взгляд, эти вещи всегда немного субъективны.}