Функционално Програмиране - Практикум

Тема 1

Основна точка

Най-простата програма на Scheme е само един байт:

> 5
5

На първия ред е показан "кодът" на програмата, а на втория - нейният резултат.

Като цяло програмите на функционалните езици се състоят в изчисляване на дадени изрази. Както може да се досетите стойноста на израза 5 е точно 5 ;-).

Атоми

Това са най-простите изрази на Scheme. Думата "атом" означава "неделим". Пример за атоми са:

5
"Hello"
#t

последното е true.

Комбинации

да видим един пример:

> (+ 2 3)
5
> (+ 2 3 4)
9

Комбинирането на елементи е аналогично на извикването на функция с аргументи в императивните езици. Формално комбинациите се използват по следния начин:
(<комбинатор> <п1> <п2> … <пn>)
Може да си мислим, че комбинаторът е някаква функция (примерно +, sqrt, …) - това почти винаги е вярно.
Основното правило е, че параметрите се изчисляват един след друг в реда на подаването им. Това се нарича основна форма - след малко ще видим и не основна форма.
За пример ще пресметнем следния израз(1)

\begin{align} \frac{\sqrt{5^2 + 7^2}}{8.2} \end{align}

(/ (sqrt (+ (sqr 5) (sqr 7))) (* 8 2))

Какво се случва тука (от гледна точка на интерпретатора)

• интерпретаторът вижда (/ (sqrt (+ (sqr 5) (sqr 7))) (* 8 2)). Трябва да го изчисли - започва да чете в скобите
  • първото нещо е / - интерпретаторът се подготвя да дели
  • (sqrt (+ (sqr 5) (sqr 7)))
    • sqrt
    • следващото нещо, което вижда интерпретаторът е (+ (sqr 5) (sqr 7))). Трябва да го изчисли, влиза в скобите
      • + значи ще събираме
      • (sqr 5) - това трябва да се изчисли
        • sqr - тази функция смята квадрат, можем да я заместим в горния израз със (* 5 5)
        • 5 - стойноста на 5 е 5 (това е атом)
      • ===> (sqr 5) получава стойност 25
      • следващото нещо което вижда интерпретаторът на това ниво е (sqr 7)
        • sqr
        • 7 ===> стойност 7 (атом)
      • ===> (sqr 7) получава стойност 49
    • ===> стойноста на (+ (sqr 5) (sqr 7))) е 74
  • ===> стойноста на (sqrt (+ (sqr 5) (sqr 7))) e 8.602325267042627 (сметнах си го отделно ;-))
  • следващия израз е (* 8 2)
    • * - значи ще умножаваме
    • 8 ===> атома 8
    • 2 ===> атома 2
  • ===> резултатът от (* 8 2) e 16
• ===> резултатът от (/ (sqrt (+ (sqr 5) (sqr 7))) (* 8 2)) е 0.5376453291901642

Следва да напишем любимата функция на всички студенти - факториел

(2)

\begin{align} fact(n)= \begin{cases} 1 & n = 0 \\ n * fact(n-1) & n > 0 \\ \end{cases} \end{align}

Да обърнем този йероглиф в код на Scheme

(define (fact n)
  (if (<= n 0)
      1
      (* n (fact (- n 1))))
)

Хм… поразителна прилика, случайно ли е ;-)

Следващата задача е за решаване на квадратно уравнение:

• да напишем функция, която смята дискриминанта
• да напишем функция, която връща първия корен (по-малкия) на квадратно уравнение, ако няма да върне #f

(3)

\begin{equation} D(a, b, c) = b^2 - 4ac \end{equation}

;Дискриминанта
(define (D a b c)
  (sqrt (- (sqr b)
           (* 4 a c))))

(4)

\begin{align} x1(a, b, c) = \begin{cases} \begin{cases} \begin{cases} \mbox{"all x"} & c = 0\\ \mbox{"no x"} & c \ne 0\\ \end{cases}& b = 0\\ -\frac{b}{c} & b \ne 0\\ \end{cases}& a = 0 \\ \begin{cases} \mbox{"no real x"} & D < 0\\ \min \left\{\frac{-b - \sqrt{D(a, b, c)}}{2a}, \frac{-b + \sqrt{D(a, b, c)}}{2a}\right\} & D \ge 0 \end{cases} & a \ne 0 \end{cases} \end{align}

(let ((<име1> <стойност1>) (<име2> <стойност2>) ... (<имеn> <стойностn)) <израз>)

Тази конструкция ви позволява да изчислите <израз>, като във него използвате <имеi>, което ще получи стойност <стойностi>.
Ама решението е дълго и затоваа… остава за упражнение на читателя :)
(Псст! Ако читателя много го мързи, да погледне тук).

Да се напише функция, която проверява дали 3 числа могат да бъдат страни на 3^{ъгълник}.

(define (is-triangle? a b c)
  (and (> (+ a b) c)
      (> (+ b c) a)
      (> (+ c a) b)
      (> a 0)
      (> b 0)
      (> c 0)
  )
)

Нека сега да проверим дали едно число е просто:
Кога X е просто? Ако съществува i > 1 такова, че X mod i = 0, то X не е просто. Иначе е. Освен това, можем да ограничим i отгоре, защото ако X = i * j, то X се дели както на i, така и на j. Поне едното от двете е по-малко или равно на $\sqrt{x}$, затова можем да търсим само в интервала $\{ 2 ; \sqrt{x} \}$. OK, време е за код:

(define (check_divisor num divisor)
   (if (> (* divisor divisor) num)
         #t
      (if (= 0 (remainder num divisor))
         #f
         (check_divisor num, (+ divisor 1))
      )
   )
)

(define (is_prime? a)
   (check_divisor a 2)
)

За упражнение:
Напишете програма, която (не задължително много бързо) намира комбинация на N елемента K-ти клас.

(5)

\begin{equation} C(N,K) = C(N-1, K) + C(N-1, K-1) \end{equation}

Както и програма, която решава квадратно уравнение по трите му коефицента.
За шестица - напишете програма, която намира хамилтонов път в даден неориентиран граф за полиномиално време.