2.4-haskell_lazy.tex

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

% взели ли сме вече вход/изход?
\newbooltrue{io}

% примери за безточково програмиране
\newboolfalse{pointfree}

\title[Лениво оценяване]{Лениво оценяване и програмиране от по-висок ред}

\date{4--11 декември 2024 г.}

\lstset{language=Haskell,style=Haskell}

\newcommand{\lra}{\onslide<+->$\longrightarrow$\xspace}

\begin{document}

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

\section{Лениво оценяване}

\begin{frame}
  \frametitle{Щипка $\lambda$-смятане}

  \renewcommand{\lra}{\onslide<+->\longrightarrow\xspace}
  \begin{itemize}[<+->]
  \item $\lambda$-изрази: $E ::= x \;|\; E_1(E_2) \;|\; \lambda x\, E$
  \item Изчислително правило: $(\lambda x\,E_1)(E_2) \mapsto E_1[x := E_2]$
  \item В какъв ред прилагаме изчислителното правило?
  \item Нека $f := \lambda x\; x!$, $g := \lambda z\;z^2+z$
  \item $g(f(4)) \lra \quad ?$
  \item $g(\underline{f(4)})
    \lra g(\underline{4!})
    \lra \underline{g(24)}
    \lra 24^2 + 24
    \lra 600$
    \begin{itemize}
    \item<16-> оценява се \alert{отвътре навън}
    \item<17-> \alert{стриктно} (апликативно, лакомо) оценяване
    \end{itemize}
  \item $\underline{g(f(4))}
    \lra (\underline{f(4)})^2 + \underline{f(4)}
    \lra (\underline{4!})^2 + \underline{4!}
    \lra 24^2 + 24
    \lra 600$
    \begin{itemize}
    \item<16-> оценява се \alert{отвън навътре}
    \item<17-> \alert{нестриктно} (нормално, лениво) оценяване
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Стриктно и нестриктно оценяване}

  Стриктното оценяване
  \begin{itemize}[<+->]
  \item се използва в повечето езици за програмиране
  \item се нарича още „call-by-value“ (извикване по стойност)
  \item позволява лесно да се контролира редът на изпълнение
  \item пестеливо откъм памет, понеже „пази чисто“
  \end{itemize}
  \onslide<+->
  Нестриктното оценяване
  \begin{itemize}[<+->]
  \item е по-рядко използвано
  \item въпреки това се среща в някаква форма в повечето езици!
    \begin{itemize}
    \item \tt{x = p != nullptr ? p->data : 0;}
    \item \tt{found = i < n \&\& a[i] == x}
    \end{itemize}
  \item нарича се още „call-by-name“ (извикване по име)
  \item може да спести сметки, понеже „изхвърля боклуците“
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Кога мързелът помага}

