2.5-haskell_data.tex

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

\title{Типове и класове в Haskell}

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

\lstset{language=Haskell,style=Haskell}

\begin{document}

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

\section{Полиморфизъм}

\begin{frame}
  \frametitle{Видове полиморфизъм в Haskell}

  В Haskell има два основни вида полиморфизъм.
  \begin{itemize}[<+->]
  \item \alert{параметричен полиморфизъм} --- възможност да създаваме конструкции, които обработват елементи от различни типове по \alert{универсален} начин
    \begin{itemize}
    \item такива конструкции наричаме \textbf{генерични (generic)}
    \item параметризират се  с \textbf{типови променливи}, които могат да приемат произволен тип за стойност
    \end{itemize}
  \item \alert{ad hoc полиморфизъм} --- възможност да създаваме конструкции, които обработват елементи от различни типове по \alert{специфичен} начин
    \begin{itemize}
    \item такива конструкции наричаме \textbf{претоварени (overloaded)}
    \item налагат механизъм за \textbf{разпределение (dispatch)}, който определя коя специфична реализация на конструкцията трябва да се използва в конкретен случай
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Параметричен полиморфизъм}

  Генеричните конструкции в Haskell са два вида:
  \begin{itemize}[<+->]
  \item \alert{генерични типове}, конструирани чрез използване на типови променливи
    \begin{itemize}
    \item функциите, кортежите и списъците могат да генерични
    \item \lst{type UnaryFunction a = a -> a}
    \item \lst{type Matrix a = [[a]]}
    \item \lst{type Dictionary k v = [(k, v)]}
    \end{itemize}
  \item \alert{генерични функции}, при които една и съща имплементация работи за различни типове
    \begin{itemize}
    \item \lst{length :: [a] -> Integer}
    \item \lst{map :: (a -> b) -> [a] -> [b]}
    \item \lst{repeated :: Integer -> UnaryFunction a -> UnaryFunction a}
    \item \lst{transpose :: Matrix a -> Matrix a}
    \item \lst{keys :: Dictionary k v -> [k]}
    \item \lst{[] :: [a]}
      \begin{itemize}
      \item константите са частен случай на функции (функции без параметри)
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Ad hoc полиморфизъм}

  В Haskell имаме претоварени константи, операции и функции:
  \begin{itemize}[<+->]
  \item \alert{претоварени константи}
    \begin{itemize}
    \item \tt5 може да означава цяло, дробно или комплексно число, в зависимост от контекста
    \item \tt{5.0} може да означава рационално число, число с плаваща запетая или комплексно число
    \item \tt{maxBound} е максималната стойност на ограничени типове
    \end{itemize}
  \item \alert{претоварени операции}
    \begin{itemize}
    \item \tt+ може да събира цели, дробни, или комплексни числа
    \item \tt/ може да дели рационални, дробни или комплексни числа
    \item \tt{==} може да сравнява числа, символи, кортежи или списъци
    \end{itemize}
  \item \alert{претоварени функции}
    \begin{itemize}
    \item \tt{elem} може да търси елемент в списък от сравними елементи
    \item \tt{show} може да извежда елемент, който има низово представяне
    \item \tt{[from..to]} може да генерира списък от последователни елементи от тип, в който имаме операции за следващ и предишен елемент
    \end{itemize}
  \end{itemize}
\end{frame}

\section{Класове от типове}

\begin{frame}
  \frametitle{Класове от типове (typeclasses)}

  \begin{definition}
    \textbf{Клас от типове} наричаме множество от типове, които поддържат определен тип поведение, зададено чрез множество от имена на функции и техните типове. \pause Функциите на даден клас наричаме \textbf{методи}.
  \end{definition}
  \pause
  Класовете от типове дават структуриран подход към ad hoc полиморфизма.\\
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{Eq} е класът от типове, които поддържат сравнение
  \item \lst{Ord} е класът от типове, които поддържат линейна наредба
  \item \lst{Show} е класът от типове, чиито елементи могат да бъдат
    извеждани в низ
  \item \lst{Num} е класът на всички числови типове
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Дефиниране на класове от типове}
  \tta{class} <клас> <типова-променлива>\tta{ where}\\
  \hspace{1em}\{<метод>\{,<метод>\} \tta{::} <тип>\}\\
  \hspace{1em}\{<метод> \tta{=} <реализация-по-подразбиране>\}\\[3ex]
  \pause
  \textbf{Примери:}\\
