git.iko.soy/ikoHSE/sc-lectures
on dependabot/npm_and_yarn/reveal.js/minimist-and-extract-zip-1.2.8 help sign in
ikoHSE/sc-lectures/2.md
986 lines 17 kB history raw
1---
2theme: superblack
3author: Ilya Kostyuchenko
4---
6# Функциональное программирование
9# Структуры
11```{ .haskell .fragment }
12data CircleType = Circle Double Double Double
13data RectangleType = Rectangle Double Double Double Double
15data Shape =
16 CircleShape CircleType | RectangleShape RectangleType
17```
19```{.haskell .fragment}
20shape = CircleShape (Circle 0 0 2)
21otherShape = RectangleShape (Rectangle 1 2 3 4)
22```
24---
26## Структура "человек"
28Имя, Фамилия, Отчество, Адрес, Почта, Возраст
30```{ .haskell .fragment }
31data Person =
32 Person String String String String String Natural
33```
35![](images/ohno.png){height=200px .fragment}
37---
39## Функции!
41```{ .haskell }
42data Person =
43 Person String String String String String Natural
44```
46```{ .haskell .fragment }
47firstName :: Person -> String
48firstName (Person name _ _ _ _ _) = name
49```
50```{ .haskell .fragment }
51setFirstName :: String -> Person -> Person
52setFirstName
53 newName
54 (Person _ lName mName address email age)
55 = Person newName lName mName address email age
56```
58```{ .haskell .fragment }
59lastName :: Person -> String
60lastName (Person _ lName _ _ _ _) = lName
61setLastName :: String -> Person -> Person
62setLastName
63 newLastName
64 (Person fName _ mName address email age)
65 = Person fName newLastName mName address email age
66```
68---
70```{ .haskell }
71middleName :: Person -> String
72middleName (Person _ _ mName _ _ _) = mName
73setMiddleName :: String -> Person -> Person
74setMiddleName
75 newMiddleName
76 (Person fName lName _ address email age)
77 = Person fName lName newMiddleName address email age
78```
80![](images/ohno.png){height=200px .fragment}
82[А что если структуры еще больше?]{.fragment}
84---
86## Record syntax
88```{ .haskell .fragment }
89data Person
90 = Person
91 { firstName :: String,
92 lastName :: String,
93 middleName :: String,
94 address :: String,
95 email :: String,
96 age :: Natural
97 }
98```
100```{ .haskell .fragment }
101-- Автоматически генерируются компилятором!
102firstName :: Person -> String
103lastName :: Person -> String
104-- ...
105```
107```{ .haskell .fragment }
108setFirstName :: String -> Person -> String
109setFirstName newName person = person {firstName = newName}
110-- Делает копию, заменяя одно (или нескеолько) поле.
111-- (То есть функции set... не нужны)
112```
114---
116# Абстракция
118---
120> Полиморфизм -- одну реализацию можно применять к разным типам.
122---
124```{ .haskell }
125length :: [a] -> Int
126```
128```{ .haskell .fragment }
129map :: (a -> b) -> [a] -> [b]
130```
132```{ .haskell .fragment }
133filter :: (a -> Bool) -> [a] -> [a]
134```
136[Problem: сама функция с `a` и `b` делать ничего не может -- она про них ничего не знает.]{.fragment}
138---
140```{.haskell}
141quicksort :: [Int] -> [Int]
142```
144```{ .haskell .fragment }
145quicksort :: [a] -> [a]
146```
148[Откуда `sort` узнает что такое `a` и как их сравнивать?]{.fragment}
150---
152## Typeclass
154---
156Самое близкое -- интрефейс.
158> Описывает свойства, которыми должен обладать объект
160---
162```{ .haskell }
163class Eq a where
164 (==) :: a -> a -> Bool
165```
167[`a` относится к классу `Eq` если существует такая функция `(==) :: a -> a -> Bool`]{.fragment}
169---
171```{ .haskell }
172class Eq a where
173 (==) :: a -> a -> Bool
174```
176```{ .fragment .haskell }
177data PersonType = Person String Int
178```
180```{ .fragment .haskell }
181instance Eq PersonType where
182 (Person name1 age1) == (Person name2 age2) =
183 name1 == name2 && age1 == age2
184```
186[instance -- "удовлетворяет", а не "экземпляр".]{ .fragment }
188---
190## Использование
192```{ .haskell .fragment }
193notEqual :: a -> a -> Bool
194```
196```{ .haskell .fragment }
197notEqual :: Eq a => a -> a -> Bool
198notEqual a b = not (a == b)
199```
202---
204```{ .haskell }
205class Eq a => Ord a where
206 (<=) :: a -> a -> Bool
207```
209[`a` относится к классу `Ord` если он относится к классу `Ord` и существует такая функция `(<=) :: a -> a -> Bool`]{.fragment}
211---
213```{ .haskell }
214class Eq a => Ord a where
215 (<=) :: a -> a -> Bool
216```
218```{ .haskell }
219data PersonType = Person String Int
220```
222```{ .fragment .haskell }
223instance Eq PersonType where
224 (Person name1 age1) == (Person name2 age2) =
225 name1 == name2 && age1 == age2
226```
228```{ .fragment .haskell }
229instance Ord PersonType where
230 (Person name1 age1) <= (Person name2 age2) =
231 name1 <= name2 && age1 <= age2
232```
234---
236## Использование
238```{ .haskell .fragment }
239(>) :: Ord a => a -> a -> Bool
240a > b = not (a <= b)
241```
243```{ .haskell .fragment }
244(>=) :: Ord a => a -> a -> Bool
245a >= b = a > b || a == b
246```
248[Тут мы можем использовать `>` на типах `a` потому что внутри функции уже есть определение `Ord a`.]{.fragment}
250---
252`notEqual` в стандартной библиотеке определен как `/=`.
254---
256```{ .haskell }
257max :: Ord a => a -> a -> a
258max a b = if a > b then a else b
259```
261[Из-за сильной системы типов гарантируется что функция вернет один из своих аргументов.]{.fragment}
263---
265## Case
267```{ .haskell .fragment }
268data Maybe a = Just a | Nothing
269```
270```{ .haskell .fragment }
271isJust :: Maybe a -> Bool
272```
274```{ .haskell .fragment }
275isJust Nothing = False
276isJust (Just _) = True
277```
279```{ .haskell .fragment }
280isJust x = case x of
281 Nothing -> False
282 Just _ -> True
283```
285[Просто возможность делать pattern matching где угодно, а не только в аргументах функций.]{ .fragment }
287---
289```{ .haskell }
290maximum :: Ord a => [a] -> Maybe a
291```
293```{ .haskell .fragment }
294max :: Ord a => a -> a -> a
295```
297```{ .haskell .fragment }
298maximum :: Ord a => [a] -> Maybe a
299maximum [] = Nothing
300maximum (x : xs) = case maximum xs of
301 Nothing -> Just x
302 Just y -> Just (max x y)
303```
305---
307## Полиморфные инстансы
309```{ .haskell .fragment }
310instance Ord (Maybe a)
311```
313```{ .haskell .fragment }
314instance Eq (Maybe a)
315```
317```{ .haskell .fragment }
318instance Eq a => Eq (Maybe a) where
319 (==) Nothing Nothing = True
320 (==) (Just a) (Just b) = a == b
321 _ == _ = False
322```
324```{ .haskell .fragment }
325instance Ord a => Ord (Maybe a) where
326 -- Потому что мы хотим чтобы Nothing был меньше всех
327 Nothing <= _ = True
328 (Just a) <= (Just b) = a <= b
329 (Just _) <= Nothing = False
330```
332---
334Что нам это дает?
336```{ .haskell .fragment }
337maximum :: Ord a => [a] -> Maybe a
338maximum [] = Nothing
339maximum (x : xs) = case maximum xs of
340 Nothing -> Just x
341 Just y -> Just (max x y)
342```
344```{ .haskell .fragment }
345maximum :: Ord a => [a] -> Maybe a
346maximum [] = Nothing
347maximum (x : xs) = max (Just x) (maximum xs)
348```
350---
352## Моноид
354> Моноид -- полугруппа с нейтральным элементом
356---
358## Полугруппа
360```{ .haskell .fragment }
361class Semigroup s where
362 (<>) :: s -> s -> s
363```
365```{ .haskell .fragment }
366instance Semigroup [x] where
367 a <> b = a ++ b -- конкатенация списков
368```
370## [Моноид]{.fragment}
372```{ .haskell .fragment }
373class Semigroup s => Monoid s where
374 mempty :: s
375```
377```{ .haskell .fragment }
378instance Monoid [x] where
379 mempty = []
380```
382---
384"Схлопывает" список моноидов.
386```{ .haskell }
387fold :: Monoid m => [m] -> m
388```
390```{ .haskell .fragment }
391fold [] = mempty
392fold (x : xs) = x <> fold xs
393```
395```{ .haskell .fragment }
396fold [[1, 3, 5], [42, 69]]
397-- [1, 3, 5, 42, 69]
398```
400---
402```{ .haskell }
403fold :: Monoid m => [m] -> m
404fold [] = mempty
405fold (x : xs) = x <> fold xs
406```
408```{ .haskell .fragment }
409fold [1, 2, 3]
410-- Что должно произойти?
411```
413---
415У целых чисел нет одного определения моноида.
417[Но мы можем определить свои типы!]{.fragment}
419```{ .haskell .fragment }
420data Sum = Sum { unSum :: Int }
421```
423```{ .haskell .fragment }
424instance Semigroup Sum where
425 (Sum a) <> (Sum b) = Sum (a + b)
426```
428```{ .haskell .fragment }
429instance Monoid Sum where
430 mempty = Sum 0
431```
433```{ .haskell .fragment }
434map :: (a -> b) -> [a] -> [b]
435```
437```{ .haskell .fragment }
438map (+ 1) [1, 2, 3]
439-- [2, 3, 4]
440```
442```{ .haskell .fragment }
443(unSum . fold . map Sum) [1, 2, 3]
444-- 6
445```
447---
449# Deriving
451```{ .haskell .fragment }
452class Show a where
453 show :: a -> String
454```
456```{ .haskell .fragment }
457data Foo = Bar Int Int String
458 deriving Show
459```
461```{ .haskell .fragment }
462show (Bar 1 2 "hello")
463-- Bar 1 2 "hello"
464```
466```{ .haskell .fragment }
467data Foo = Bar Int Int String
468 deriving (Show, Eq, Ord)
469```
471```{ .haskell .fragment }
472Bar 3 10 "hello" == Bar 3 10 "hello"
473-- True
474Bar 3 10 "hello" == Bar 3 10 "oh no"
475-- False
476```
478```{ .haskell .fragment }
479Bar 3 10 "hello" < Bar 4 -1000 "oh no"
480-- True
481```
484---
486## Синонимы типов
488[Тип можно обозвать как-то по-другому чтобы код было удобнее читать.]{.fragment}
490```{ .haskell .fragment }
491type String = [Char]
492```
494```{ .haskell .fragment }
495type Age = Int
496type Name = String
497```
499```{ .haskell .fragment }
500data Person = Person Name Age
501```
503[Буквально эквивалентно тому чтобы сделать find and replace по коду.]{.fragment}
505---
507```{ .haskell }
508scream :: String -> String
509scream = map toUpper
510```
512```{ .haskell .fragment }
513type Name = String
514```
516```{ .haskell .fragment }
517name :: Name
518name = "Vasya"
520-- This is fine.
521scream name
522-- "VASYA"
523```
526[В функцию `capitalize` можно передать константу типа `Name` потому что `String` и `Name` это одно и то же.]{.fragment}
528---
530`data` -- новый тип
532`type` -- просто обозвали по-другому
534---
536```{ .haskell }
537fold :: Monoid m => [m] -> m
538fold [] = mempty
539fold (x : xs) = x <> fold xs
540```
542```{ .haskell .fragment }
543fold ["Hello", "World"]
544-- "HelloWorld"
545--
546-- Потому что
547-- type String = [Char]
548```
550---
552# Обработка ошибок
554---
556```{ .java }
557TreeMap<String, Integer> m = new TreeMap();
558m.put("one", 1);
559m.put("two", 2);
560m.put("three", 3);
561```
563```{ .java .fragment }
564m.get("one");
565// 1
566```
568```{ .java .fragment }
569m.get("five");
570// null
571```
573```{ .java .fragment }
574class TreeMap<K,V> {
575 V get(K key) {
576 ...
577```
579[Неявный контекст ошибки ВЕЗДЕ.]{.fragment}
581---
583```{ .java }
584class TreeMap<K,V> {
585 Pair<V, Boolean> get(K key) {
586 ...
587```
589```{ .java .fragment }
590Pair<Integer, Boolean> result = m.get("one");
592if (result.second()) {
593 print(m.first());
594} else {
595 print("oh no");
597// 1
598```
600```{ .java .fragment }
601Pair<Integer, Boolean> result = m.get("five");
603if (result.second()) {
604 print(m.first());
605} else {
606 print("oh no");
608// oh no
609```
611---
613```{ .java }
614class TreeMap<K,V> {
615 V get(K key) throws NoElementException {
616 ...
617```
619```{ .java .fragment }
620try {
621 print(m.get("five"));
622} catch (NoElementException e) {
623 print("oh no");
625// oh no
626```
628---
630```{ .java }
631class Optional<T> {
632 ...
633```
635```{ .java .fragment }
636class TreeMap<K,V> {
637 Optional<V> get(K key) {
638 ...
639```
641---
643```{ .haskell }
644m :: Map String Int
645m = fromList [("one", 1), ("two", 2), ("three", 3)]
646```
648```{ .haskell .fragment }
649data Maybe a = Just a | Nothing
650```
652```{ .haskell .fragment }
653lookup :: k -> Map k v -> Maybe v
654```
656```{ .haskell .fragment }
657lookup "one" m
658-- Just 1
659```
661```{ .haskell .fragment }
662lookup "five" m
663-- Nothing
664```
666```{ .haskell .fragment }
667case lookup "one" m of
668 Just n -> ...
669 Nothing -> ...
670```
672---
674```{ .haskell }
675data Either a b = Left a | Right b
676```
678```{ .haskell .fragment }
679lookup :: k -> Map k v -> Either MapError v
680```
682```{ .haskell .fragment }
683makePayment :: Card -> Amount -> Either PaymentError Card
684```
686```{ .haskell .fragment }
687makePayment card amount =
688 if balance card >= amount
689 then Right (withdraw amount card)
690 else Left InsufficientFunds
691```
693---
695```{ .haskell }
696-- Обновляет аккаунт пользователя новой информацией о карте
697updateAccount :: Account -> Card -> Account
698```
700```{ .haskell .fragment }
701makePayment :: Card -> Amount -> Either PaymentError Card
702```
704```{ .haskell .fragment }
705card = creditCard account
707newAcccount :: Either PaymentError Account
708newAcccount =
709 updateAccount account (makePayment card (RUB 150))
710```
712```{ .haskell .fragment }
713newAcccount =
714 updateAccount account (makePayment card (RUB 150))
715-- (Card -> Account) (Either PaymentError Card)
716```
718```{ .haskell .fragment }
719newAcccount =
720 case makePayment card (RUB 150) of
721 Left e -> Left e
722 Right c -> updateAccount account c
723```
725---
727```{ .haskell }
728newAcccount =
729 updateAccount account (makePayment card (RUB 150))
730-- (Card -> Account) (Either PaymentError Card)
731```
733```{ .haskell .fragment }
734newAcccount =
735 magic (updateAccount account) (makePayment card (RUB 150))
736-- | (Card -> Account) (Either PaymentError Card)
737-- |
738-- (Card -> Account)
739-- -> (Either PaymentError Card
740-- -> Either PaymentError Account)
741```
743---
745## Lists!
747```{ .haskell .fragment }
748map :: (a -> b) -> [a] -> [b]
749```
751```{ .haskell .fragment }
752map :: (a -> b) -> ([a] -> [b])
753```
755```{ .haskell .fragment }
756magic ::
757 (Card -> Account) ->
758 ( (Either PaymentError) Card ->
759 (Either PaymentError) Account
760 )
761```
763```{ .haskell .fragment }
764type F = Either PaymentError
765```
767```{ .haskell .fragment }
768magic :: (Card -> Account) -> (F Card -> F Account)
769```
771---
773```{ .haskell }
774magic :: (Card -> Account) -> (F Card -> F Account)
775```
777[А мы можем обобщить `F`?]{.fragment}
779```{ .haskell .fragment }
780fmap ::
781 Functor f =>
782 (Card -> Account) ->
783 (f Card -> f Account)
784```
786---
788# Functor!
790![](images/fmap1.png){width=450 .fragment}
792![](images/fmap2.png){width=450 .fragment}
794---
796```{ .haskell }
797class Functor f where
798 fmap :: (a -> b) -> f a -> f b
799```
801```{ .haskell .fragment }
802class Functor [] where
803 fmap :: (a -> b) -> [a] -> [b]
804 fmap _ [] = []
805 fmap f (x : xs) = f x : fmap f xs
806```
808```{ .haskell .fragment }
809class Functor Maybe where
810 fmap :: (a -> b) -> Maybe a -> Maybe b
811 fmap _ Nothing = Nothing
812 fmap f (Just x) = Just (f x)
813```
815```{ .haskell .fragment }
816class Functor (Either e) where
817 fmap :: (a -> b) -> Either e a -> Either e b
818 fmap _ (Left e) = Left e
819 fmap f (Right x) = Right (f x)
820```
822---
824```{ .haskell }
825updateAccount :: Account -> Card -> Account
826makePayment :: Card -> Amount -> Either PaymentError Card
828newAcccount :: Either PaymentError Account
829newAcccount =
830 fmap (updateAccount account) (makePayment card (RUB 150))
831```
833---
835```{ .haskell }
836class Functor f where
837 fmap :: (a -> b) -> f a -> f b
838```
840```{ .haskell .fragment }
841class Functor (x ->) where
842 fmap :: (a -> b) -> (x -> a) -> (x -> b)
843 fmap (f :: a -> b) (g :: x -> a) = \(u :: x) -> f (g u)
844```
846```{ .haskell .fragment }
847 fmap (f :: a -> b) (g :: x -> a) = f . g
848```
850```{ .haskell .fragment }
851 fmap = (.)
852```
854---
856## Functor + Monoid
857## [= Alternative!]{.fragment}
860```{ .haskell .fragment }
861class Monoid s where
862 (<>) :: s -> s -> s
863 mempty :: s
864```
866```{ .haskell .fragment }
867foo :: f a -> f a -> f a
868```
870```{ .haskell .fragment }
871class Functor f => Alternative f where
872 (<|>) :: f a -> f a -> f a
873 empty :: f a
874```
876---
878```{ .haskell }
879class Functor f => Alternative f where
880 (<|>) :: f a -> f a -> f a
881 empty :: f a
882```
884```{ .haskell .fragment }
885instance Alternative Maybe where
886 (Just x) <|> _ = Just x
887 Nothing <|> y = y
889 empty = Nothing
890```
892```{ .haskell .fragment }
893Just 42 <|> Just 69
894-- Just 42
895```
897```{ .haskell .fragment }
898Nothing <|> Just 69
899-- Just 69
900```
902---
904```{ .haskell }
905instance Monoid e => Alternative (Either e) where
906 (Right x) <|> _ = Right x
907 _ <|> y = y
908 empty = Left mempty
909```
911```{ .haskell .fragment }
912Left "oh no" <|> Right 8
913-- Right 8
914```
916```{ .haskell .fragment }
917Right 42 <|> Right 8
918-- Right 42
919```
921```{ .haskell .fragment }
922makePayment :: Card -> Amount -> Either PaymentError Card
923```
925```{ .haskell .fragment }
926makePayment card1 (Rub 150) <|> makePayment card2 (Rub 150)
927```
929---
931```{ .haskell }
932instance Alternative [] where
933 xs <|> ys = xs ++ ys
934 empty = []
935```
937```{ .haskell .fragment }
938class Applicative f => Alternative f where ...
939```
941```{ .haskell .fragment }
942class Functor f => Applicative f where
943 pure :: a -> f a
944 ...
945```
947```{ .haskell .fragment }
948mult :: Alternative f => Int -> f Int
949mult n = mult' n 2
950 where
951 mult' n m =
952 if n <= m
953 then empty
954 else
955 if n `mod` m == 0
956 then pure m <|> mult (n `div` m)
957 else mult' n (m + 1)
958```
960---
962```{ .haskell }
963mult 10 :: [Int]
964-- [2, 5]
965```
967```{ .haskell .fragment }
968mult 10 :: Maybe Int
969-- Just 2
970```
972```{ .haskell .fragment }
973mult 23 :: [Int]
974-- []
975```
977```{ .haskell .fragment }
978mult 23 :: Maybe Int
979-- Nothing
980```
982---
984```{ .haskell }
985import Control.Applicative
986```