Схема: обновление списка без использования таких обязательных функций, как набор - PullRequest
Новая
       4

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

0 голосов
/ 11 марта 2020

Я только начал изучать схему, и меня попросили реализовать алгоритм быстрой сортировки в схеме, но нам не разрешено использовать какие-либо императивные функции, такие как set!, и нам не разрешено использовать filter* 1003. *

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

(define quicksort
(lambda (L)
    (cond
        [(or (null? L) (null? (cdr L))) L]
        [else (let ((pivot (car L)) (small '()) (large '()))
                   (do ((i (- (length L) 1) (- i 1)))
                       ((= i 0))
                           (if (< (list-ref L i) pivot)
                               (set! small (cons (list-ref L i) small))
                               (set! large (cons (list-ref L i) large))))
                           (append (quicksort small) (list pivot) (quicksort large)))])))

Этот код работает , но есть ли способ обновить списки small и large без использования set?

Ответы [ 2 ]

3 голосов
/ 11 марта 2020

Если вы не можете использовать set!, вы не можете изменять списки. Вас просят сделать это функционально, без каких-либо мутаций. Вместо изменения списка на месте создайте меньшие, частично отсортированные списки, а затем объедините их, сохранив сортировку.

1 голос
/ 12 марта 2020

Чтобы быть справедливым, быстрая сортировка является действующим алгоритмом, и многие заявили бы, что замена векторов списками изменит его настолько, что больше не будет быстрой сортировкой. Я буду игнорировать это в данный момент.

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

(segment 5 '(5 1 1 3 8 6 4 9 8 5 3 5 3 8 6))
; ==> ((1 1 3 4 3 3) (5 5) (8 6 9 8 8 6))

Конечно, вы сначала делаете простые тесты: 

(segment 5 '(5)) ; ==> (() (5) ())
(segment 5 '(5 1)) ; ==> ((1) (5) ())
(segment 5 '(5 8)) ; ==> (() (5) (8))
(segment 5 '(5 8 1 5)) ; ==> ((1) (5 5) (8))

Порядок результатов в подсписке не важен. например. результат ((3 3 4 3 1 1) (5 5) (6 8 8 9 6 8)) одинаково достаточен и, скорее всего, легче сделать.

Сделав quicksort, сначала проверив, является ли он списком менее чем из 2 элементов, например. (or (null? lst) (null? (cdr lst))) и верните аргумент или создайте 3 сегмента, используя первый элемент в качестве основного, а затем append рекурсию младшего и высшего, а затем добавьте 3 списка вместе, и вы получите их в порядке.

Как вдохновение здесь процедура, которая делится на странные? а не: 

(define (split-odd lst)
  (let loop ((lst lst) (odd '()) (even '()))
    (cond
      ((null? lst) (list odd even))
      ((odd? (car lst)) (loop (cdr lst) (cons (car lst) odd) even))
      (else (loop (cdr lst) odd (cons (car lst) even))))))
(split-odd '(1 2 3 4 5 6))
; ==> ((5 3 1) (6 4 2))
...