Poza nawiasem

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 (<nazwa funkcji> <argumenty>)
    <zwracana wartosc>)

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 (<nazwa funkcji> <argumenty>)
    <definicje>
    <zwracana wartosc>)

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. ;-)