\begin{lstlisting}
class Eq a where
  (==), (/=) :: a -> a -> Bool
  x /= y     =  not (x == y)
  x == y     =  not (x /= y)
\end{lstlisting}
\pause
\begin{lstlisting}
class Measurable a where
   size :: a -> Integer
   empty :: a -> Bool
   empty x = size x == 0
\end{lstlisting}
\end{frame}

\begin{frame}
  \frametitle{Класови ограничения}
  \begin{definition}
    Ако \tt{C} e клас, а \tt{t} е типова променлива, то \tt{C t} наричаме \textbf{класово ограничение}. \pause Множество от класови ограничения наричаме \textbf{контекст}.
  \end{definition}
  \pause
  Класовите ограничения ни дават възможност да дефинираме претоварени функции.\\[2ex]
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{elem :: Eq a => a -> [a] -> Bool}
  \item \lst{maximum :: Ord a => [a] -> a}
  \item \lst{(^) :: (Integral b, Num a) => a -> b -> a}
  \item \lst{larger :: Measurable a => a -> a -> Bool}
  \item<.-> \lst{larger x y = size x > size y}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Дефиниране на екземпляри на клас}
  \begin{definition}
    \textbf{Екземпляр} (инстанция) на клас е тип, за който са дефинирани методите на класа.
  \end{definition}
  \pause
  \tta{instance} <клас> <тип> \tta{where}\\
  \hspace{1em} \{<дефиниция-на-метод>\}\\[1ex]
  \pause
  \textbf{Примери:}%
  \vspace{-1ex}
\begin{lstlisting}
instance Eq Bool where
  True  == True  = True
  False == False = True
  _     == _     = False
\end{lstlisting}\pause%
\begin{lstlisting}
instance Measurable Integer where
  size 0 = 0
  size n = 1 + size (n `div` 10)
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Екземпляри с контекст}
  Можем да добавяме контекст в дефиницията за екземпляри:\\
  \tta{instance} [<контекст> \tta{=>}] <клас> <тип> \tta{where}\\
  \hspace{1em} \{<дефиниция-на-метод>\}\\[2ex]
  \pause
  \textbf{Примери:}
\small
\begin{lstlisting}
instance (Eq a, Eq b) => Eq (a,b) where
  (x,y) == (u,t) = x == u && y == t
\end{lstlisting}
  \pause
\begin{lstlisting}
instance (Measurable a, Measurable b) => Measurable (a,b) where
  size (x,y) = size x + size y
\end{lstlisting}
  \pause
\begin{lstlisting}
instance Measurable a => Measurable [a] where
  size = sum . map size
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Наследяване}
  Можем да дефинираме клас \tt{B}, който допълва методите на вече съществуващ клас \tt{A}.\\
  Тогава казваме, че:
  \begin{itemize}[<+->]
  \item Класът \tt{B} \textbf{наследява} (разширява) класа \tt{A}
  \item Класът \tt{B} е \textbf{подклас} (производен клас, subclass) на класа \tt{A}
  \item Класът \tt{A} е \textbf{надклас} (родителски клас, superclass) на класа \tt{B}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Пример: Стандартен клас Ord}
\lstsmall
\begin{lstlisting}
class Eq a => Ord a  where
  (<), (<=), (>=), (>)  :: a -> a -> Bool
  max, min              :: a -> a -> a
  compare               :: a -> a -> Ordering
  compare x y
    | x == y    = EQ
    | x < y     = LT
    | otherwise = GT
  x < y  = compare x y == LT
  x > y  = compare x y == GT
  x == y = compare x y == EQ
  x <= y = compare x y /= GT
  x >= y = compare x y /= LT
  max x y = if x > y then x else y
  min x y = if x < y then x else y
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Множествено наследяване}
  Даден клас може да наследява едновременно няколко родителски класа.\\[2ex]
  \textbf{Примери:}
