Uczymy się dodawać

Przeglądając archiwa pewnego lispowego bloga natrafiłem na ciekawe zadanko. Do tego bloga pewnie jeszcze wrócimy, a tymczasem zajmijmy się samym zadaniem:

Zdefiniuj rekurencyjne funkcje LIST+ i (*) LIST- wykonujące operacje “pisemnego” dodawania i odejmowania liczb reprezentowanych przez listy cyfr dziesiętnych, np.:

(LIST+ '(1 2 3) '(6 8)) ==> (1 9 1)

(*) (LIST- '(1 9 1) '(6 8)) ==> (1 2 3)

Zadanie nie jest trudne, ale zanim przedstawię swoje rozwiązanie, kilka słów dotyczących definiowania funkcji w Scheme. Do tej pory wykorzystywałem następujący model:

(define ( )
)

Często jednak zdarza się, że podczas pisania jednej funkcji piszemy dla niej funkcje pomocnicze. Na potrzeby funkcji merge-sort powstały np. right-half, split, czy slice. Definiowanie każdej funkcji w globalnej przestrzeni nazw jest wygodne podczas eksperymentowania, bo można dowolnie zmieniać i przenosić definicje. Jeżeli jednak nasza funkcja jest częścią większego programu, dobrym zwyczajem jest ukrywać wszystkie szczegóły, udostępniając na zewnątrz tylko prosty i zwarty interface. Technikę tę nazywa się black-box abstraction, jako że dany kawałek kodu możemy traktować jako “czarną skrzynkę” - interesuje nas tylko to, jakie wartości przyjmuje na wejściu i jakie wartości zwraca. W związku z tym, że możemy każdą z tych “czarnych skrzynek” oddzielnie przetestować i wymienić w razie potrzeby, ich stosowanie znacznie ułatwia rozwijanie i debugowanie kodu. W Scheme procedury, oprócz kombinacji zwracających wartość, mogą zawierać serię pomocniczych definicji. Wzór definicji funkcji wygląda więc teraz następująco:

(define ( )

)

W taki właśnie sposób zdefiniowałem ogólną metodę list-op, która wykonuje działania “słupkami”, od jedności do najbardziej znaczących cyfr zadanych liczb.

(define (list-op operator)
(define (list-parse L1 L2 carry)
(define (safe-car L)
(if (null? L)
0
(car L)))

(define (safe-cdr L)
(if (null? L)
()
(cdr L)))

(define partial-result
(+ (operator (safe-car L1) (safe-car L2)) carry))

(define current-digit
(modulo partial-result 10))

(define new-carry
(if (< partial-result 0)
(- (quotient partial-result 10) 1)
(quotient partial-result 10)))

(cons current-digit
(if (and (null? L1)
(null? L2))
()
(list-parse (safe-cdr L1)
(safe-cdr L2)
new-carry))))

(lambda (L1 L2)
(cut-zeros (reverse (list-parse (reverse L1)
(reverse L2)
0)))))

(define (cut-zeros L)
(if (or (null? L)
(not (zero? (car L))))
L
(cut-zeros (cdr L))))

(define list+ (list-op +))
(define list- (list-op -))

Prócz tego, że funkcja lisp-op wykorzystuje black-box abstraction, jest ona również tzw. higher-order function, tzn. funkcją, która przyjmuje na wejściu funkcję i zwraca jako wartość inną funkcję. Funkcje te szczegółowo przedstawia pan Sussman w wykładzie 2a.

Funkcję cut-zeros zostawiłem na zewnątrz, bo przyda mi się ona do zdefiniowania funkcji mnożącej dwie zadane liczby reprezentowane jako listy cyfr. Implementację uczyniłem najprostszą na ile to było możliwe. Skoro potrafimy już dodawać i odejmować, mnożenie zdefiniować można następująco:

(define (list* L1 L2)
(if (null? (cut-zeros L2))
()
(list+ L1 (list* L1 (list- L2 '(1))))))

Jak widać, pomnożyć liczbę a przez b to znaczy pomnożyć a przez b-1 i dodać do wyniku a. Jeżeli zaś b jest zerem, to wynikiem mnożenia jest lista pusta (u nas będąca synonimem zera). Implementację dzielenia pozostawiam jako ćwiczenie dla czytelnika. ;-)

Komentuj wpis