\begin{lstlisting}[language=Scheme]
(define (f x y) (if (< x 5) x y))
(define (g l)   (f (car l) (cadr l)))
\end{lstlisting}
\pause
\begin{tabular}[t]{l@{}l}
\tt{\underline{(g '(3))}}
&\lra \tt{(f \underline{(car '(3))} (cadr '(3)))}\\
&\lra \tt{(f 3 \underline{(cadr '(3))})}
\lra \alert{Грешка!}
\end{tabular}
\onslide<+->
\begin{lstlisting}
f x y = if x < 5 then x else y
g l   = f (head l) (head (tail l))
\end{lstlisting}
\onslide<+->
\begin{tabular}[t]{l@{}l}
\tt{\underline{g [3]}}
&\lra \tt{\underline{f (head [3]) (head (tail [3]))}}\\
&\lra \tt{if} \underline{\tt{head [3]}} \tt{< 5 then head [3] else head (tail [3])}\\
&\lra \tt{if \underline{3 < 5} then head [3] else head (tail [3])}\\
&\lra \tt{\underline{if True then head [3] else head (tail [3])}}\\
&\lra \tt{\underline{head [3]}}
\lra \tt 3
\end{tabular}
\end{frame}

\begin{frame}
  \frametitle{Теорема за нормализация}

  \begin{itemize}[<+->]
  \item всеки път когато апликативното оценяване дава резултат и нормалното оценяване дава резултат
  \item има случаи, когато нормалното оценяване дава резултат, но апликативното не!
  \item нещо повече:
  \end{itemize}
  \onslide<.->
  \begin{theorem}[за нормализация, Curry]
    Ако има някакъв ред на оценяване на програмата, който достига до резултат, то и с нормална стратегия на оценяване ще достигнем до същия резултат.
  \end{theorem}
  \onslide<+->
  \begin{corollary}
    Ако с нормално оценяване програмата даде грешка или не завърши, то няма да получим резултат с \alert{никоя друга стратегия на оценяване}.
  \end{corollary}
\end{frame}

\begin{frame}
  \frametitle{Извикване при нужда („call-by-need“)}

Ако $g(z) = z^2 + z$, $g(g(g(2))) = ?$
\pause
{\small
\begin{equation*}
  \begin{array}{rl}
  g(g(g(2))) \pause &\mapsto g(g(2))^2 + g(g(2)) \pause\mapsto (g(2)^2+ g(2))^2 + g(2)^2 + g(2) \pause\mapsto\\
  &\mapsto ((2^2+2)^2+2^2+2)+(2^2+2)^2 + 2^2+2 \mapsto \ldots
  \end{array}
\end{equation*}}\pause
Времето и паметта нарастват експоненциално!\\
\pause
\fbox{\textbf{Идея:} $(\lambda x\,E_1)(E_2) \mapsto \lett{x = E_2}{E_1}$}
\pause
{\small
\begin{equation*}
  \begin{array}{rl}
    g(g(g(2))) \pause &\mapsto \lett{x = g(g(2))}{x^2 + x}\pause \mapsto\\
    &\mapsto \lett{y=g(2)}{\lett{x=y^2+y}{x^2 + x}} \pause \mapsto\\
    &\mapsto \lett{z=2}{\lett{y=z^2+z}{\lett{x=y^2+y}{x^2 + x}}} \pause \mapsto\\
    &\mapsto \lett{y=6}{\lett{x = y^2+y}{x^2 + x}} \pause \mapsto\\
    &\mapsto \lett{x=42}{x^2 + x} \mapsto 1806
  \end{array}
\end{equation*}}\pause\vspace{-1.5em}
\begin{itemize}[<+->]
\item Избягва се повторението чрез споделяне на общи подизрази
\item Заместването се извършва чак когато е \alert{абсолютно наложително}
\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Кога се налага оценяване на израз?}

  Във всеки даден момент Haskell оценява някой израз $s$. \pause
  \begin{itemize}[<+->]
  \item ако $s \equiv$ \lst{if} $e$ \lst{then} $e_1$ \lst{else} $e_2$
    \begin{itemize}
    \item първо се оценява $e$
    \item ако оценката е \lst{True}, се преминава към оценката на $e_1$
    \item ако оценката е \lst{False}, се преминава към оценката на $e_2$
    \end{itemize}
  \item ако $s \equiv \tt f\,e_1\,e_2\,\ldots\,e_n$, за \tt f --- $n$-местна примитивна функция:
    \begin{itemize}
    \item оценяват се последователно $e_1,\ldots,e_n$
    \item прилага се примитивната операция над оценките им
    \end{itemize}
  \item нека сега да допуснем, че $s \equiv \tt f\,e$
  \item първо се оценява \tt f, за да разберем как да продължим
  \item ако $\tt f\,x_1\,\ldots\,x_n$ \tt| $g_1$ \tt= $t_1$ \ldots\ \tt| $g_k$ \tt= $t_k$ е дефинирана чрез пазачи:
    \begin{itemize}
    \item тогава \tt f се замества с израза:\\
      \tt{\textbackslash $x_1 \ldots\ x_n$ ->} \lst{if} $g_1$ \lst{then} $t_1$ \lst{else} \ldots\ \lst{if} $g_k$ \lst{then} $t_k$ \lst{else error "..."}
    \end{itemize}
  \item ако \tt f е конструктор (константа), \alert{оценката остава \tt f $e$}
  \item ако \tt{f = \textbackslash $p$ -> $t$}, където $p$ е образец, редът на оценяване зависи от образеца!
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Кога се оценяват изразите при използване на образци?}

  Как се оценява \tt{(\textbackslash $p$ -> $t$) $e$}?\pause
  \begin{itemize}[<+->]
  \item ако $p \equiv c$ е константа
    \begin{itemize}
    \item преминава се към оценката на аргумента $e$
    \item ако се установи че оценката тя съвпада с константата $c$, преминава се към оценката на тялото $t$
    \end{itemize}
  \item ако $p \equiv \tt\_$ е анонимният образец
    \begin{itemize}
    \item преминава се директно към оценката на $t$ \alert{без да се оценява $e$}
    \end{itemize}
  \item ако $p \equiv \tt x$ е променлива
    \begin{itemize}
    \item преминава се към оценка на израза $t$ \alert{като се въвежда локалната дефиниция \tt{x = $e$}}
    \end{itemize}
  \item ако \tt{$p \equiv\,$\tuple p}
    \begin{itemize}
    \item преминава се към оценката на $e$
    \item като се установи, че тя е от вида \tuple e, преминава се към оценката на израза \tt{(\textbackslash $p_1\,p_2\,\ldots\,p_n$ -> $t$) $e_1\,e_2\,\ldots\,e_n$}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Кога се оценяват изразите при използване на образци?}

  Как се оценява \tt{(\textbackslash $p$ -> $t$) $e$}?\pause
  \begin{itemize}[<+->]
  \item ако $p \equiv \tt(p_h\tt:p_t\tt)$
    \begin{itemize}
    \item преминава се към оценката на $e$
    \item ако се установи, че тя е от вида $\tt(e_h\tt:e_t\tt)$, преминава се към оценката на израза \tt{(\textbackslash $p_h\;p_t$ -> $t$) $e_h\;e_t$}
    \end{itemize}
  \item ако $p \equiv $\hlist p
    \begin{itemize}
    \item преминава се към оценката на $e$
    \item ако се установи, че тя е от вида \hlist e, преминава се към оценката на израза \tt{(\textbackslash $p_1\;p_2\;\ldots\;p_n$ -> $t$) $e_1\;e_2\;\ldots\;e_n$}
    \item всъщност е еквивалентно да разгледаме $p$ като $p_1\tt:p_2\tt:\ldots\tt:p_n$\tt{:[]}
    \end{itemize}
  \item ако има няколко равенства за $f$ с използване на различни образци, се търси кой образец пасва отгоре надолу
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Оценяване в Haskell: пример 1}

\begin{lstlisting}
sumHeads (x:xs) (y:ys) = x + y
\end{lstlisting}
\pause
\begin{tabular}{rl}
  &\tt{\underline{sumHeads} [1..10] [5..50]}\\\pause
  \lra& \tt{(\textbackslash(x:xs) -> \textbackslash(y:ys) -> x + y) \underline{[1..10]} [5..50]}\\
  \lra& \tt{\underline{(\textbackslash(x:xs) -> \textbackslash(y:ys) -> x + y) (1:[2..10])} [5..50]}\\
  \lra& \tt{\lett{x=1; xs=[2..10]}{(\textbackslash(y:ys) -> x + y) \underline{[5..50]}}}\\
  \lra& \tt{\lett{x=1; xs=[2..10]}{\underline{(\textbackslash(y:ys) -> x + y) (5:[6..50])}}}\\
  \lra& \tt{\lett{x=1; xs=[2..10]; y=5; ys=[6..50]}{\underline x + \underline y}}\\
  \lra& \tt{\underline{1 + 5}} \lra\;\tt 6
\end{tabular}
\end{frame}

\begin{frame}
  \frametitle{Оценяване в Haskell: пример 2}

  \small
  \begin{tabular}{r@{ }l@{ }l}
    &\multicolumn 2l{\tt{(filter isPrime [4..1000]) \underline{!!} 1}}\\\pause
    \lra&\multicolumn 2l{\tt{(\textbackslash(\_:xs) n -> xs !! (n-1)) \underline{(filter isPrime [4..1000])} 1}}\\
    \lra&\multicolumn 2l{\tt{(\textbackslash(\_:xs) n -> xs !! (n-1)) (\underline{filter} isPrime [4..1000]) 1}}\\
    \lra&\ldots\tt{\underline{(\textbackslash p (z:zs) ->}}&\underline{\tt{if p z then z:filter p zs}}\\
    &&\tt{\underline{else filter p zs) isPrime} [4..1000]}\ldots\\
    \lra&\ldots\tt{\lett{p=isPrime}{}}&\tt{(\textbackslash (z:zs) -> if p z then z:filter p zs}\\
    &&\tt{else filter p zs) \underline{[4..1000]}}\ldots\\
    \lra&\ldots\tt{\lett{p=isPrime}{}}&\underline{\tt{(\textbackslash (z:zs) -> if p z then z:filter p zs}}\\
    &&\underline{\tt{else filter p zs) (4:[5..1000]))}}\ldots\\
    \lra&\multicolumn 2{@{}l}{\ldots\tt{\lett{p=isPrime; z=4; zs=[5..1000]}{}}}\\
    &\multicolumn 2{@{}l}{\tt{if \underline{p z} then z:filter p zs else filter p zs}\ldots}\\
    \lra&\multicolumn 2{@{}l}{\ldots\tt{\lett{p=isPrime; z=4; zs=[5..1000]}{}}}\\
    &\multicolumn 2{@{}l}{\tt{if False then z:filter p zs else \underline{filter p zs}}\ldots}\\
  \end{tabular}
\end{frame}

\begin{frame}
  \frametitle{Оценяване в Haskell: пример 2}

  \small
  \begin{tabular}{r@{ }l@{ }l}
    \lra&\ldots\tt{\underline{(\textbackslash p (z:zs) ->}}&\underline{\tt{if p z then z:filter p zs}}\\
        &&\tt{\underline{else filter p zs) isPrime} [5..1000]}\ldots\\
    \lra&\ldots\tt{\lett{p=isPrime}{}}&\underline{\tt{(\textbackslash (z:zs) -> if p z then z:filter p zs}}\\
        &&\underline{\tt{else filter p zs) (5:[6..1000])}}\ldots\\
    \lra&\multicolumn 2{@{}l}{\tt{\ldots \lett{p=isPrime; z=5; zs=[6..1000]}{}}}\\
        &\multicolumn 2{@{}l}{\tt{if \underline{p z} then z:filter p zs else filter p zs}\ldots}\\
    \lra&\multicolumn 2{@{}l}{\tt{\ldots \lett{p=isPrime; z=5; zs=[6..1000]}{}}}\\
        &\multicolumn 2{@{}l}{\tt{if True then \underline{z:filter p zs} else filter p zs}\ldots}\\
    \lra&\multicolumn 2{@{}l}{\tt{\underline{(\textbackslash(\_:xs) n -> xs !! (n-1)) (5:filter isPrime [6..1000])} 1}}\\
    \lra&\multicolumn 2{@{}l}{\tt{\lett{xs=filter isPrime [6..1000]}{}}\underline{\tt{(\textbackslash n -> xs !! (n-1)) 1}}}\\
    \lra&\multicolumn 2{@{}l}{\tt{\lett{xs=filter isPrime [6..1000]; n=1}{xs \underline{!!} (n-1)}}}\\
    \lra&\multicolumn 2{@{}l}{\tt{\underline{(\textbackslash (y:\_) 0 -> y) (filter isPrime [6..1000])} 0}}
  \end{tabular}
\end{frame}

\begin{frame}
  \frametitle{Оценяване в Haskell: пример 2}

\small
\begin{tabular}{r@{ }l@{ }l}
  \lra&\ldots\tt{\underline{(\textbackslash p (z:zs) ->}}&\underline{\tt{if p z then z:filter p zs}}\\
  &&\tt{\underline{else filter p zs) isPrime} [6..1000]}\ldots\\
  \lra&\ldots\tt{\lett{p=isPrime}{}}&\underline{\tt{(\textbackslash (z:zs) -> if p z then z:filter p zs}}\\
  &&\underline{\tt{else filter p zs) (6:[7..1000])}}\ldots\\
  \lra&\multicolumn 2{@{}l}{\ldots\tt{\lett{p=isPrime; z=6; zs=[7..1000]}{}}}\\
  &\multicolumn 2{@{}l}{\tt{if \underline{p z} then z:filter p zs else filter p zs}\ldots}\\
  \lra&\multicolumn 2{@{}l}{\ldots\tt{\lett{p=isPrime; z=6; zs=[7..1000]}{}}}\\
  &\multicolumn 2{@{}l}{\tt{if False then z:filter p zs else \underline{filter p zs}}\ldots}\\
  \lra&\ldots\tt{\underline{(\textbackslash p (z:zs) ->}}&\underline{\tt{if p z then z:filter p zs}}\\
  &&\tt{\underline{else filter p zs) isPrime} [7..1000]}\ldots\\
  \lra&\ldots\tt{\lett{p=isPrime}{}}&\underline{\tt{(\textbackslash (z:zs) -> if p z then z:filter p zs}}\\
  &&\underline{\tt{else filter p zs) (7:[8..1000])}}\ldots\\
  \lra&\multicolumn 2{@{}l}{\ldots\tt{\lett{p=isPrime; z=7; zs=[8..1000]}{}}}\\
  &\multicolumn 2{@{}l}{\tt{if \underline{p z} then z:filter p zs else filter p zs}\ldots}
\end{tabular}
\end{frame}

\begin{frame}
  \frametitle{Оценяване в Haskell: пример 2}

\begin{tabular}{r@{ }l@{ }l}
  \lra&\multicolumn 2{@{}l}{\ldots\tt{\lett{p=isPrime; z=7; zs=[8..1000]}{}}}\\
  &\multicolumn 2{@{}l}{\tt{if True then \underline{z:filter p zs} else filter p zs} \ldots}\\
  \lra&\multicolumn 2{@{}l}{\underline{\tt{(\textbackslash (y:\_) 0 -> y) (7:filter isPrime [8..1000]) 0}}}\\
  \lra&\multicolumn 2{@{}l}{\tt{\lett{y=7}y}}\\
  \lra&\tt 7
\end{tabular}
\end{frame}

\section{Потоци}

\begin{frame}
  \frametitle{Потоци в Haskell}

  \begin{itemize}[<+->]
  \item Можем да си мислим, че аргументите в Haskell са \textbf{обещания}, които се изпълняват при нужда
  \item В частност, \tt{x:xs = (:) x xs}, където
    \begin{itemize}
    \item \tt x е обещание за глава
    \item \tt{xs} е обещание за опашка
    \end{itemize}
  \item \alert{списъците в Haskell всъщност са потоци!}
  \item можем да работим с безкрайни списъци
    \begin{itemize}
    \item \tt{ones = 1 : ones}
    \item \evalstoinf{length ones}
    \item \evalsto{take 5 ones}{[1,1,1,1,1]}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Генериране на безкрайни списъци}

  \begin{itemize}
  \item \tta[$a$\tta{..}\tta] $\rightarrow$ \tta[$a$\tta, $a+1$\tta, $a+2$\tta,\ldots\tta]
  \item \textbf{Примери:}
    \begin{itemize}
    \item \tt{nats = [0..]}
    \item \evalsto{take 5 [0..]}{[0,1,2,3,4]}
    \item \evalsto{take 26 ['a'..]}{\ "abcdefghijklmnopqrstuvwxyz"}
    \end{itemize}
  \item Синтактична захар за \tt{enumFrom from}
    \pause
  \item \tta[$a$\tta, $a+\Delta x$ \tta{..}\tta] $\rightarrow$ \tta[$a$\tta, $a+\Delta x$\tta, $a + 2\Delta x$\tta, \ldots \tta]
  \item \textbf{Примери:}
    \begin{itemize}
    \item \tt{evens = [0,2..]}
    \item \evalsto{take 5 evens}{[0,2,4,6,8]}
    \item \evalsto{take 7 ['a','e'..]}{\ "aeimquy"}
    \end{itemize}
  \item Синтактична захар за \tt{enumFromThen from then}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Генериране на безкрайни списъци}

  \begin{itemize}[<+->]
  \item \lst{repeat :: a -> [a]}
    \begin{itemize}
    \item създава безкрайния списък \lst{[x,x,...]}
    \item \lst{repeat x = [x,x..]}
    \item \lst{repeat x = x : repeat x}
    \item \lst{replicate n x = take n (repeat x)}
    \end{itemize}
  \item \lst{cycle :: [a] -> [a]}
    \begin{itemize}
    \item \evalsto{cycle [1,2,3]}{[1,2,3,1,2,3,...]}
    \item \lst{cycle l = l ++ cycle l}
    \item създава безкраен списък повтаряйки подадения (краен) списък
    \end{itemize}
  \item \lst{iterate :: (a -> a) -> a -> [a]}
    \begin{itemize}
    \item \lst{iterate f z} създава безкрайния списък \lst{[z,f(z),f(f(z)),...]}
    \item \lst{iterate f z = z : iterate f (f z)}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Отделяне на безкрайни списъци}

  \begin{overlayarea}{\textwidth}{15em}
    Отделянето на списъци работи и за безкрайни списъци.\pause
    \begin{itemize}[<+->]
    \item \tt{oddSquares = \rvl{[ x\^{}2 | x <- [1,3..] ]}}
    \item {\small\tt{twins = \rvl{[ (x,x+2) | x <- [3,5..], isPrime x, isPrime
          (x+2) ]}}}
    \item \tt{pairs = \rvl{[ (x,y) | x <- [0..], y <- [0..x - 1] ]}}
    \item \tt{pythagoreanTriples = \rvl{
          \begin{tabular}[t]{ll}
            [ (a,b,c) | &c <- [1..],\\
                        &b <- [1..c-1],\\
                        &a <- [1..b-1],\\
                        &a\^{}2 + b\^{}2 == c\^{}2,\\
                        &gcd a b == 1]
          \end{tabular}}}
    \end{itemize}
  \end{overlayarea}
