Poza nawiasem

W poprzednim wpisie rozwiÄ?zywa??em zadanie 1.3 z Wizard Booka. Polega??o ono na napisaniu funkcji o trzech argumentach, kt??ra zwraca sumÄ? kwadrat??w dw??ch wiÄ?kszych z nich. Zastanawia??em siÄ? r??wnie?? nad zadaniem uog??lnionym, tzn. o funkcji przyjmujÄ?cÄ? dowolnÄ? ilo??Ä? argument??w, kt??ra zwraca sumÄ? kwadrat??w n najwiÄ?kszych z nich. Nie potrafi??em jednak w??wczas wyobraziÄ? sobie implementacji sortowania listy. Okaza??o siÄ? jednak, ??e znowu nie my??la??em rekurencyjnie.

PrzyjÄ???em bowiem, ??e je??eli mam zaimplementowaÄ? sortowanie, to powinienem zaczÄ?Ä? od jednej z prostszych metod, jak np. sortowanie bÄ?belkowe (ang. bubble sort). Mimo usilnych pr??b nie potrafi??em jednak stworzyÄ? niczego, co by??oby przejrzyste i proste. Zagnie??d??one iteracje, indeksowanie tablic i zamiana element??w - elementy idealnie pasujÄ?ce do programowania imperatywnego w ??wiecie zamkniÄ?tych nawias??w wyglÄ?dajÄ? co najmniej dziwnie.

Wreszcie dzisiaj, w trakcie podr????y pociÄ?giem, przypomnia??em sobie o rekurencyjnych metodach sortowania. W przeciÄ?gu godziny na stronach notesu uda??o mi siÄ? zapisaÄ? w Scheme implementacjÄ? algorytmu sortowania przez scalanie (ang. merge sort). Do szczÄ???cia potrzebne by??y mi w zasadzie dwie rzeczy. Pierwsza to ??Ä?czenie dw??ch posortowanych list w jednÄ? posortowanÄ?. Implementacja okaza??a siÄ? ca??kiem prosta. Przede wszystkim, je??eli kt??ra?? z list jest pusta, to wynik r??wny jest drugiej li??cie. W przeciwnym wypadku budujemy nowÄ? listÄ?. Na jej szczyt wk??adamy mniejszy z pierwszych element??w obu list, a resztÄ? budujemy rekurencyjnie wywo??ujÄ?c siebie. Lista, z kt??rej zdjÄ?to pierwszy element zostaje oczywi??cie go w tym wywo??aniu pozbawiona.

(define (merge L1 L2)
  (cond ((null? L1) L2)
        ((null? L2) L1)
        ((< (car L1) (car L2)) (cons (car L1)
                                     (merge L2
                                            (cdr L1))))
        (else (cons (car L2)
                    (merge L1
                           (cdr L2))))))

Operator cons tworzy parÄ? z dw??ch zadanych obiekt??w. Jego zagnie??d??one wywo??ania mogÄ? s??u??yÄ? do tworzenia list. Np. lista (1 2 3) mo??e byÄ? skonstruowana za pomocÄ? wywo??ania (cons 1 (cons 2 (cons 3 ()))).

Nale??y siÄ? te?? s??owo sprostowania. Ostatnim razem do sprawdzania, czy lista jest pusta zdefiniowa??em w??asnÄ? funkcjÄ? empty?. Dzisiaj w otch??aniach dokumentacji dowiedzia??em siÄ? o funkcji null?, kt??ra robi dok??adnie to samo.

Poprawno??Ä? dzia??ania funkcji merge mo??emy ??atwo sprawdziÄ?.

(merge ‘(1 2 3 4 5) ‘(2 4 6))
(1 2 2 3 4 4 5 6)

Przy pomocy apostrofu w zapisie '(1 2 3 4 5) informujemy interpreter, by nie wykonywa?? nastÄ?pujÄ?cej po nim kombinacji. W tym przypadku jest to zwiÄ???lejszy spos??b na zapisanie (list 1 2 3 4).

DrugÄ? rzeczÄ? kluczowÄ? przy implementacji merge sort jest podzia?? listy na dwie czÄ???ci. To zadanie uog??lni??em do funkcji zwracajÄ?cej dowolny kawa??ek listy zawarty pomiÄ?dzy zadanymi indeksami (czyli co?? na wz??r pythonowej metody slice).

; (head L): zwroc liste bez ostatniego elementu
(define (head L)
  (if (= (length L) 1)
      ()
      (cons (car L)
            (head (cdr L)))))
 
(define (slice L start end)
  (if (= start 0)
      (if (> end (- (length L) 1))
          L
          (slice (head L) start end))
      (slice (cdr L) (- start 1) (- end 1))))

Przyk??adowo wiÄ?c dla listy (7 11 13 17 19 23) u??ycie

(slice L 0 2)

zwr??ci (7 11) (czyli element pierwszy i drugi), za??

(slice L 2 5)

zwr??ci (13 17 19) (elementy od trzeciego do sz??stego).

Na podstawie tej funkcji z ??atwo??ciÄ? mo??emy ju?? podzieliÄ? listÄ? na dwie czÄ???ci.

(define (split L index)
  (list (slice L 0 index)
        (slice L index (length L))))

Funkcja split dzieli listÄ? w miejscu wskazanym przez indeks i zwraca listÄ?, kt??rej pierwszym elementem jest lewa czÄ???Ä? zadanej listy, a drugim elementem prawa czÄ???Ä?. W merge sort bÄ?dziemy dzieliÄ? listÄ? dok??adnie w po??owie, dlatego warto zdefiniowaÄ? do tego oddzielnÄ? funkcjÄ?:

(define (split-half L)
  (split L (quotient (length L) 2)))

LewÄ? i prawÄ? czÄ???Ä? listy uzyskujemy wiÄ?c w ten spos??b:

(define (left-half L)
  (car (split-half L)))
 
(define (right-half L)
  (cadr (split-half L)))

(cadr L) jest skr??towym zapisem dla kombinacji (car (cdr L)). I to ju?? wszystko, co jest potrzebne do zapisania algorytmu merge sort.

(define (merge-sort L)
  (if (< (length L) 2)
      L
      (merge (merge-sort (left-half L))
             (merge-sort (right-half L)))))

Czy to nie by??o proste? ;-)

Ostateczne rozwiÄ?zanie uog??lnionego zadania 1.3 wyglÄ?da wiÄ?c nastÄ?pujÄ?co:

; (max L n): zwroc n najwiekszych elementow z listy L
(define (max L n)
  (slice (reverse (merge-sort L)) 0 n))
 
(define (square x)
  (* x x))
 
(define (sum-of-squares L)
  (if (null? L)
      0
      (+ (square (car L))
         (sum-of-squares (cdr L)))))
 
(define (fun L n)
  (sum-of-squares (max L n)))