1 Д.з. Shape – типичные ошибки contains (Circle r x y) a b = if (sqrt ((x-a)^2+(y-b)^2)) Double contains:: a -> Double -> Double -> Bool instance Shape. - презентация

1 1 Д.з.

2 Shape – типичные ошибки contains (Circle r x y) a b = if (sqrt ((x-a)^2+(y-b)^2))

3 Shape data Circle = Circle Double Double Double data Rect = Rect Double Double Double Double class Shape a where area:: a -> Double perim:: a -> Double contains:: a -> Double -> Double -> Bool instance Shape Circle where contains (Circle r x0 y0) x y = (x-x0)^2+(y-y0)^2)

4 Дроби data Ration = Rat Integer Integer instance Ord Ration where Rat a b < Rat c d = a*c < b*d --- Вспомните 6 класс! Rat a b 0 then a*c b*d instance Eq Ration where Rat a b == Rat c d = a*c == b*d instance Num Ration where Rat a b + Rat c d = Rat (a*c + b*d) (b*d) instance Show Ration where show (Rat a b) = show a ++ "/" ++ show b 4

5 Еще про классы 5

6 Правила по умолчеию class Shape a where weight:: a->Double weight s = area s * 10 В определении класса можно задавать правила В instance можно их переопределять instance Shape Abc where weight s = area s * area s Полезное применение – связь или == и /= и т.д. class Ord x x x > y = y < x 6

7 deriving data Abc = …deriving Show Определить show автоматически (как-то) Еще Ord Eq Можно писать несколько классов data Abc = …deriving (Show, Ord, Eq) См. также 7

8 Сравнение классов и обьектов в обычных языках 8

9 В чем разница? Классы – это совсем то же, что объекты в C# или С++? Инкапсуляция? Несколько мешают конструкторы, с их помощью мы всегда можем посмотреть поля Полиморфизм Бывает статический и динамический (Тут мы обсуждали, в чем разница…) Списки не могут содержать элементы разных типов, даже если они экземпляры одного класса [Circle 1 2 6, Rect , Circle ] В Haskell так писать нельзя! (Тут мы обсуждали, как это связано с полиморфизмом) Но см. 9

10 Как сообщать о неудаче? 10

11 findSame – варианты решения 1. Число для сообщения об ошибке [1,2,3,2] 2 [1,2,3] может быть и "хорошим" ответом [1,2,3] На практике вполне хорошее решение Или, современный вариант [1,2,3] Вернуть пару [1,2,3,2] (True, 2) [1,2,3] (False, 0) Как сделать generic?? – не очень понятно 11

[2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые" title="findSame- еще варианты 3. Возвращаем строку [1,2,3,t] -> "Not found" [1,2,3,2] "2" Неудобно.. 4. [] или [x] [1,2,3,2] -> [2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые" class="link_thumb"> 12 findSame- еще варианты 3. Возвращаем строку [1,2,3,t] -> "Not found" [1,2,3,2] "2" Неудобно.. 4. [] или [x] [1,2,3,2] -> [2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые вычисления! 12 [2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые"> [2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые вычисления! 12"> [2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые" title="findSame- еще варианты 3. Возвращаем строку [1,2,3,t] -> "Not found" [1,2,3,2] "2" Неудобно.. 4. [] или [x] [1,2,3,2] -> [2] [1,2,3] -> [] 5. Список всех повторяющихся [1,2,3,2,3] -> [2,3] [1,2,3] -> [] Разве мы не будем делать лишнюю работу? Ленивые">

13 Maybe 6. Специальный тип Например: data Result = Found a | NotFound Есть стандартный тип: data Maybe a = Just a | Nothing [1,2,3,2] -> Just 2 [1,2,3] -> Nothing findSame [] = Nothing findSame (x:xs) = if elem x xs then Just x else findSame xs 13

14 Failure continuations (продолжения при ошибке) 14

15 find find условие список Вернуть элемент, удовлетворяющий условию Тоже проблема, как сообщить об ошибке Идея – в качестве параметра будем передавать значение, которое надо возвращать при ошибке Примеры find (>0) xs (-1) find odd xs 0 Определение find f [] err = err find f (x:xs) err = if f x then x else find f xs err 15

16 find c failure continuation На самом деле можно считать, что err – это то, что надо сделать при ошибке Пример: Найти в xs число > 0 а если его нет, то найти число >0 в ys, а если и его нет, вернуть 0. find (>0) xs (find (>0) ys 0) Так можно, потому что ленивые вычисления Получается, что find не совсем функция, а что-то вроде оператора: find условие список код-который-надо-выполнить-если-не-нашли Называется failure continuation (продолжение при ошибке) 16

17 Еще пример Найти первое число, большее 1000, а если его нет, то первое число большее 500, а если и его нет, то первое число большее 100 (а если и его нет, вернуть 0): find (>1000) xs (find (>500) xs (find (>100) 0) 17

18 findSame с failure continuation findsame [] err = err findsame (x:xs) err = find (==x) xs ( findsame xs err ) Небольшой фокус: Написали findSame без if Потому что find – это тоже что-то вроде if С другой стороны, сам по себе failure continuation вовсе не фокус, а вполне естественная функциональность В вычислительных пакетах всегда было что-то похожее – например, при решении СЛУ передаем функцию, которую надо вызвать, если у системы нет решений 18

19 superMap и т.д. 19

20 superMap superMap (\x->[sin x, cos x]) [1,2,3] [sin 1, cos 1, sin 2, cos 2, sin 3, cos 3] superMap f [] = [] superMap f (x:xs) = f x ++ superMap f xs Играет очень большую роль в Haskell стандартная функция concatMap стандартный оператор >>= 20

21 >>= [1,2,3] >>= \x->[sin x, cos x] Может использоваться и как обычный map [1,2,3] >>= \x -> [sin x] [sin 1, sin 2, sin 3] Можно удалять элементы [2, -4, 3, -8, -9, 4] [2, 3, 4] [2, -4, 3, -8, -9, 4] >>= \x -> if x < 0 then [] else [x*x] [2, 3, 4] 21

22 Символьные вычисления 22

23 Как представлять выражения, чтобы можно обрабатывать в программе Пока будем рассматривать выражения, которые состоят из целых чисел, переменной X и операции сложения и умножения data Expr = Num Integer | X | Add Expr Expr | Mult Expr Expr deriving Show или м.б. deriving (Show, Eq) Примеры: Add X (Num 1) Так мы записываем x+! Mult X (Add (Num 1) (Mult X X)) Так мы записываем x*(1+x*x) 23

24 Про некоторые доп.задачи 24

25 ham Richard Hamming: 2^i * 3^j * 5^k 1, 3, 9, 10, 27, 30, 81, 90, 100, 243, … map (*3) ham 3, 9, 27, 30, 81, 90, 243, … Не хватает только 1, 10, 100, 1000, … Как добавить? merge! ham = merge (map (*3) ham) ([10^n | i

26 pascal pascal = [[1], [1,1], [1,2,1], [1,3,3,1], … pascal = [1] : map getNext pascal getNext xs = [1] ++ zipWith (+) xs (tail xs) ++ [1] Или, без вспомогательной функции: pascal = [1] : map (\xs -> [1] ++zipWith (+) xs (tail xs)++ [1]) pascal 26

27 Д.з. 27

28 Д.з. В системе тестирования 28