\end{frame}



\begin{frame}
  \frametitle{Функции от по-висок ред над безкрайни списъци}

  Повечето функции от по-висок ред работят и над безкрайни списъци!
  \begin{itemize}[<+->]
  \item \lst{powers2 = 1 : map (*2) powers2}
  \item \lst{notdiv k = filter (\\x -> x `mod` k > 0) [1..]}
  \item \lst{fibs = 0:1:zipWith (+) fibs (tail fibs)}
  \item \evalstop{foldr (+) 0 [1..]}{...}
    \begin{itemize}
    \item \alert{Внимание:} \lst{foldr} не работи над безкрайни списъци с операции, които изискват оценка на десния си аргумент!
    \item \lst{triplets = iterate (map (+3)) [3,2,1]}
    \item \evalsto{take 3 triplets}{[[3,2,1],[6,5,4],[9,8,7]]}
    \item \evalstop{take 5 (foldr (++) [] triplets)}{[3,2,1,6,5]}
    \item \evalstop{take 5 (foldl (++) [] triplets)}{...}
    \item \alert{\lst{foldl} не може да работи с безкрайни списъци!}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{io}>[fragile]
  \frametitle{Ленив вход и изход}

  \begin{itemize}[<+->]
  \item Ленивото оценяване в Haskell ни позволява да работим с входно/изходни потоци
  \item \lst{getContents :: IO String} --- връща списък от \alert{всички} символи на стандартния вход
  \item списъкът се оценява лениво, т.е. прочита се при нужда
  \item \textbf{Пример:}