\begin{lstlisting}
class (Ord a, Num a) => Real a where
  ...
\end{lstlisting}
\pause
\begin{lstlisting}
class (Ord a, Measurable a) => OrdMeasurable a where
  sortByOrder, sortBySize :: [a] -> [a]
\end{lstlisting}
\end{frame}

\begin{frame}
  \frametitle{Сравнение на Haskell с други обектно-ориентирани езици}
  \begin{itemize}[<+->]
  \item Класовете в Haskell съответстват на \alert{абстрактни класове или интерфейси}
  \item Методите в Haskell съответстват на \alert{чисти виртуални функции}
  \item Класовете и обектите в C++ \alert{нямат директен еквивалент в Haskell}
    \begin{itemize}
    \item В Haskell данните винаги са разделени от методите
    \item Няма ограничения на достъпа (public, private)
    \item Няма понятие за разширяване на тип данни, само на интерфейс
    \item Съответно, няма \alert{подтипов полиморфизъм}
    \end{itemize}
  \item Екземплярите съответстват на \alert{имплементиране (наследяване) на интерфейси}
    \begin{itemize}
    \item В C++ и Java то може да бъде и множествено
    \end{itemize}
  \item В Haskell претоварените функции имат \alert{еднозначно определен тип}
    \begin{itemize}
    \item В C++ сме свободни да пишем функции с едно и също име и различни сигнатури
    \item В Haskell сме длъжни да наложим класови ограничения
    \end{itemize}
  \item В Haskell не можем да правим насилствено преобразуване на тип към даден клас (casting)
  \end{itemize}
\end{frame}

\section{Алгебрични типове}

\begin{frame}
  \frametitle{Потребителски дефинирани типове}
  В Haskell имаме възможност да дефинираме нови типове данни.\\[2ex]
  \begin{itemize}[<+->]
  \item \tta{data} <тип> [<параметри>] \tta= <дефиниция>
  \item{} <тип> трябва да започва с главна буква
  \item{} <параметри> е списък от различни типови променливи
  \item{} <дефиниция> ::= <елемент> \{ \tta| <елемент> \}
    \begin{itemize}
    \item{} <дефиниция> описва различните варианти за елементи на типа
    \end{itemize}
  \item{} <елемент> ::= <конструктор> \{ <тип-на-параметър> \}
    \begin{itemize}
    \item всеки вариант за елемент на типа се описва с уникален <конструктор>
    \item{} <конструктор> трябва да започва с главна буква
    \item{} <конструктор> може да има произволен брой параметри, чиито типове се задават в дефиницията
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Изброени типове}
  Най-простият вид потребителски дефинирани типове са \alert{изброените типове}.\\[2ex]
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{data Bool = False | True}
  \item \lst{data Compare = LT | EQ | GT}
  \item \lst{data Weekday = Mon | Tue | Wed | Thu | Fri | Sat | Sun}
  \item \lst{today :: Weekday}
  \item<.-> \lst{today = Tue}
  \item \lst{isWeekend :: Weekday -> Bool}
  \item<.-> \lst{isWeekend Sat = True}
  \item<.-> \lst{isWeekend Sun = True}
  \item<.-> \lst{isWeekend _   = False}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Записи}
  Друга възможност за потребителски дефинирани типове са \alert{записите}.\\
  \pause
  \begin{itemize}[<+->]
  \item \lst{type Name = String}
  \item<.-> \lst{type Score = Int}
  \item<.-> \lst{data Player = Player Name Score}
    \begin{itemize}
    \item Да, името на типа може да съвпада с името на (единствения) конструктор
    \end{itemize}
  \item \lst{katniss :: Player}
  \item<.-> \lst{katniss = Player "Katniss Everdeen" 45}
  \item \lst{getName :: Player -> Name}
  \item<.-> \lst{getName (Player name _) = name}
  \item \lst{better :: Player -> Player -> Name}
    \begin{lstlisting}
