В каком направлении выполняется процедура сгиба в схеме MIT?

Если я хочу перевернуть список в схеме MIT, я могу сделать это с помощью (fold cons '() list), так что если список равен (define lis '(1 2 3 4)), то (fold cons '() lis) дает (4 3 2 1). Есть два вида сгибов, левый и правый, но если я использую (fold-right cons '() lis), я получаю (1 2 3 4), так что простой сгиб не может быть таким. Кроме того, если я использую (fold-left cons '() lis), я получаю ((((() . 1) . 2) . 3) . 4), так что это также не может быть сгибом в исходном примере. какая складка нужна, чтобы перевернуть список?

Я спрашиваю, потому что хочу иметь возможность сделать общую складку, чтобы:

(define ls '((1 2 3) (4 5 6)))
(gen-fold cons '() ls)
=> ((6 5 4) (3 2 1))
(define l2 '(((1 2) (2 3)) ((3 4) (4 5))))
(gen-fold cons '() ls)
=> (((5 4) (4 3)) ((3 2) (2 1)))

Редактировать: чтобы лучше представить вопросы, на этих диаграммах показано вращение списка, которое, как я считаю, происходит, когда вызывается '(fold cons '() '(1 2 3)), предполагая, что fold является модифицированным fold-left в соответствии с Алексисом Кингом:

(define lis (list '(1 2 3))

     cons
    /   \
   1    cons
        /  \
       2   cons
           /  \
          3   '()

(cons lis '())

         cons
        /  \
      cons '()
     /  \
    1   cons
       /   \
      2    cons
           /  \
          3   '()

(fold-left (cons lis '()))

        cons
       /    \
    cons     cons
   /  \      /  \
  2   cons  1   '()
      /  \
     3   '()


        cons
       /    \
    cons     cons
   /  \       /  \
  3   '()    2    cons
                  /   \
                1     '()

   cons
  /  \
 3   cons
     /  \
    2   cons
        /  \
       1   '()

reduce fold scheme mit-scheme
person Anandamide    schedule 04.11.2015    source источник
comment
Базовая среда схемы MIT не включает функцию fold, только fold-left и fold-right. Единственный полу-встроенный fold, о котором я могу думать, это SRFI-1. Включаете ли вы что-нибудь, что могло бы ввести определение для fold?   -  person Alexis King    schedule 04.11.2015
comment
Ну, может показаться, что это встроенная функция, потому что с новой установкой mit-scheme я могу войти и ввести (fold cons '() '(1 2 3)) и получить => (3 2 1) без определения fold   -  person Anandamide    schedule 04.11.2015
comment
какая складка нужна, чтобы перевернуть список? свернуть влево с помощью { cons с перевернутым порядком аргументов }.   -  person Will Ness    schedule 10.09.2020

Ответы (1)


arrow_upward
5
arrow_downward

MIT Scheme не включает функцию fold в свою базовую библиотеку, только fold-left и fold-right. Однако существует функция fold, объявленная SRFI. -1, который поддерживается MIT Scheme и демонстрирует описанное вами поведение.

Функция fold представляет собой левое свертывание, т. е. она накапливает список путем итерации слева направо, но она отличается от функции fold-left MIT Scheme тем, что порядок аргументов процедуры накопления изменен. То есть fold применяет предоставленную процедуру с аргументом-аккумулятором последним, а fold-left применяет процедуру с аргументом-аккумулятором первым.

Чтобы проиллюстрировать это, вот как можно определить fold в терминах fold-left:

(define (fold proc init lst)
  (fold-left (lambda (x acc) (proc acc x)) init lst))

По моему опыту, порядок аргументов fold более распространен среди реализаций Лиспа, тогда как порядок аргументов fold-left более распространен среди других функциональных языков. Аргумент acc передается последним именно по той причине, которую вы обнаружили: это упрощает использование fold с процедурами, подобными cons, которые принимают накопленное значение в качестве второго аргумента.

Кроме того, вы, похоже, перепутали fold-left и fold-right в своем исходном вопросе: именно fold-right возвращает список без изменений, а fold-left возвращает перевернутый набор пар. Если вы понимаете, как определяются fold-left и fold-right, это имеет смысл.

Определенным образом и fold-left, и fold-right перекрывают списки, начиная с слева, поскольку списки Scheme односвязные и не могут быть прочитаны справа. Разница в том, что левое свертывание является итеративным, а правое — рекурсивным.

Левая складка применяет процедуру к каждому элементу один за другим, а затем передает результат следующему приложению. Это приводит к обратному порядку элементов при просмотре как вложенных приложений:

(proc eN ... (proc e1 (proc e0 init)) ...)

Напротив, правая складка применяет процедуру рекурсивно, сохраняя порядок во вложенных приложениях:

(proc e0 (proc e1 ... (proc eN init) ...))

При использовании с cons левая складка меняет местами, но правая складка — это просто тождество.

(Это потенциально более интересно в ленивых языках, таких как Haskell, потому что правильное свертывание не зависит от всего списка, хотя предположительно начинается справа, поэтому оно может работать с бесконечными потоками... однако это гораздо менее актуально в Scheme.)

person Alexis King    schedule 04.11.2015