\begin{lstlisting}
noSpaces = do text <- getContents
              putStr (filter (/=' ') text)
\end{lstlisting}
  \item \lst{interact :: (String -> String) -> IO ()} --- лениво прилага функция над низове над стандартния вход и извежда резултата на стандартния изход
  \item \textbf{Пример:}
\begin{lstlisting}
noSpaces = interact (filter (/=' '))
\end{lstlisting}
  \end{itemize}
\end{frame}

\section{Безточково програмиране}

\begin{frame}
  \frametitle{Апликация}

  \begin{itemize}[<+->]
  \item Операцията „апликация“ се дефинира с \lst{f $ x = f x}
  \item За какво може да бъде полезна?
  \item Операцията \lst{$} е с най-нисък приоритет и е дясноасоциативна
    \begin{itemize}
    \item за разлика от прилагането на функции, което е с най-висок приоритет и лявоасоциативно
    \end{itemize}
  \item Може да бъде използвана за спестяване на скоби вложени надясно
  \item \tt(\ldots\tt{((f} $x_1$\tt) $x_2$\tt) \ldots $x_n$\tt) = \tt f $x_1$ $x_2$ \ldots $x_n$
  \item $f_1$ \tt($f_2$ \ldots \tt($f_n$ \tt{x)}\ldots\tt) = $f_1$ \tt\$ $f_2$ \tt\$ \ldots \tt\$ $f_n$ \tt{\$ x}
  \item \textbf{Примери:}
    \begin{itemize}
    \item \alt<+->{\lst{head $ tail $ take 5 $ drop 7 $ l}}{\lst{head (tail (take 5 (drop 7 l)))}}
    \item \alt<+->{\lst{sum $ map (^2) $ filter odd $ [1..10]}}{\lst{sum (map (^2) (filter odd [1..10]))}}
    \item \evalstop{map ($2) [(+2),(3^),(*5)]}{[4,9,10]}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Композиция}

  \begin{itemize}[<+->]
  \item \lst{(f . g) x = f (g x)} --- операция „композиция“
  \item с най-висок приоритет, дясноасоциативна
  \item Може да бъде използвана за спестяване на скоби вложени надясно
  \item $f_1$ \tt($f_2$ \ldots \tt($f_n$ \tt{x)}\ldots\tt) = $f_1$ \tt. $f_2$ \tt. \ldots \tt. $f_n$ \tt{\$ x}
  \item \textbf{Примери:}
    \begin{itemize}
    \item \alt<+->{\lst{sublist n m = take m . drop n}}{\lst{sublist n m l = take m (drop n l)}}
    \item \alt<+->{\lst{sumOddSquares = sum . map (^2) . filter odd}}{\lst{sumOddSquares l = sum (map (\^2) (filter odd l))}}
    \item \lst{repeated n f x = foldr (\$) x (replicate n f)}
    \item \lst{repeated n f = foldr (.) id (replicate n f)}
    \item \lst{repeated n f = foldr (.) id ((replicate n) f)}
    \item \lst{repeated n = foldr (.) id . replicate n}
    \item \lst{repeated n = (foldr (.) id .) (replicate n)}
    \item \lst{repeated = (foldr (.) id .) . replicate}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{pointfree}>
  \frametitle{Безточково (point-free) програмиране}

  С помощта на операциите \tt{\$} и \tt. можем да дефинираме функции чрез директно използване на други функции.\\\pause
  Този стил се нарича \textbf{безточково програмиране}.\\\pause
  \textbf{Пример 1:}
  \begin{itemize}[<+->]
    \small
  \item \lst{g l = filter (\\f -> f 2 > 3) l}
  \item \lst{g = filter (\\f -> (f \$ 2) > 3)}
  \item \lst{g = filter (\\f -> (>3) (($2) f))}
  \item \lst{g = filter $ (>3) . ($2)}
  \end{itemize}
  \onslide<+->
  \textbf{Пример 2:}
  \begin{itemize}[<+->]
  \footnotesize
  \item \lst{split3 ll = map (\\x -> map (\\f -> filter f x)  [(<0),(==0),(>0)]) ll}
  \item \lst{split3 = map  (\\x -> map (\\f -> flip filter x f) [(<0),(==0),(>0)])}
  \item \lst{split3 = map  (\\x -> map (flip filter x) [(<0),(==0),(>0)])}
  \item \lst{split3 = map  (\\x -> flip map [(<0),(==0),(>0)] (flip filter x))}
  \item \lst{split3 = map (flip map [(<0),(==0),(>0)] . flip filter)}
  \item \lst{split3 = map $ flip map [(<0),(==0),(>0)] . flip filter}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{pointfree}>
  \frametitle{Безточково (point-free) програмиране}
  \textbf{Пример 3:}
  \begin{itemize}[<+->]
  \small
  \item \lst{checkMatrix k m = all (\\r -> any (\\x -> mod k x > 0) r) m}
  \item \lst{checkMatrix k = all (\\r -> any (\\x -> mod k x > 0) r)}
  \item \lst{checkMatrix k = all (any (\\x -> mod k x > 0))}
  \item \lst{checkMatrix k = all (any (\\x -> (>0) ((mod k) x)))}
  \item \lst{checkMatrix k = all (any ((>0) . (mod k)))}
  \item \lst{checkMatrix k = all (any (((>0) .) (mod k)))}
  \item \lst{checkMatrix = all . any . ((>0) .) . mod}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{pointfree}>
  \frametitle{Безточково (point-free) програмиране}

  Можем да използваме още следните функции от \lst{Control.Monad}:
  \begin{itemize}[<+->]
  \item \lst{curry f x y = f (x,y)}
  \item \lst{uncurry f (x,y) = f x y}
  \item \lst{join f x = f x x}
  \item \lst{ap f g x = f x (g x)}
    \begin{itemize}
    \item \lst{join f = ap f id}
    \item \lst{join = (`ap` id)}
    \end{itemize}
  \item \lst{(f >>= g) x = g (f x) x}
    \begin{itemize}
    \item \lst{g =<< f = f >>= g}
    \item \lst{f >>= g = ap (flip g) f}
    \end{itemize}
  \item \lst{liftM2 f g h x = f (g x) (h x)}
    \begin{itemize}
    \item \lst{ap f = liftM2 f id}
    \item \lst{ap = (`liftM2` id)}
    \end{itemize}
  \end{itemize}
