1.5-scheme_ds.tex

\documentclass[alsotrans,beameroptions={aspectratio=169}]{beamerswitch}
\usepackage{fprog}

%% кои теми да се включат

% матрици
\newboolfalse{matrices}

% капсулация чрез функционални обекти
\newbooltrue{encapsulation}

% алтернативна реализация на add-assoc
\newboolfalse{altaddassoc}

% дълбоки списъци
\newbooltrue{deeplists}

% графи
\newboolfalse{graphs}

% допълнителни съкратени команди за дълбоките списъци
\newcommand{\hzero}{\textcolor{red}}
\newcommand{\vzero}{\textcolor{orange}}
\newcommand{\hstep}{\textcolor{green}}
\newcommand{\vstep}{\textcolor{cyan}}

\title{Структури от данни в Scheme}
\subtitle{\ifbool{matrices}{матрици, }асоциативни списъци, дървета\ifbool{deeplists}{, дълбоки списъци}{}\ifbool{graphs}{, графи}{}}

\date[25.10–6.11.2024 г.]{25 октомври – 6 ноември 2024 г.}

\lstset{language=Scheme}

\newcommand{\samplegraph}[1][1.2]{%
  \begin{tikzpicture}
    [>=stealth,
    every node/.style=graphnode,
    scale=#1]
    \node (1) at (1,2) {1};
    \node (2) at (3,2.2)   {2};
    \node (3) at (1.9,1.2)     {3};
    \node (4) at (0.8,0.3) {4};
    \node (5) at (2.5,0)   {5};
    \node (6) at (3.5,1.2) {6};
    \graph {
      (1) -> {(2), (3)};
      (2) -> (3);
      (3) -> {(4), (5)};
      (5) -> {(2), (4) ,(6)};
      (6) -> (2);
    };
  \end{tikzpicture}}

% изисквания към графа:
% да не е силно свързан (т.е. да има недостижим връх)
%% 1
% да има път, който се намира само след backtracking
%% 1 -> 2 -> 3 -> 4 <- 3 -> 5
% да има път, който минава през цикъл при първо минаване и пътят се намира едва след backtracking
%% 1 -> 2 -> 3 -> 5 -> 2 -> ... <- 5 -> 6
% да има път, който минава през цикъл, но в цикъла се влиза чак след backtracking, при първо минаване се намира пътя
%% 1 -> 2 -> 3 -> 4 <- 3 -> 5 -> 2 -> ...

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Матрици}

\subsection{Представяне}

\begin{frame}<\switch{matrices}>[fragile]
  \frametitle{Представяне на матрици}
  Можем да представим матрица като списък от списък от елементи:\\
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.5\textwidth}
      \begin{equation*}
        \left(
          \begin{array}{ccc}
            1 & 2 & 3\\
            4 & 5 & 6
          \end{array}
        \right)
      \end{equation*}
    \end{column}
    \begin{column}{0.5\textwidth}
      \vspace{2ex}
      \tt{((1 2 3) (4 5 6))}
    \end{column}
  \end{columns}
  \vspace{2ex}
  \pause
  Проверка за коректност:
  \pause
\begin{lstlisting}
(define (all? p? l)
  (foldr (lambda (x y) (and x y)) #t (map p? l)))

(define (matrix? m)
  (and (list? m)
       (not (null? (car m)))
       (all? list? m)
       (all? (lambda (row) (= (length row)
                             (length (car m)))) m)))
\end{lstlisting}
\end{frame}

\subsection{Операции}

\begin{frame}<\switch{matrices}>[fragile]
  \frametitle{Базови операции}

  Брой редове и стълбове
  \pause
  \onslide<+->
\begin{lstlisting}
(define @\alt<+->{get-rows length)}{(get-rows m) (length m))}@
(define (get-columns m) (length (car m)))
\end{lstlisting}
  \onslide<+->
  Намиране на първи ред и стълб
  \onslide<+->
\begin{lstlisting}
(define @\alt<+->{get-first-row car)}{(get-first-row m) (car m))}@
(define (get-first-column m) (map car m))
\end{lstlisting}
  \onslide<+->
  Изтриване на първи ред и стълб
  \onslide<+->
\begin{lstlisting}
(define @\alt<+->{del-first-row cdr)}{(del-first-row m) (cdr m))}@
(define (del-first-column m) (map cdr m))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{matrices}>[fragile]
  \frametitle{Разширени операции}

  Намиране на ред и стълб по индекс
  \pause
  \onslide<+->
\begin{lstlisting}
(define @\alt<+->{get-row list-ref)}{(get-row m i) (list-ref m i))}@
(define (get-column m i)
  (map (lambda (row) (list-ref row i)) m))
\end{lstlisting}
  \pause
  Транспониране\\
  \pause
  \onslide<+->
  \textbf{Вариант 1 (директна рекурсия):}
\begin{lstlisting}
(define (transpose m)
  (if (null? (get-first-row m)) '()
      (cons (get-first-column m)
            (transpose (del-first-column m)))))
\end{lstlisting}
  \onslide<+->

 \textbf{Вариант 2 (\tt{accumulate}):}
  \begin{overprint}