better (Player name1 score1) (Player name2 score2)
  | score1 > score2  = name1
  | otherwise        = name2
    \end{lstlisting}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Записи с полета}
  \begin{itemize}[<+->]
  \item По същество записите са еквивалентни на кортежите...
  \item ...които по същество са декартово произведение на типове
  \item Би било удобно, ако имахме имена на всяко от полетата
  \item В Haskell има специален синтаксис:
  \item<.-> \tta{\{} <поле>\{, <поле>\}\tta{::}<тип> \{, <поле>\{, <поле>\}\tta{::}<тип> \}\tta{\}}
  \item за всяко от полетата автоматично се дефинира функция селектор
  \item \textbf{Пример:}
    \begin{itemize}
    \item \lst!data Player = Player { name :: Name, score :: Score }!
    \item \lst{name :: Player -> Name}
    \item<.-> \lst{score :: Player -> Score}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Алтернативи}
  Можем да дефинираме типове, които обединяват няколко други типа.\\
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst!data Shape = Circle { radius :: Double } !\\
    \hspace{4em}\lst!| Rectangle { width, height :: Double }!
  \item \lst{circle :: Shape}
  \item<.-> \lst{circle = Circle 2.3}
  \item \lst{rect :: Shape}
  \item<.-> \lst{rect = Rectangle 3.5 1.8}
  \item \lst{area :: Shape -> Double}
  \item \lst{area (Circle r) = pi * r^2}
  \item<.-> \lst{area (Rectangle w h) = w * h}
  \item \lst{enlarge :: Shape -> Shape}
  \item \lst{enlarge (Circle r) = Circle (2*r)}
  \item<.-> \lst{enlarge (Rectangle w h) = Rectangle (2*w) (2*h)}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Автоматични екземпляри на класове}

  При работа с алгебрични типове се сблъскваме с един недостатък:\pause
  \begin{itemize}[<+->]
  \item \evalstoerrp{Circle 2.3 == Circle 4.5}
  \item \evalstop{circle}{circle :: Shape}
  \item \evalstoerrp{[Mon..Fri]}
  \item \evalstoerrp{Thu < Sat}
  \end{itemize}
  \onslide<+->
  За използването на тези елементарни операции се налага ръчно да пишем тривиални екземпляри за класове като \lst{Eq}, \lst{Ord}, \lst{Enum}, \lst{Show}:
  \onslide<+->
  \small
\begin{lstlisting}
instance Eq Shape where
  Circle x      == Circle y       = x == y
  Rectangle a b == Rectangle c d  = (a,b) == (c,d)
  _             == _              = False
\end{lstlisting}
  \onslide<+->