\end{frame}


\begin{frame}<\switch{pointfree}>
  \frametitle{Безточково (point-free) програмиране}
  \textbf{Пример 4:}
  \begin{itemize}[<+->]
  \item \lst{sorted l = all (\\(x,y) -> x <= y) (zip l (tail l))}
  \item \lst{sorted l = all (\\(x,y) -> (<=) x y) (ap zip tail l)}
  \item \lst{sorted l = all (uncurry (<=)) (ap zip tail l)}
  \item \lst{sorted = all (uncurry (<=)) . ap zip tail}
  \item \lst{sorted = all (uncurry (>=)) . (zip =<< tail)}
  \end{itemize}
  \onslide<+->
  \textbf{Пример 5:}
  \begin{itemize}[<+->]
    \item \lst{minsAndMaxs m = map (\\r -> (minimum r, maximum r)) m}
    \item \lst{minsAndMaxs = map (\\r -> (minimum r, maximum r))}
    \item \lst{minsAndMaxs = map (\\r -> (,) (minimum r) (maximum r))}
    \item \lst{minsAndMaxs = map (liftM2 (,) minimum maximum)}
    \item \lst{minsAndMaxs = map \$ liftM2 (,) minimum maximum}
  \end{itemize}
\end{frame}

\section{Стриктно оценяване}