\begin{lstlisting}
(define (transpose m)
  (accumulate @\rvl{cons} \rvl{'()} \rvl0 \rvl{(- (get-columns m) 1)}@ @\rvl{(lambda (i) (get-column m i))} \rvl{1+}@))
\end{lstlisting}
  \end{overprint}
\end{frame}

\begin{frame}<\switch{matrices}>[fragile]
  \frametitle{Аритметични операции}

  Събиране на матрици
  \pause
\begin{lstlisting}
(define (+vectors v1 v2) (map + v1 v2))
(define (+matrices m1 m2) (map +vectors m1 m2))
\end{lstlisting}
  \pause
  \vspace{2ex}
  Умножение на матрици \pause
  ($c_{i,j} = \vec a_i\cdot \vec b^T_j = \sum_{k=0}^n A_{i,k}B_{k,j}$)
  \pause
  \small
\begin{lstlisting}
(define (*vectors v1 v2) (apply + (map * v1 v2)))@\pause@
(define (*matrices m1 m2)
  (let ((m2t (transpose m2)))
       (map (lambda (row)
              (map (lambda (column) (*vectors row column))
                   m2t))
            m1)))
\end{lstlisting}
\end{frame}

\section{Абстракция със структури от данни}

\subsection{Нива на абстракция}

\begin{frame}[<+->]
  \frametitle{Абстракция със структури от данни}

  \begin{definition}[Абстракция]
    Принцип за разделянето („абстрахирането“) на \emph{представянето} на дадена структура от данни (СД) от нейното \emph{използване}.
  \end{definition}
  \begin{itemize}
  \item основен принцип на обектно-ориентираното програмиране
  \item позволява използването на СД преди представянето ѝ да е уточнено
  \item предимства:
    \begin{itemize}
    \item програмите работят на по-високо концептуално ниво със СД
    \item позволява алтернативни имплементации на дадена СД, подходящи за различни видове задачи
    \item влиянието на промени по представянето е ограничено до операциите, които „знаят“ за него
    \item подобрения при представянето автоматично се разпространяват до по-горните нива на абстракция
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[<+->]
  \frametitle{Пример: рационално число}

  \begin{itemize}
  \item Логическо описание: обикновена дроб
  \item Физическо представяне: наредена двойка от цели числа
  \item Базови операции:
    \begin{itemize}[<.->]
    \item конструиране на рационално число
    \item получаване на числител
    \item получаване на знаменател
    \end{itemize}
  \item Аритметични операции:
    \begin{itemize}[<.->]
    \item събиране, изваждане
    \item умножение, деление
    \item сравнение
    \end{itemize}
  \item Приложни програми
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Нива на абстракция}

  \begin{center}
    \begin{tikzpicture}
      \graph[nodes={
        draw,
        minimum width=24em,
        minimum height=5ex,
        align=center},
      edges={thick,>=stealth},
      grow up sep=4ex] {
      a[as={физическо представяне\\(наредена двойка от цели числа)}] ->
      b[as={базови операции\\(конструктор, селектори за числител и знаменател)}] ->
      c[as={аритметични операции\\(\tt{+}, \tt{-}, \tt{*}, \tt{/}, \tt{=}, \tt{<}, \tt{>}, \tt{<=}, \tt{>=})}] ->
      d[as={приложни програми}]
      };
    \end{tikzpicture}
  \end{center}
\end{frame}

\subsection{Абстракция с наредени двойки}

\begin{frame}[fragile]
  \frametitle{Рационални числа}

  Физическо представяне\\[2ex]
  \begin{center}
    \small
    \begin{tikzpicture}
      \pointcellxx[nodes={minimum width=8em}] a{\text{числител}}{\text{знаменател}}
    \end{tikzpicture}
  \end{center}
  \pause
  Базови операции
  \begin{itemize}[<+->]
  \item \alt<+->{\lst{(define make-rat cons)}}{\lst{(define (make-rat n d) (cons n d))}}
  \item \alt<+->{\lst{(define get-numer car)}}{\lst{(define (get-numer r) (car r))}}
  \item \alt<+->{\lst{(define get-denom cdr)}}{\lst{(define (get-denom r) (cdr r))}}
  \end{itemize}
  \onslide<+->
  \vspace{2ex}
  По-добре:
\begin{lstlisting}
(define (make-rat n d)
   (if (= d 0) (cons n 1) (cons n d)))
\end{lstlisting}
\end{frame}

\begin{frame}<1-3>[label=ratarith,fragile]
  \frametitle{Аритметични операции}

  \sizeboth\footnotesize
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.34\textwidth}
      \vspace{4ex}
      \begin{equation*}
        \frac{n_1}{d_1}\frac{n_2}{d_2} = \frac{n_1n_2}{d_1d_2}
      \end{equation*}
      \vspace{8ex}
      \begin{uncoverenv}<2->
        \begin{equation*}
          \frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1d_2 + n_2d_1}{d_1d_2}
        \end{equation*}
      \end{uncoverenv}
      \vspace{8ex}
      \begin{uncoverenv}<3->
        \begin{equation*}
          \frac{n_1}{d_1} < \frac{n_2}{d_2} \alt<3>{\leftrightarrow}{\alert{\nleftrightarrow}} n_1d_2 < n_2d_1
        \end{equation*}
      \end{uncoverenv}
    \end{column}

    \begin{column}{0.66\textwidth}
\begin{lstlisting}
(define (*rat p q)
  (make-rat
    (* (get-numer p) (get-numer q))
    (* (get-denom p) (get-denom q))))
\end{lstlisting}
      \begin{uncoverenv}<2->
\begin{lstlisting}
(define (+rat p q)
  (make-rat
    (+ (* (get-numer p)
          (get-denom q))
       (* (get-denom p)
          (get-numer q)))
    (* (get-denom p) (get-denom q))))
\end{lstlisting}
      \end{uncoverenv}
      \begin{uncoverenv}<3->
\begin{lstlisting}
(define (<rat p q)
  (< (* (get-numer p) (get-denom q))
     (* (get-numer q) (get-denom p))))
