Реверс списка через foldr - Lisp

Узнай цену своей работы

Формулировка задачи:

#!/usr/bin/racket
#lang scheme
 
(define (fold-right op init seq)
    (if (null? seq)
        init
        (op (car seq) (fold-right op init (cdr seq)))))
 
(define (fold-left op init seq)
    (define (iter result rest)
        (if (null? rest)
            result
            (iter (op result (car rest)) (cdr rest))))
    (iter init seq))

(define (reverse-r seq)
    (fold-right (lambda (x y) (append y (list x))) '() seq))
 
(display (reverse-r (list 1 2 3 4 5 6 7)))
(newline)
Решил задачу из SICP благодаря какому-то интуитивному представлению о том, как работает этот алгоритм, но толком проанализировать его не получается. Как работает реверс через foldr? Глядя на код, я бы назвал один из аргументов лямбды аккумулятором (скорее всего, это x). Хочу представить работу алгоритма на первых двух итерациях и на последних двух. Вот мое понимание. В свертке лямбда применяется к первому элементу списка и результату свертки хвоста, соответственно x = (car seq), y = (foldr rest). На последнем шаге x = последний элемент списка, y = nil. Что происходит при редукции с конца? В коде (append y (list x)) nil прибавляется к списку, содержащему последний элемент. Далее к результату этой операции прибавляется предпоследний элемент. Но почему nil между предпоследним и последним элементом не разрывает список на две части?

Решение задачи: «Реверс списка через foldr»

textual
Листинг программы
scala> foldRight(List[Int]())(List(1, 2, 3), (x: Int, acc) => acc :+ x))
res0: List[Int] = List(3, 2, 1)

Объяснение кода листинга программы

В данном коде используется функция foldRight для реверса списка. Список, который нужно перевернуть, это List(1, 2, 3). Функция foldRight принимает три аргумента:

  1. foldRight(List[Int]()) - это инициализация аккумулятора, который будет содержать результат. В данном случае аккумулятор инициализируется пустым списком List[Int]().
  2. List(1, 2, 3) - это список, который нужно перевернуть.
  3. (x: Int, acc) => acc :+ x) - это функция, которая определяет, как будет происходить накопление результата. В данном случае функция просто добавляет текущий элемент x в конец аккумулятора acc. Таким образом, foldRight проходит по каждому элементу списка, начиная с последнего, и добавляет его в начало аккумулятора. В результате получается список, перевернутый относительно исходного. В данном случае результатом будет List(3, 2, 1).

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 4.857 из 5
Похожие ответы