1 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Еще один пример функциональной программы 2 6 4 1. - презентация

1 1 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Еще один пример функциональной программы type FGraph = (Int, (Int->Int->Bool)) type LGraph = [(Int, [Int])] myFGraph :: FGraph myFGraph = (6, \x y -> case (x, y) of (1,4) -> True (1,5) -> True (2,6) -> True (3,1) -> True (3,5) -> True (5,4) -> True (_,_) -> False ) myLGraph :: LGraph myLGraph = [(1, [4,5]), (2, [6]), (3, [1,5]), (4, []), (5, [4]), (6, [])] -- функции преобразования графа из одного представления в другое convertF2L :: FGraph -> LGraph convertL2F :: LGraph -> FGraph convertF2L (n, func) = [(i, [j | j

2 2 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования type FGraph = (Int, (Int->Int->Bool)) Проверим, имеется ли путь от одной вершины до другой с помощью обхода графа «в ширину». Множества вершин будем представлять в виде функции: type Set = Int -> Bool Операции объединения, разности, проверки пустоты: empty :: Int -> Set -> Bool diff :: Set -> Set -> Set disj :: Set -> Set -> Set empty n s = null (filter s [1..n]) (s1 `diff` s2) n = s1 n && not (s2 n) (s1 `disj` s2) n = s1 n || s2 n Наличие пути проверяем с помощью обхода в ширину: path :: Int -> Int -> FGraph -> Bool breadth :: FGraph -> Set -> Set -> Set path start finish g = (breadth g startOnly startOnly) finish where startOnly n = n == start breadth front visited | empty n front = visited | otherwise = breadth gr (newlist `diff` visited) (newlist `disj` visited) where newlist = foldr disj (\x->False) (map g (filter front [1..n]))

3 3 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования Классы в Haskell. Класс определяет набор операций (функций). Тип данных принадлежит некоторому классу, если для него определены все функции, объявленные в классе. class Eq t where (==), (/=) :: t -> t -> Bool Мы объявляем, что некоторый тип данных принадлежит этому классу, с помощью определения «экземпляра» класса. instance Eq Bool where True == True = True False == False = True _ == _ = False x /= y = not (x == y) instance (Eq t)=> Eq [t] where [] == [] = True (x1:s1) == (x2:s2) = (x1 == x2) && (s1 == s2) _ == _ = False

4 4 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Пример: определение операций сравнения над деревьями data Tree a = Empty | Node (Tree a) a (Tree a) instance (Eq t) => Eq (Tree t) where Empty == Empty = True (Node tl1 n1 tr1) == (Node tl2 n2 tr2) = (n1 == n2) && (tl1 == tl2) && (tr1 == tr2) _ == _ = False instance (Eq t) => Eq (Tree t) where Empty == Empty = True (Node tl1 n1 tr1) == (Node tl2 n2 tr2) = (n1 == n2) && (((tl1 == tl2) && (tr1 == tr2)) || ((tl1 == tr2) && (tr1 == tl2))) _ == _ = False t1 = Node (Node Empty 2 Empty) 1 (Node (Node Empty 4 Empty) 3 (Node Empty 5 Empty)) t2 = Node (Node (Node Empty 5 Empty) 3 (Node Empty 4 Empty)) 1 (Node Empty 2 Empty) t1 == t2 ? t1t2

5 5 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Вывод значений различных типов в виде строки Немного упрощенная версия класса для вывода значений в виде строки: class Show t where show :: t -> String shows :: t -> String -> String show v = shows v [] shows v s = show v ++ s instance (Show t) => Show (Tree t) where shows Empty s = s shows (Node tl n tr) = ('(':). (shows tl). (shows n). (shows tr). (')':)

6 6 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Расширение классов class (Eq t) => Ord t where ( ), (>=) :: t -> t -> Bool a = b) a b) a > b = not (a = b = not (a < b) instance (Ord t) => Ord (Tree t) where Empty

7 7 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Стандартная реализация операций для встроенных классов data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Eq, Ord, Show) объекты равны, если равны все составляющие их части сравнение происходит в лексикографическом порядке составляющих объекты конструкторов: Empty < (Node t1 n t2) для любых t1, n и t2 преобразование в строку: выводятся имена конструкторов и их аргументы t1 t2