\end{lstlisting}
      \end{uncoverenv}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[label=ratprog,fragile]
  \frametitle{Програми с рационални числа}

  \begin{equation*}
    \sum_{i=0}^n \frac{x^i}{i!}
  \end{equation*}

  \onslide<+->

  \begin{overprint}
\begin{semiverbatim}
(define (my-exp x n)
  (accumulate
    \rvl{+rat} \rvl{(make-rat 0 1)} 0 n
    \rvl{(lambda (i) (make-rat (pow x i) (fact i)))} 1+))
\end{semiverbatim}
  \end{overprint}
\end{frame}

\begin{frame}<1-2>[label=ratnorm,fragile]
  \frametitle{Нормализация}

  \textbf{Проблем:} Числителят и знаменателят стават много големи!\\[2ex]
  \pause
  \textbf{Проблем:} \evalsto{(<rat (make-rat 1 2) (make-rat 1 -2))}{\#t}\\[2ex]
  \pause
  \textbf{Идея:} Да работим с \emph{нормализирани} дроби $\frac p q$, където $p \in \mathbb Z, q \in \mathbb N^+$ и $gcd(p,q) = 1$.
  \pause
\begin{lstlisting}
(define (make-rat n d)
  (if (or (= d 0) (= n 0)) (cons 0 1)
    (let* ((g (gcd n d))
           (ng (quotient n g))
           (dg (quotient d g)))
       (if (> dg 0) (cons ng dg)
                    (cons (- ng) (- dg))))))
\end{lstlisting}
  \pause
  \alert{Не е нужно да правим каквито и да е други промени!}
\end{frame}

\againframe<4>{ratarith}

\againframe<3->{ratnorm}

\subsection{Абстракция със сигнатура}

\begin{frame}[fragile]
  \frametitle{Сигнатура}

  \sizeboth\footnotesize
  \textbf{Проблем:} Не можем да различим СД с еднакви представяния! (рационално число, комплексно число, точка в равнината)\\
  \pause
  \textbf{Идея:} Да добавим „етикет“ на обекта
  \begin{center}
    \begin{tikzpicture}
      \pointcellx a{\texttt{rat}}
      \nextcellxx[nodes={minimum width=8em}] b{\text{числител}}{\text{знаменател}}a
    \end{tikzpicture}
  \end{center}
  \pause
  \vspace{-.5ex}
\begin{lstlisting}
(define (make-rat n d)
  @\alert{(cons 'rat}@
    (if (or (= d 0) (= n 0)) (cons 0 1)
      (let* ((g (gcd n d))
             (ng (quotient n g))
             (dg (quotient d g)))
         (if (> dg 0) (cons ng dg)
                      (cons (- ng) (- dg)))))))
(define get-numer @\alert{cadr}@)
(define get-denom @\alert{cddr}@)
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Проверка за коректност}

  Вече можем да проверим дали даден обект е рационално число:
\begin{lstlisting}
(define (rat? p)
  (and (pair? p) (eqv? (car p) 'rat)
       (pair? (cdr p))
       (integer? (cadr p)) (positive? (cddr p))
       (= (gcd (cadr p) (cddr p)) 1)))
\end{lstlisting}
  \pause
  Можем да добавим проверка за коректност:
\begin{lstlisting}
(define (check-rat f)
  (lambda (p)
    (if (rat? p) (f p) 'error)))

(define get-numer (check-rat cadr))
(define get-denom (check-rat cddr))
\end{lstlisting}
\end{frame}

\subsection{Капсулация}

\begin{frame}<\switch{encapsulation}>[fragile]
  \frametitle{Капсулация на базови операции}

  \textbf{Проблем:} операциите над СД са видими глобално\\[2ex]
  \pause
  \textbf{Идея:} да ги направим „private“
  \pause
\begin{lstlisting}
(define (make-rat n d)
  (lambda (prop)
    (case prop
      ('get-numer n)
      ('get-denom d)
      ('print (cons n d))
      (else 'unknown-prop))))
\end{lstlisting}
  \pause
  \begin{itemize}
  \item \lst{(define r (make-rat 3 5))}
  \item \evalsto{(r 'get-numer)}3
  \item \evalsto{(r 'get-denom)}5
  \item \evalsto{(r 'print)}{(3 . 5)}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{encapsulation}>[fragile]
  \frametitle{Нормализация при капсулация}

\sizeboth\small
\begin{lstlisting}
(define (make-rat n d)
  @\alert{(let* ((d (if (= 0 d) 1 d))}@
         @\alert{(sign (if (> 0 d) 1 -1))}@
         @\alert{(g (gcd n d))}@
         @\alert{(numer (* sign (quotient n g)))}@
         @\alert{(denom (* sign (quotient d g))))}@
   (lambda (prop)
    (case prop
      ('get-numer numer)
      ('get-denom denom)
      ('print (cons numer denom))
      (else 'unknown-prop))))
\end{lstlisting}
  \pause
  \begin{itemize}
  \item \lst{(define r (make-rat 4 6))}
  \item \evalsto{(r 'print)}{(2 . 3)}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{encapsulation}>[fragile]
  \frametitle{Капсулация на операции с аргументи}

\sizeboth\footnotesize
\begin{lstlisting}
(define (make-rat n d)
  (let* ((g (gcd n d))
         (d (if (= 0 d) 1 d))
         (sign (if (> 0 d) 1 -1))
         (numer (* sign (quotient n g)))
         (denom (* sign (quotient d g))))
   (lambda (prop . params)
     (case prop
       ('get-numer numer)
       ('get-denom denom)
       ('print (cons numer denom))
       @\alert{('* (let ((r (car params))) (make-rat (* numer (r 'get-numer))}@
                                             @\alert{(* denom (r 'get-denom)))))}@
       (else 'unknown-prop))))
\end{lstlisting}
\vspace*{-.5ex}
  \pause
  \begin{itemize}
  \item \lst{(define r1 (make-rat 3 5))}
  \item \lst{(define r2 (make-rat 5 2))}
  \item \evalsto{((r1 '* r2) 'print)}{(3 . 2)}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{encapsulation}>[fragile]
  \frametitle{Извикване на собствени операции}

\sizeboth\footnotesize
\begin{lstlisting}
(define (make-rat n d)
  (let* ((g (gcd n d))
         (d (if (= 0 d) 1 d))
         (sign (if (> 0 d) 1 -1))
         (numer (* sign (quotient n g)))
         (denom (* sign (quotient d g))))
   @\alert{(define (self prop . params)}@
     (case prop
       ('get-numer numer)
       ('get-denom denom)
       ('print (cons numer denom))
       ('* (let ((r (car params)))
            (make-rat (* @\alert{(self 'get-numer)}@ (r 'get-numer))
                      (* @\alert{(self 'get-denom)}@ (r 'get-denom)))))
       (else 'unknown-prop)))
   @\alert{self}@))
\end{lstlisting}
  \pause
  Извикването на метод на обект чрез препратка \tt{self} или \tt{this} се нарича \alert{отворена рекурсия}.
\end{frame}

\section{Асоциативни списъци}

\subsection{Дефиниция}

\begin{frame}
  \frametitle{Асоциативни списъци}

  \begin{definition}
    Асоциативните списъци (още: речник, хеш, map) са списъци от наредени двойки \tt(<ключ> \tt. <стойност>\tt). <ключ> и <стойност> може да са произволни S-изрази.
  \end{definition}
  \vspace{2ex}
  \tt{((}$K_1$ \tt. $V_1$\tt) \tt($K_1$ \tt. $V_2$\tt) \ldots \tt($K_n$ \tt. $V_n$\tt{))}\\[2ex]
  \begin{tikzpicture}
    \pointcell{a1}
    \nextcell{a2}{a1}
    \nextdots{a2}
    \dotsnextcell{an}
    \nullptr{annext}

    \pointcellxx[below=2ex of a1]{kv1}{K_1}{V_1}
    \draw[ptr] (a1data) to (kv1data);

    \pointcellxx[below=2ex of a2]{kv2}{K_2}{V_2}
    \draw[ptr] (a2data) to (kv2data);

    \pointcellxx[below=2ex of an]{kvn}{K_n}{V_n}
    \draw[ptr] (andata) to (kvndata);
  \end{tikzpicture}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Примери за асоциативни списъци}

  \begin{itemize}[<+->]
  \item \tt{((1 . 2) (2 . 3) (3 . 4))}
  \item \tt{((a . 10) (b . 12) (c . 18))}
  \item \tt{((l1 1 8) (l2 10 1 2) (l3))}
  \item \tt{((al1 (1 . 2) (2 . 3)) (al2 (b)) (al3 (a . b) (c . d)))}
  \end{itemize}
  \vspace{2ex}
  \onslide<+->
  \textbf{Пример:}
  Създаване на асоциативен списък по списък от ключове и функция:
\begin{lstlisting}
(define (make-alist f keys)
  (map (lambda (x) (cons x (f x))) keys))
\end{lstlisting}
  \onslide<+->
  \evalsto{(make-alist square '(1 3 5))}{((1 . 1) (3 . 9) (5 . 25))}
\end{frame}

\subsection{Операции}

\begin{frame}[fragile]
  \frametitle{Селектори за асоциативни списъци}

  \begin{itemize}[<+->]
  \item \lst{(define (keys alist) (map car alist))}
  \item \lst{(define (values alist) (map cdr alist))}
  \item \tta{(assoc} <ключ> <асоциативен-списък>\tta)
    \begin{itemize}[<.->]
    \item Ако <ключ> се среща сред ключовете на <асоциативен-списък>,
      връща първата двойка \tt(<ключ> \tt. <стойност>\tt)
    \item Ако <ключ> не се среща сред ключовете, връща \tt{\#f}
    \item Сравнението се извършва с \tt{equal?}
    \end{itemize}
  \item \tta{(assv} <ключ> <асоциативен-списък>\tta)
    \begin{itemize}[<.->]
    \item също като \tt{assoc}, но сравнява с \tt{eqv?}
    \end{itemize}
  \item \tta{(assq} <ключ> <асоциативен-списък>\tta)
    \begin{itemize}[<.->]
    \item също като \tt{assoc}, но сравнява с \tt{eq?}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Трансформации над асоциативни списъци}

  \begin{itemize}[<+->]
  \item Изтриване на ключ и съответната му стойност (ако съществува):\\
    \onslide<+->
\begin{lstlisting}
(define (del-assoc key alist)
  (filter (lambda (kv) (not (equal? (car kv) key))) alist))
\end{lstlisting}
  \item Задаване на стойност за ключ (изтривайки старата, ако има такава):\\
    \onslide<+->
\begin{lstlisting}
(define (add-assoc key value alist)
  (cons (cons key value) (del-assoc key alist)))
\end{lstlisting}
    \ifbool{altaddassoc}{
    \begin{itemize}
    \item А ако искаме да запазим реда на ключовете?
    \end{itemize}}{}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{altaddassoc}>[fragile]
  \frametitle{Задаване на стойност за ключ}
\small
  \textbf{Вариант №1 (грозен и по-бърз):}
\begin{lstlisting}
(define (add-assoc key value alist)
   (let ((new-kv (cons key value)))
        (cond ((null? alist) (list new-kv))
              ((eqv? (caar alist) key) (cons new-kv (cdr alist)))
              (else (cons (car alist)
                    (add-assoc key value (cdr alist))))))
\end{lstlisting}
  \pause
  \textbf{Вариант №2 (красив и по-бавен):}
\begin{lstlisting}
(define (add-assoc key value alist)
  (let ((new-kv (cons key value)))
       (if (assv key alist)
           (map (lambda (kv) (if (eq? (car kv) key)
                                 new-kv kv)) alist)
           (cons new-kv alist))))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Задачи за съществуване}

  \textbf{Задача.} Да се намери има ли елемент на l, който удовлетворява p.\\
  \pause
  \textbf{Формула:} $\exists x\in l: p(x)$\\
  \pause
  \textbf{Решение:}
\begin{lstlisting}
(define (search p l)
  (and (not (null? l))
       (or (p (car l)) (search p (cdr l)))))
\end{lstlisting}
  \pause
  \alert{Важно свойство:} Ако \tt p връща „свидетел“ на истинността на свойството $p$ (както например \tt{memv} или \tt{assv}), то \tt{search} също връща този „свидетел“.\\
  \pause
  \textbf{Пример:}
\begin{lstlisting}
(define (assv key al)
  (search (lambda (kv) (and (eqv? (car kv) key) kv)) al))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Задачи за всяко}
  \textbf{Задача.} Всеки елемент на l да се трансформира по дадено правило f.\\
  \pause
  \textbf{Формула:} $\{f(x)\,|\,x \in l \}$\\
  \pause
  \textbf{Решение:} \lst{(map f l)}\\[2ex]
  \pause
  \textbf{Задача.} Да се изберат тези елементи от l, които удовлетворяват p.\\
  \pause
  \textbf{Формула:} $\{x\,|\,x \in l \wedge p(x) \}$\\
  \pause
  \textbf{Решение:} \lst{(filter p l)}\\[2ex]
  \pause
  \textbf{Задача.} Да се провери дали всички елементи на l удовлетворяват p.\\
  \pause
  \textbf{Формула:} $\forall x\in l:\,p(x)$ \pause $\leftrightarrow \neg \exists x\in l:\,\neg p(x)$\\
  \pause
  \textbf{Решение:}
\begin{lstlisting}
(define (all? p? l)
  (not (search (lambda (x) (not (p? x))) l)))
\end{lstlisting}
\end{frame}
\section{Двоични дървета}

\subsection{Представяне}

\begin{frame}[fragile]
  \frametitle{Представяне на двоични дървета}

  Представяме двоични дървета като вложени списъци от три елемента:\\[2ex]
  \begin{columns}[t,onlytextwidth]
    \begin{column}{0.5\textwidth}
      \centering
      \begin{forest} baseline
        [корен [ляво] [дясно]]
      \end{forest}
    \end{column}
    \begin{column}{0.5\textwidth}
      \tt(<корен> <ляво> <дясно>\tt)
    \end{column}
  \end{columns}
  \pause
  \vspace{2ex}
  Пример:
  \begin{columns}[t,onlytextwidth]
    \begin{column}{0.5\textwidth}
      \centering
      \begin{forest} baseline, for tree={circle,draw}
        [1 [2] [3 [4] [5]]]
      \end{forest}
    \end{column}
    \begin{column}{0.5\textwidth}
\begin{verbatim}
(1 (2 () ())
   (3 (4 () ())
      (5 () ())))
\end{verbatim}
    \end{column}
  \end{columns}
\end{frame}

\subsection{Операции}

\begin{frame}[fragile]
  \frametitle{Базови операции}

  Проверка за коректност:
  \pause
\begin{lstlisting}
(define (tree? t)
  (or (null? t)
      (and (list t) (= (length t) 3))
           (tree? (cadr t))
           (tree? (caddr t))))
\end{lstlisting}
  \pause
  Конструктори:
  \pause
\begin{lstlisting}
(define empty-tree '())
(define (make-tree root left right) (list root left right))
\end{lstlisting}
  \pause
  Селектори:
  \pause
\begin{lstlisting}
(define root-tree car)
(define left-tree cadr)
(define right-tree caddr)
(define empty-tree? null?)
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Разширени операции}

  Дълбочина на дърво:
  \pause
\begin{lstlisting}
(define (depth-tree t)
  (if (empty-tree? t) 0
      (1+ (max (depth (left-tree t))
               (depth (right-tree t))))))
\end{lstlisting}
  \pause
  Намиране на поддърво:
  \pause

  \begin{fixedarea}[.4]
    \begin{onlyenv}<4 |trans:0>
\begin{lstlisting}
(define (memv-tree x t)
  (cond ((empty-tree? t) #f)
        ((eqv? x (root-tree t)) t)
        (else (or (memv-tree x (left-tree t))
                  (memv-tree x (right-tree t))))))
\end{lstlisting}
    \end{onlyenv}
    \begin{onlyenv}<5->
\begin{lstlisting}
(define (memv-tree x t)
  (and (not (empty-tree? t))
       (or (and (eqv? x (root-tree t)) t)
           (memv-tree x (left-tree t))
           (memv-tree x (right-tree t)))))
\end{lstlisting}
    \end{onlyenv}
  \end{fixedarea}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Търсене на път в двоично дърво}

  \textbf{Задача:} Да се намери в дървото път от корена до даден възел \tt x.
  \pause
  \begin{fixedarea}[.7]
  \begin{onlyenv}<2 |trans:0>
\begin{lstlisting}
(define (path-tree x t)
  (cond ((empty-tree? t) #f)
        ((eqv? x (root-tree t)) (list x))
        (else (cons#f (root-tree t)
                      (or (path-tree x (left-tree t))
                          (path-tree x (right-tree t)))))))

(define (cons#f h t) (and t (cons h t)))
\end{lstlisting}
  \end{onlyenv}
  \begin{onlyenv}<3->
\begin{lstlisting}
(define (path-tree x t)
  (and (not (empty-tree? t))
       (or (and (eqv? x (root-tree t)) (list x))
           (cons#f (root-tree t)
                   (or (path-tree x (left-tree t))
                       (path-tree x (right-tree t)))))))

(define (cons#f h t) (and t (cons h t)))
\end{lstlisting}
  \end{onlyenv}
\end{fixedarea}
\end{frame}

\section{Дълбоки списъци}

\begin{frame}<\switch{deeplists}>[fragile]
  \frametitle{Работа с дълбоки списъци}

% TODO диаграма на списъка с наредени двойки
\begin{verbatim}
((1 (2)) (((3) 4) (5 (6)) () (7)) 8)
\end{verbatim}
  \textbf{Задача.} Да се преброят в атомите в дълбок списък.\\
  \textbf{Подход:} Обхождане в две посоки: хоризонтално и вертикално
  \pause
  \begin{itemize}[<+->]
  \item \hzero{Хоризонтално дъно:} \rvl{достигане до празен списък \tt{()}}
  \item \vzero{Вертикално дъно:} \rvl{достигане до друг атом}
  \item \hstep{Хоризонтална стъпка:} \rvl{обхождане на опашката \tt{(cdr l)}}
  \item \vstep{Вертикална стъпка:} \rvl{обхождане на главата \tt{(car l)}}
  \end{itemize}
  \vspace{2ex}
  \onslide<+->
  За удобство можем да дефинираме функцията \tt{atom?}:
\begin{lstlisting}
(define (atom? x) (and (not (null? x)) (not (pair? x))))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{deeplists}>[fragile]
  \frametitle{Примери}
  \small
  \textbf{Задача.} Да се преброят в атомите в дълбок списък.\\
  \evalsto{(count-atoms '((1 (2)) (((3) 4) (5 (6)) () (7)) 8))}8
  \pause
\begin{lstlisting}
(define (count-atoms l)
  (cond ((null? l) @\hzero0@)
        ((atom? l) @\vzero1@)
        (else (+ @\vstep{(count-atoms (car l))} \hstep{(count-atoms (cdr l))}@))))
\end{lstlisting}
\vspace{2ex}
  \pause
  \textbf{Задача.} Да се съберат всички атоми от дълбок списък.\\
  \evalsto{(flatten '((1 (2)) (((3) 4) (5 (6)) () (7)) 8))}{(1 2 3 4 5 6 7 8)}
  \pause
\begin{lstlisting}
(define (flatten l)
  (cond ((null? l) @\hzero{'()}@)
        ((atom? l) @\vzero{(list l)}@)
        (else (append @\vstep{(flatten (car l))} \hstep{(flatten (cdr l))}@))))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{deeplists}>[fragile]
  \frametitle{Примери}

  \textbf{Задача.} Да се обърне редът на атомите в дълбок списък.\\
  \evalsto{(deep-reverse '((1 (2)) (((3) 4) (5 (6)) () (7)) 8))}{(8 ((7) () ((6) 5) (4 (3))) ((2) 1))}
  \pause
\begin{lstlisting}
(define (deep-reverse l)
  (cond ((null? l) @\hzero{'()}@)
        ((atom? l) @\vzero{l}@)
        (else (append @\hstep{(deep-reverse (cdr l))}@
                @\vstep{(list (deep-reverse (car l)))}@))))
\end{lstlisting}
\end{frame}

% TODO: диаграма на дълбок списък без наредени двойки
\begin{frame}<\switch{deeplists}>[fragile]
  \frametitle{Свиване на дълбоки списъци}

  \tt{(deep-foldr }<х-дъно> <в-дъно> <операция> <списък>\tt)\\
  \pause
  \onslide<+->
\begin{lstlisting}
(define (deep-foldr op term nv l)
  (cond ((null? l) @\hzero{nv}@)
        ((atom? l) @\vzero{(term l)}@)
        (else (op @\vstep{(deep-foldr op term nv (car l))}@
                  @\hstep{(deep-foldr op term nv (cdr l))}@))))
\end{lstlisting}
  \onslide<+->
\begin{lstlisting}
(define (count-atoms l) (deep-foldr @\rvl+ \rvl{(lambda (x) 1)} \rvl0@ l))
\end{lstlisting}
  \onslide<+->
\begin{lstlisting}
(define (flatten l) (deep-foldr @\rvl{append} \rvl{list} \rvl{'()}@ l))
\end{lstlisting}
  \onslide<+->
  \begin{visibleenv}<12->
\begin{lstlisting}
(define (snoc x l) (append l (list x)))\end{lstlisting}%
  \end{visibleenv}%
\begin{lstlisting}
(define (deep-reverse l) (deep-foldr @\rvl{snoc} \rvl{id} \rvl{'()}@ l))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{deeplists}>[fragile]
  \frametitle{Директна реализация на \tt{deep-foldr}}

  Как работи \tt{deep-foldr}?
  \pause
  \begin{itemize}[<+->]
  \item пуска себе си рекурсивно за всеки елемент на дълбокия списък
  \item при достигане на вертикално дъно (атоми) прилага \tt{term}
  \item и събира резултатите с \tt{op}
  \end{itemize}
  \onslide<+->
  Можем да реализираме \tt{deep-foldr} чрез \tt{map} и \tt{foldr}!
  \onslide<+->
\begin{lstlisting}
(define (branch p? f g) (lambda (x) (p? x) (f x) (g x)))
(define (deep-foldr op term nv l)
  (foldr @\hstep{op} \hzero{nv}@
   (map (branch atom?
                @\vzero{term}@
                @\vstep{(lambda (l) (deep-foldr op term nv l))}@
        l)))
\end{lstlisting}
  \onslide<+->
 \textbf{Задача.} Реализирайте функция за ляво свиване на дълбоки списъци \tt{deep-foldl}.
\end{frame}

\section{Графи}

\subsection{Представяне}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Представяне на графи чрез асоциативни списъци}

  \begin{columns}[t,onlytextwidth]
    \begin{column}{0.7\textwidth}
      \begin{center}
        \samplegraph
      \end{center}
    \end{column}
    \begin{column}{0.3\textwidth}
\begin{semiverbatim}
\alt<2>{((1 2 3)
 (2 3)
 (3 4 5)
 (4)
 (5 2 4 6)
 (6 2))}{((1 . (2 3))
 (2 . (3))
 (3 . (4 5))
 (4 . ())
 (5 . (2 4 6))
 (6 . (2)))}
 \end{semiverbatim}
    \end{column}
  \end{columns}
  \vspace{2ex}
  Асоциативен списък, в който \alert{ключовете} са върховете, а \alert{стойностите} са списъци от техните деца.
\end{frame}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Абстракция за граф}

\begin{lstlisting}
(define @\alt<2>{vertices keys)}{(vertices g) (keys g))}@

(define (children v g)             @\alert{\(\{u|u\leftarrow{}v\}\)}@
  (cdr (assv v g))))

(define (edge? u v g)              @\alert{\(u\stackrel?\rightarrow{}v\)}@
  (memv v (children u g)))

(define (map-children v f g)       @\alert{\(\forall{}u\leftarrow{}v\)}@
  (map f (children v g)))

(define (search-child v f g)       @\alert{\(\exists{}u\leftarrow{}v\)}@
  (search f (children v g)))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Абстракция за граф}

  \sizeboth\footnotesize
  Абстракция чрез капсулация
  \vspace{-.3ex}
\begin{lstlisting}
(define (make-graph g)
  (define (self prop . params)
    (case prop
      ('print g)
      ('vertices (keys g))
      ('children (let ((v (car params)))
                   (cdr (assv v g))))             @\alert{\(\{u|u\leftarrow{}v\}\)}@
      ('edge? (let ((u (car params)) (v (cadr params)))
                (memv v (self 'children u))))     @\alert{\(u\stackrel?\rightarrow{}v\)}@
      ('map-children (let ((v (car params))
                           (f (cadr params)))     @\alert{\(\forall{}u\leftarrow{}v\)}@
                       (map f (self 'children v))))
      ('search-child (let ((v (car params))
                           (f (cadr params)))     @\alert{\(\exists{}u\leftarrow{}v\)}@
                       (search f (self 'children v))))))
  self)
\end{lstlisting}
\end{frame}

\subsection{Задачи}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Локални задачи}

  \small
  \textbf{Задача. }Да се намерят върховете, които нямат деца.\\
  \pause
  \textbf{Решение. }\tt{childless(g)} $ = \{v\;|\;\nexists u \leftarrow v \}$
  \pause
\begin{lstlisting}
(define (childless g)
  (filter (lambda (v) (null? (children v g))) (vertices g)))
\end{lstlisting}
  \pause
  \vspace{2ex}
  \textbf{Задача. }Да се намерят родителите на даден връх.\\
  \pause
  \textbf{Решение. }\tt{parents(v, g)} $ = \{u\;|\;u \rightarrow v \}$
  \pause
\begin{lstlisting}
(define (parents v g)
  (filter (lambda (u) (edge? u v g)) (vertices g)))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Проверка за симетричност}
  \textbf{Задача. }Да се провери дали граф е симетричен.\\
  \pause
  \textbf{Решение. }\tt{symmetric?(g)} $ = \forall u\forall v\leftarrow u: v\rightarrow u$
  \pause
\begin{lstlisting}
(define (symmetric? g)
  (all? (lambda (u)
            (all? (lambda (v) (edge? v u g))
                    (children u g)))
            (vertices g)))
\end{lstlisting}
\end{frame}

\subsection{Обхождане в дълбочина}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Схема на обхождане в дълбочина}

  Обхождане на връх \tt u:
  \begin{itemize}
  \item Обходи последователно всички деца \tt v на \tt u
  \end{itemize}
  \pause
{\small
\begin{lstlisting}
(define (dfs u g)
  (@<функция-за-обработка>@ (lambda (v) (@<действие>@ (dfs v g)))
                          (children u g)))
\end{lstlisting}
}
  \pause
  \begin{itemize}[<+->]
  \item \alert{Имаме ли дъно?}
    \begin{itemize}
    \item Да: при празен списък от деца няма рекурсивно извикване!
    \end{itemize}
  \item \alert{Какво се случва ако графът е цикличен?}
    \begin{itemize}
    \item Програмата също зацикля! Как да се справим с този проблем?
    \item Трябва да помним през кои върхове сме минали!
    \item Два варианта:
      \begin{enumerate}
      \item да помним всички обходени до момента върхове
      \item<+- | alert@+(1)> да помним текущия път
      \end{enumerate}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Търсене на път в дълбочина}

  \sizeboth\small
  \begin{columns}
    \begin{column}{.75\textwidth}
      \textbf{Задача.} Да се намери път от \tt u до \tt v, ако такъв има.\\
      \pause\onslide<+->
      \textbf{Решение.} Има път от \tt u до \tt v, ако:\\[-1ex]
      \begin{itemize}
      \setlength{\itemsep}{0pt}
      \item \tt u = \tt v, или
      \item има дете \tt w $\leftarrow$ \tt u, така че има път от \tt w до \tt v
      \end{itemize}
    \end{column}
    \begin{column}{.25\textwidth}
      \samplegraph[.8]
    \end{column}
  \end{columns}
  \vspace{-4ex}
  \onslide<+->
  \begin{fixedarea}[.51]
    \begin{onlyenv}<6->
\begin{lstlisting}
(define (dfs-path u v g)
  (define (dfs-search path)
    (let ((current (car path)))
      (cond ((eqv? current v) (reverse path))
            ((memv current (cdr path)) #f)
            (else (search-child current
                    (lambda (w) (dfs-search (cons w path))) g))))
  (dfs-search (list u)))
\end{lstlisting}
    \end{onlyenv}
    \begin{onlyenv}<-5 |trans:0>
\begin{lstlisting}
(define (dfs-path u v g)
  (if (eqv? u v) (list u)
      (search-child u (lambda (w)
                         (cons#f u (dfs-path w v g))) g)))
\end{lstlisting}
    \end{onlyenv}
  \end{fixedarea}
  \onslide<+->
  \alert{Директно рекурсивно решение, работи само за ацикличен граф!}\\
  \onslide<+->
  Итеративното натрупване на пътя позволява да правим проверки за цикъл.
\end{frame}

\subsection{Търсене в ширина}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Схема на обхождане в ширина}
  \begin{onlyenv}<1-2| trans:1>
    Обхождане, започващо от връх \tt u:
    \begin{itemize}
    \item Маркира се \tt u за обхождане на ниво 1
    \item За всеки връх \tt v избран за обхождане на ниво $n$:
      \begin{itemize}
      \item Маркират се всички деца \tt w на \tt v за обхождане на
        ниво $n+1$
      \end{itemize}
    \end{itemize}
  \end{onlyenv}%
  \begin{visibleenv}<2-| trans:1-2>%
    \small%
\begin{lstlisting}
(define (bfs u g)
  (define (bfs-level l)
    (if (null? l) @<дъно>@
        (bfs-level
          (@<функция-за-обработка>@ (lambda (v) (children v g))
                                  l))))
  (bfs-level (list u)))
\end{lstlisting}
  \end{visibleenv}
  \begin{onlyenv}<3- | trans:2-3>
    \begin{fixedarea}[.45]
      \begin{onlyenv}<4-8| trans:3>
        \begin{center}
          \samplegraph \hspace{5em}
          \onslide<5->
          \scriptsize
          \begin{forest}
            for tree={graphnode,edge=-Stealth}
            [1
            [2,visible on=<6->
            [3,visible on=<7->
            [4,visible on=<8->]
            [5,visible on=<8->]]]
            [3,visible on=<6->
            [4,visible on=<7->]
            [5,visible on=<7->
            [2,visible on=<8->]
            [4,visible on=<8->]
            [6,visible on=<8->]]]]
          \end{forest}
        \end{center}
      \end{onlyenv}
      \begin{onlyenv}<9-| trans:2>
        \begin{itemize}[<+(8)->]
        \item \alert{Какво се случва ако графът е цикличен?}
          \begin{itemize}
          \item Ако има път: намира го.
          \item Ако няма път: програмата зацикля! Как да се справим с този проблем?
          \item Трябва да помним през кои върхове сме минали!
          \item Нивото трябва да представлява \alert{списък от пътища}
          \end{itemize}
        \end{itemize}
      \end{onlyenv}
    \end{fixedarea}
  \end{onlyenv}
\end{frame}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Разширяване на пътища}

  Удобно е пътищата да са представени като \alert{стек}
  \begin{itemize}
  \item последно посетеният възел е най-лесно достъпен
  \end{itemize}
  \pause
  \begin{columns}[T]
    \begin{column}{0.65\textwidth}
      \evalsto{(extend '(3 1))}{((4 3 1) (5 3 1))}
      \pause
\begin{lstlisting}
(define (extend path)
  (map-children (car path)
     (lambda (w) (cons w path)) g))
\end{lstlisting}
      \pause
      Трябва да филтрираме циклите:
      \pause
\begin{lstlisting}
(define (remains-acyclic? path)
  (not (memv (car path) (cdr path))))

(define (extend-acyclic path)
  (filter remains-acyclic? (extend path))
\end{lstlisting}
    \end{column}
    \begin{column}{0.35\textwidth}
      \onslide<2->
      \samplegraph
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}<\switch{graphs}>[fragile]
  \frametitle{Търсене на път в ширина}

  \sizeboth\footnotesize
  \textbf{Задача.} Да се намери \alert{най-краткият} път от \tt u до \tt v, ако такъв има.\\
  \pause
  \textbf{Решение.} Обхождаме в ширина от \tt u докато намерим ниво, в което има път, завършващ във върха  \tt v.
  \pause
\begin{lstlisting}
(define (bfs-path u v g)
  @\textcolor{black!20}{(define (extend path) ...)}@
  @\textcolor{black!20}{(define (extend-acyclic path) ...)}@
  (define (extend-level level)@\pause@
    (apply append (map extend-acyclic level)))@\pause@
  (define (target-path path)@\pause@
    (and (eqv? (car path) v) path))@\pause@

  (define (bfs-level level)@\pause@
    (and (not (null? level))
         (or (search target-path level)
             (bfs-level (extend-level level)))))@\pause@

  (bfs-level (list (list u))))
\end{lstlisting}
\end{frame}

\end{document}