\begin{lstlisting}
instance Show Shape where
  show (Circle x)      = "Circle " ++ show x
  show (Rectangle a b) = "Rectangle " ++ show a ++ " " ++ show b
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Автоматични екземпляри на класове}

  Haskell има възможност за автоматично извеждане на екземпляри на класовете \lst{Eq}, \lst{Ord}, \lst{Enum}, \lst{Show}, \lst{Read}.\pause
  \small
  \begin{itemize}[<+->]
  \item \tta{data} <тип> [<параметри>] \tta= <дефиниция> \tta{deriving} <класове>
  \item{} <класове> е кортеж от стандартни класове, екземпляри за които искаме автоматично да бъдат изведени
  \item \lst{data Weekday = Mon | Tue | Wed | Thu | Fri | Sat | Sun}\\
    \hspace{5em}\lst{deriving (Eq, Ord, Enum, Show, Read)}
  \item \lst{Eq}: два елемента се считат равни, ако имат равни конструктори с равни параметри
  \item \lst{Ord}: елементите се сравняват лексикографски, като конструкторите се считат наредени в реда, в който са дефинирани
  \item \lst{Enum}: позволено само за изброени типове
  \item \lst{Show}, \lst{Read}: извежда се/въвежда се конструкторът и след това всеки един от параметрите му
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Параметризирани типове}
  Потребителските типове могат да бъдат \alert{генерични}, т.е. да зависят от типови параметри.\\
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{data Maybe a = Nothing | Just a}\\
      \hspace{5em}\lst{deriving (Eq, Ord, Show, Read)}
  \item \typestop{Just 5}{Maybe Int}
  \item \typestop{Just "wow"}{Maybe String}
  \item \typestop{Nothing}{Maybe a}
  \item \typestop{Just Nothing}{Maybe (Maybe a)}
  \item \lst{getAt :: Integer -> [a] -> Maybe a}
  \item \lst{getAt _ []  = Nothing}
  \item<.-> \lst{getAt 0 (x:_) = Just x}
  \item<.-> \lst{getAt n (_:xs) = getAt (n-1) xs}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Сума на типове}
  \begin{itemize}[<+->]
  \item \lst{data Either a b = Left a | Right b}\\
      \hspace{5em}\lst{deriving (Eq, Ord, Show, Read)}
  \item \typestop{Left 3}{Either Int b}
  \item \typestop{Right 'a'}{Either a Char}
  \end{itemize}
  \onslide<+->
  \textbf{Задача.} Да се напише функция, която по даден списък от играчи намира най-добрия резултат, ако е постигнат от единствен играч, или списък от имената на играчите, които са постигнали най-добър резултат.
  \onslide<+->
\begin{lstlisting}
searchBest :: [Player] -> Either Score [Name]@\onslide<+->@
searchBest players
 | length bestPlayers == 1 = Left best
 | otherwise = Right $ map name bestPlayers
   where best = maximum $ map score players
         bestPlayers = filter ((==best) . score) players
\end{lstlisting}
\end{frame}

\section{Рекурсивни алгебрични типове}

\begin{frame}[fragile]
  \frametitle{Рекурсивни алгебрични типове}
  Можем да дефинираме типове, позовавайки се на самите тях \alert{рекурсивно}.\\[2ex]
  \pause
  \textbf{Пример:}
  \lst{data Nat = Zero | Succ Nat deriving (Eq, Ord, Show, Read)}
  \begin{itemize}[<+->]
  \item \lst{five = Succ $ Succ $ Succ $ Succ $ Succ Zero}
  \item \lst{fromNat :: Nat -> Integer}
  \item \lst{fromNat Zero = 0}
  \item<.-> \lst{fromNat (Succ n) = fromNat n + 1}
  \item \evalsto{fromNat five}5
  \end{itemize}
\end{frame}

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

\begin{lstlisting}
data Bin = One | BitZero Bin | BitOne Bin
           deriving (Eq, Ord, Show, Read)
\end{lstlisting}
  \pause
  \begin{itemize}[<+->]
  \item \lst{six = BitZero $ BitOne $ One}
  \item \lst{fromBin :: Bin -> Integer}
  \item \lst{fromBin One = 1}
  \item<.-> \lst{fromBin (BitZero b) = 2 * fromBin b}
  \item<.-> \lst{fromBin (BitOne b) = 2 * fromBin b + 1}
  \item \lst{succBin :: Bin -> Bin}
  \item \lst{succBin One = BitZero One}
  \item<.-> \lst{succBin (BitZero b) = BitOne b}
  \item<.-> \lst{succBin (BitOne b) = BitZero $ succBin b}
  \item \evalsto{fromBin \$ succBin \$ succBin six}8
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Списъци}

\begin{lstlisting}
data List a = Nil | Cons a (List a)
              deriving (Eq, Ord, Show, Read)