\begin{frame}
  \frametitle{Разходване на памет при лениво оценяване}

  Ленивото оценяване може да доведе до голям разход на памет.\\[1em]\pause
  В Scheme:
  \lstset{language=Scheme}
  \begin{itemize}[<+->]
  \item \lst{(define (f x) (f (- 1 x)))}
  \item \evalstops{\tt{(f 0)}}{\textsf{забива, но не изразходва памет}}
  \item \tt f е \textbf{опашково-рекурсивна} и се реализира чрез итерация
  \item \evalstos{\tt{(f 0)}}{\evalstos{\tt{(f 1)}}{\evalstos{\tt{(f 0)}}{\evalstos{\tt{(f 1)}}{...}}}}
  \end{itemize}
  \onslide<+->
  В Haskell:
  \lstset{language=Haskell}
  \begin{itemize}[<+->]
  \item \lst{f x = f (1-x)}
  \item \evalstops{\tt{f 0}}{\textsf{\alert{забива с изтичане на памет!}}}
  \item \evalstos{\tt{f 0}}{\evalstos{\tt{f (1-0)}}{\evalstos{\tt{f (1-(1-0))}}{\evalstos{\tt{f (1-(1-(1-0)))}{...}}}}}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Стриктно оценяване в Haskell}

  \begin{itemize}[<+->]
  \item в Haskell може да изискаме даден израз да се оцени веднага
  \item еквивалентно на форсиране на обещание
  \item \lst{seq :: a -> b -> b}
  \item оценява първия си аргумент и връща втория като резултат
  \item \textbf{Примери:}
    \begin{itemize}
    \item \lst{second _ y = y}
    \item \evalsto{second (10^10^10) 2}{2}
    \item \lst{seq (10^10^10) 2} $\xrightarrow{\hspace{35ex}}$ \tt2
    \item \lst{f x = seq x (f (1-x))}
    \item \evalstops{\tt{f 0}}{\textsf{забива, но не изразходва памет!}}
    \end{itemize}
  \item \tt{f \$! x = seq x \alt<+->{\$ f x}{(f x)}}
    \begin{itemize}
    \item първо оценява \tt x и след това прилага \tt f над оценката на \tt x
    \item прилага \tt f над \tt x със стриктно оценяване
    \item \lst^f x = f \$! (1-x)^
    \ifbool{pointfree}{
    \item \lst^(\$!) = ap seq^}{}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Изразходване на памет при \tt{foldl}}

  \begin{tabular}{rl}
    &\lst{foldl (+) 0 [1..4]}\\
    \pause
   \lra&\lst{foldl (+) (0 + 1) [2..4]}\\
   \lra&\lst{foldl (+) ((0 + 1) + 2) [3..4]}\\
   \lra&\lst{foldl (+) (((0 + 1) + 2) + 3) [4..4]}\\
   \lra&\lst{foldl (+) ((((0 + 1) + 2) + 3) + 4) []}\\
   \lra&\lst{((((0 + 1) + 2) + 3) + 4)}\\
   \lra&\lst{(((1 + 2) + 3) + 4)}\\
   \lra&\lst{((3 + 3) + 4)}\\
   \lra&\lst{(6 + 4)}\\
   \lra&\lst{10}
  \end{tabular}\\[2em]
  \onslide<+->
  \alert{Проблем:} Изразходва памет при оценяване, понеже отлага изчисления!
\end{frame}

\begin{frame}[fragile]
  \frametitle{Стриктен вариант на \tt{foldl}}

  \onslide<+->
\begin{lstlisting}
foldl' _ nv [] = nv
foldl' op nv (x:xs) = (foldl' op $! op nv x) xs
\end{lstlisting}
  \onslide<+->
  \begin{tabular}{rl}
    &\tt{foldl' (+) 0 [1..4]}\\
   \lra&\tt{foldl' (+) 1 [2..4]}\\
   \lra&\tt{foldl' (+) 3 [3..4]}\\
   \lra&\tt{foldl' (+) 6 [4..4]}\\
   \lra&\tt{foldl' (+) 10 []}\\
   \lra&\tt{10}
  \end{tabular}
\end{frame}

\end{document}