\end{lstlisting}
  \pause
  \begin{itemize}[<+->]
  \item \lst{l = Cons 1 $ Cons 2 $ Cons 3 $ Nil}
  \item можем да използваме синтаксиса за записи:\\
    \lst!data List a = Nil | Cons { listHead :: a, listTail :: List a }!\\
    \hspace{5em}\lst{deriving (Eq, Ord, Show, Read)}
  \item \evalstop{listHead l}1
  \item \lst{fromList :: List a -> [a]}
  \item \lst{fromList Nil = []}
  \item<.-> \lst{fromList (Cons x t) = x:fromList t}
  \item \lst{(+++) :: List a -> List a -> List a}
  \item \lst{Nil +++ l = l}
  \item<.-> \lst{Cons h t +++ l = Cons h (t +++ l)}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Двоични дървета}
\begin{lstlisting}
data BinTree a = Empty | Node { root :: a, left, right :: BinTree a }
                 deriving (Eq, Ord, Show, Read)
\end{lstlisting}
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{t = Node 3 (Node 1 Empty Empty) (Node 5 Empty Empty)}
  \item \lst{depth :: BinTree a -> Integer}
  \item \lst{depth Empty = 0}
  \item<.-> \lst{depth (Node x l r) = max (depth l) (depth r) + 1}
  \item \lst{leaves :: BinTree a -> [a]}
  \item \lst{leaves Empty = []}
  \item<.-> \lst{leaves (Node x Empty Empty) = [x]}
  \item<.-> \lst{leaves (Node x l r) = leaves l ++ leaves r}
  \end{itemize}
\end{frame}

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

  Трансформиране на двоично дърво (\lst{map}):
  \pause
\begin{lstlisting}
mapBinTree :: (a -> b) -> BinTree a -> BinTree b
mapBinTree _ Empty        = Empty
mapBinTree f (Node x l r) = Node (f x) (mapBinTree f l) (mapBinTree f r)
\end{lstlisting}
  \vspace{4ex}
  \pause
  Свиване на двоично дърво (\lst{foldr}):
\begin{lstlisting}
foldrBinTree :: (a -> b -> b) -> b -> BinTree a -> b
foldrBinTree _  nv Empty        = nv
foldrBinTree op nv (Node x l r) =
  foldrBinTree op (x `op` foldrBinTree op nv r) l
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Дървета с произволен брой наследници}
\small
  Можем да правим \alert{взаимнорекурсивни} дефиниции:
\begin{lstlisting}
data Tree a =  Tree { rootTree :: a, subtrees :: TreeList a }
data TreeList a = None | SubTree { firstTree :: Tree a, restTrees :: TreeList a }
\end{lstlisting}
\pause
\begin{lstlisting}
leaf x = Tree x None
tree = Tree 1 $ SubTree (leaf 2)
              $ SubTree (Tree 3 $ SubTree (leaf 4) $ None)
              $ SubTree (leaf 5) $ None
\end{lstlisting}
\pause
\begin{lstlisting}
level :: Integer -> Tree a -> [a]@\pause@
level 0 (Tree x _)     = [x]
level k (Tree _ ts)    = levelTrees (k - 1) ts
\end{lstlisting}
\pause
\begin{lstlisting}
levelTrees :: Integer -> TreeList a -> [a]@\pause@
levelTrees _ None           = []
levelTrees k (SubTree t ts) = level k t ++ levelTrees k ts
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Полиморфни списъци}
\small
\begin{lstlisting}
data SExpr = SBool Bool | SChar Char | SInt Int |
             SDouble Double | SList { list :: [SExpr] }
             deriving (Eq, Ord, Show, Read)
\end{lstlisting}
  \ \pause
\begin{lstlisting}
sexpr = SList [SInt 2, SChar 'a', SList [SBool True, SDouble 1.2, SList []]]
\end{lstlisting}
  \pause
\begin{lstlisting}
countAtoms :: SExpr -> Integer@\pause@
countAtoms (SList sls) = sum $ map countAtoms sls
countAtoms _           = 1
\end{lstlisting}
  \pause
\begin{lstlisting}
flatten :: SExpr -> SExpr@\pause@
flatten (SList sls) = SList $ concatMap (list . flatten) sls
flatten x           = SList [x]
\end{lstlisting}
\end{frame}

\end{document}