git.iko.soy/ikoHSE/sc-lectures
on dependabot/npm_and_yarn/reveal.js/socket.io-parser-3.3.3 help sign in
ikoHSE/sc-lectures/3.md
865 lines 17 kB history raw
1---
2theme: superblack
3author: Ilya Kostyuchenko
4---
6# Функциональное программирование
8---
10## Напоминалочка
12```{ .haskell }
13class Functor f where
14 fmap :: (a -> b) -> f a -> f b
15```
17```{ .haskell .fragment }
18class Functor f => Alternative f where
19 (<|>) :: f a -> f a -> f a
20 empty :: f a
21```
23---
25## Библиотека про математику
26#### (на джаве)
28```{ .java .fragment }
29static int add(int x, int y) {
30 return x + y;
32```
34["Нам для сертификации надо чтобы каждая функция логировала свой вызов."]{.fragment}
36---
38### Вариант 1
40```{ .java .fragment }
41static int add(int x, int y) {
42 log += "add";
43 return x + y;
45```
471. Неявная зависимость
482. Невозможно рефакторить
493. Почему функция для складывания чисел умеет логи?
51---
53### Вариант 2
55```{ .java .fragment }
56static Pair<Integer, String> add(int x, int y, string log) {
57 return new Pair(x + y, log + "add");
59```
611. ~~Неявная зависимость~~
622. ~~Невозможно рефакторить~~
633. Неудобно программировать
643. Почему функция для складывания чисел умеет логи?
66---
68### Вариант ООП
70```{ .java .fragment }
71static int add(int x, int y, Logger log) {
72 Logger.log("add");
73 return x + y;
75```
771. ~~Неявная зависимость~~
782. ~~Невозможно рефакторить~~
793. Неудобно программировать
803. ~~Почему функция для складывания чисел умеет логи?~~
82---
84```{ .haskell }
85add :: Int -> Int -> (Int, String)
86add x y = (x + y, "add " + show x + show y)
87```
89[Неудобно программировать]{ .fragment }
91```{ .haskell .fragment }
92add :: Int -> Int -> Int
93times :: Int -> Int -> Int
95add8AndDouble :: Int -> Int
96add8AndDouble = times 2 . add 8
97```
99---
101```{ .haskell }
102add :: Int -> Int -> (Int, String)
103times :: Int -> Int -> (Int, String)
104```
106```{ .haskell .fragment }
107add8AndDouble :: Int -> (Int, String)
108add8AndDouble x = (y2, log1 <> log2)
109 where
110 (y1, log1) = add 8 x
111 (y2, log2) = times 2 y1
112```
114![](images/ohno.png){height=200px .fragment}
116```{ .haskell .fragment }
117add8AndDouble :: Int -> Int
118add8AndDouble = times 2 . add 8
119```
121---
123```{ .haskell }
124data WithLog a = WithLog a String
125```
127```{ .haskell .fragment }
128add :: Int -> Int -> WithLog Int
129times :: Int -> Int -> WithLog Int
130```
132```{ .haskell .fragment }
133add8AndDouble :: Int -> WithLog Int
134add8AndDouble = times 2 `magic` add 8
135```
137```{ .haskell .fragment }
138magic ::
139 (Int -> WithLog Int) ->
140 (Int -> WithLog Int) ->
141 (Int -> WithLog Int)
142```
144```{ .haskell .fragment }
145magic f g x1 = WithLog x3 (log1 <> log2)
146 where
147 (WithLog x2 log1) = g x1
148 (WithLog x3 log2) = f x2
149```
151---
153```{ .haskell }
154magic ::
155 (Int -> WithLog Int) ->
156 (Int -> WithLog Int) ->
157 (Int -> WithLog Int)
158```
160```{ .haskell .fragment }
161(<=<) ::
162 (Int -> WithLog Int) ->
163 (Int -> WithLog Int) ->
164 (Int -> WithLog Int)
165```
167```{ .haskell .fragment }
168add8AndDouble :: Int -> WithLog Int
169add8AndDouble = times 2 <=< add 8
170```
172---
174```{ .haskell }
175factor :: Int -> WithLog [Int]
177sum :: [Int] -> WithLog Int
178```
180```{ .haskell .fragment }
181sumFactors :: Int -> WithLog [Int]
182sumFactors = sum <=< factor -- Doesn't work :(
183```
185```{ .haskell .fragment }
186(<=<) ::
187 (Int -> WithLog Int) ->
188 (Int -> WithLog Int) ->
189 (Int -> WithLog Int)
190```
192```{ .haskell .fragment }
193(<=<) ::
194 (b -> WithLog c ) ->
195 (a -> WithLog b ) ->
196 (a -> WithLog c )
197```
199```{ .haskell .fragment }
200(.) ::
201 (b -> c ) ->
202 (a -> b ) ->
203 (a -> c )
204```
206---
208```{ .haskell }
209getCoffee :: Order -> Maybe Coffee
210payForCoffee :: Coffee -> Maybe Payment
211```
213```{ .haskell .fragment }
214buyCoffee :: Order -> Maybe Payment
215buyCoffee = payForCoffee <=< getCoffee
216```
218```{ .haskell .fragment }
219getCoffee :: Order -> Either CoffeeError Coffee
220payForCoffee :: Coffee -> Either CoffeeError Payment
221```
223```{ .haskell .fragment }
224buyCoffee :: Order -> Either CoffeeError Payment
225buyCoffee = payForCoffee <=< getCoffee
226```
228```{ .haskell .fragment }
229(<=<) ::
230 Composable m =>
231 (b -> m c) ->
232 (a -> m b) ->
233 (a -> m c)
234```
236---
238```{ .haskell }
239class Applicative m => Monad m where
240 (<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
241```
243```{ .haskell .fragment }
244instance Monad Maybe where
245 (<=<) f g x = case g x of
246 Nothing -> Nothing
247 Just x2 -> f x2
248```
250```{ .haskell .fragment }
251instance Monad (Either e) where
252 (<=<) f g x = case g x of
253 Left e -> Left e
254 Right x2 -> f x2
255```
257```{ .haskell .fragment }
258instance Monad WithLog where
259 (<=<) f g x = WithLog x3 (log1 <> log2)
260 where
261 (WithLog x2 log1) = g x
262 (WithLog x3 log2) = f x2
263```
265---
267### Больше операторов!
269```{ .haskell .fragment }
270(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
271```
272```{ .haskell .fragment }
273buyCoffee :: Order -> Maybe Payment
274buyCoffee = payForCoffee <=< getCoffee
275```
277```{ .haskell .fragment }
278flip :: (a -> b -> c) -> (b -> a -> c)
279flip f b a = f a b
280```
282```{ .haskell .fragment }
283(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
284(>=>) = flip (<=<)
285```
287```{ .haskell .fragment }
288buyCoffee = getCoffee >=> payForCoffee
289```
291---
293### Маленькое отступление
295`f :: () -> a` эквивалентно `f :: a`
297[Потому что у `()` всего одно значение (`()`), а любая функция для одинаковых аргументов всегда возвращает одинаковые значения (потому что по-другому невозможно).]{ .fragment }
299---
301```{ .haskell }
302(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
303```
305```{ .haskell .fragment }
306(>>=) :: Monad m => m b -> (b -> m c) -> m c
307```
309```{ .haskell .fragment }
310buyCoffee :: Order -> Maybe Payment
311buyCoffee order = getCoffee order >>= payForCoffee
312```
314```{ .haskell .fragment }
315maybeBuyCoffee :: Maybe Order -> Maybe Payment
316maybeBuyCoffee mOrder = mOrder >>= buyCoffee
317```
319```{ .haskell .fragment }
320(>>=) :: Monad m => m b -> (b -> m c) -> m c
321```
323```{ .haskell .fragment }
324(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
325```
327```{ .haskell .fragment }
328 (() -> m b) -> (b -> m c) -> (() -> m c)
329```
330```{ .haskell .fragment }
331 m b -> (b -> m c) -> m c
332```
334---
336```{ .haskell }
337(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
338```
340```{ .haskell }
341(>>=) :: Monad m => m b -> (b -> m c) -> m c
342(>>=) mb bmc = ( (\() -> mb) >=> bmc ) ()
343```
345```{ .haskell .fragment }
346(>>=) mb bmc = ( (\() -> mb) >=> bmc ) ()
347-- () -> m b |
348-- b -> m c
349--
350-- ^-----------------------^
351-- () -> m c
352```
354---
356### Время раскрыть ложь
358```{ .haskell }
359class Applicative m => Monad m where
360 (>>=) :: m a -> (a -> m b) -> m b
361 return :: a -> m a
362```
364```{ .haskell .fragment }
365 -- Law:
366 ma :: m a
367 (ma >>= return) == ma
368```
370```{ .haskell .fragment }
371 -- Law:
372 f :: a -> m b
373 (f >=> return) == f
374```
376[`return` -- нейтральный элемент по `>=>`]{.fragment}
378```{ .haskell .fragment }
379 -- Law:
380 x :: a
381 f :: a -> m b
382 (return x >>= f) == f x
383```
385---
387```{ .haskell }
388instance Monad Maybe where
389 ma >>= f = case ma of
390 Nothing -> Nothing
391 Just a -> f a
393 return a = Just a
394```
396```{ .haskell .fragment }
397instance Monad (Either e) where
398 ma >>= f = case ma of
399 Left e -> Left e
400 Right a -> f a
402 return a = Right a
403```
405```{ .haskell .fragment }
406instance Monad WithLog where
407 (WithLog a log1) >>= f = WithLog b (log1 <> log2)
408 where
409 WithLog b log2 = f a
411 return a = WithLog a ""
412```
414---
416## More Monads!
418```{ .haskell }
419type Markup = Int
421getCoffee :: Markup -> Order -> Coffee
422payForCoffee :: Markup -> Coffee -> Payment
424buyCoffee :: Markup -> Order -> Payment
425buyCoffee markup = payForCoffee markup . getCoffee markup
426```
428```{ .haskell .fragment }
429data Reader r a = Reader
430 { runReader :: r -> a
431 }
432```
434[`r` -- то, что у нас в "окружении".]{ .fragment }
436---
438```{ .haskell }
439data Reader r a = Reader { runReader :: r -> a }
441getCoffee :: Order -> Markup -> Coffee
442payForCoffee :: Coffee -> Markup -> Payment
443```
445```{ .haskell .fragment }
446getCoffee :: Order -> Reader Markup Coffee
447payForCoffee :: Coffee -> Reader Markup Payment
448```
450```{ .haskell .fragment }
451type PricingEnv = Reader Markup
452```
454```{ .haskell .fragment }
455getCoffee :: Order -> PricingEnv Coffee
456payForCoffee :: Coffee -> PricingEnv Payment
457```
459```{ .haskell .fragment }
460buyCoffee :: Order -> PricingEnv Payment
461buyCoffee = payForCoffee <=< getCoffee
462```
464```{ .haskell .fragment }
465payment :: Payment
466payment = runReader (buyCoffee order) markup
467```
469---
471```{ .haskell }
472data Reader r a = Reader
473 { runReader :: r -> a
474 }
476instance Monad (Reader r) where
477 return a = Reader (\_ -> a)
479 (Reader g) >>= f = Reader ( \r -> runReader (f (g r)) r )
480```
482```{ .haskell .fragment}
483 (>>=) :: Reader r a -> (a -> Reader r b) -> Reader r b
485 (Reader g) >>= f = Reader ( \r -> runReader (f (g r)) r )
486-- ^---^
487-- a
488-- ^-------^
489-- Reader r b
490-- ^-----------------^
491-- r -> b
492```
494---
496```{ .haskell }
497type Price = Int
498getCoffeePrice :: Markup -> Coffee -> Price
499getDiscount :: Markup -> Coffee -> Price
500getPayment :: Markup -> Price -> Payment
502payForCoffee :: Markup -> Coffee -> Payment
503payForCoffee markup coffee = getPayment markup amount
504 where
505 coffeePrice = getCoffeePrice markup coffee
506 discount = getDiscount markup coffee
507 amount = coffeePrice - discount
508```
510```{ .haskell .fragment }
511type PricingEnv = Reader Markup
513getCoffeePrice :: Coffee -> PricingEnv Price
514getDiscount :: Coffee -> PricingEnv Price
515getPayment :: Price -> PricingEnv Payment
517payForCoffee :: Coffee -> PricingEnv Payment
518payForCoffee coffee =
519 coffee >>= getCoffeePrice >>= \coffeePrice ->
520 coffee >>= getDiscount >>= \discount ->
521 getPayment (coffeePrice - discount)
522```
524---
526## Do syntax
528```{ .haskell .fragment }
529bar :: Reader r a
530qux :: a -> Reader r b
532foo :: Reader r b
533foo = bar >>= \x -> qux x
534```
536```{ .haskell .fragment }
537foo = do
538 -- (x :: a) <- (bar :: Reader r a)
539 x <- bar
540 qux x
541```
543```{ .haskell .fragment }
544foo = do
545 -- (x :: a) <- (bar :: Reader r a)
546 x <- bar
547 -- (y :: b) <- (qux x :: Reader r b)
548 y <- qux x
549 return y
550```
552```{ .haskell .fragment }
553foo = bar >>= \x -> qux x >>= return
554```
556---
558```{ .haskell }
559type PricingEnv = Reader Markup
561getCoffeePrice :: Coffee -> PricingEnv Price
562getDiscount :: Coffee -> PricingEnv Price
563getPayment :: Price -> PricingEnv Payment
565payForCoffee :: Coffee -> PricingEnv Payment
566payForCoffee coffee =
567 coffee >>= getCoffeePrice >>= \coffeePrice ->
568 coffee >>= getDiscount >>= \discount ->
569 getPayment (coffeePrice - discount)
570```
572```{ .haskell .fragment }
573payForCoffee :: Coffee -> PricingEnv Payment
574payForCoffee coffee = do
575 coffeePrice <- getCoffeePrice coffee
576 discount <- getDiscount coffee
577 getPayment (coffeePrice - discount)
578```
580---
582## Let statement
584```{ .haskell }
585payForCoffee :: Coffee -> PricingEnv Payment
586payForCoffee coffee = do
587 coffeePrice <- getCoffeePrice coffee
588 discount <- getDiscount coffee
589 getPayment (coffeePrice - discount)
590```
593```{ .haskell .fragment }
594payForCoffee :: Coffee -> PricingEnv Payment
595payForCoffee coffee = do
596 coffeePrice <- getCoffeePrice coffee
597 discount <- getDiscount coffee
598 let amount = coffeePrice - discount
599 getPayment amount
600```
602---
604```{ .haskell }
605type PricingEnv = Reader Markup
606type Price = Int
608data Coffee = Coffee { getCoffeePrice :: Price }
610getCoffeePrice :: Coffee -> PricingEnv Price
611```
613```{ .haskell .fragment }
614data Reader r a = Reader { runReader :: r -> a}
615```
617```{ .haskell .fragment }
618ask :: Reader r r
619ask = Reader (\r -> r)
620```
622```{ .haskell .fragment }
623getCoffeePrice :: Coffee -> PricingEnv Price
624getCoffeePrice coffee = do
625 -- (markup :: Markup) <- (ask :: PricingEnv Markup)
626 markup <- ask
627 let coffePrice = getCoffeePrice coffee
628 return (coffee + markup)
629```
631---
633```{ .haskell }
634data Order = Order { orderCoffee :: Coffee, orderId :: Int }
635```
637```{ .haskell .fragment }
638createOrder :: Coffee -> Order
639```
641[Откуда брать `orderId`?]{ .fragment }
643```{ .haskell .fragment }
644createOrder :: Coffee -> Reader Int Order
645createOrder coffee = do
646 newId <- ask
647 return (Order coffee newId)
648```
650[🎉]{ .fragment }
652```{ .haskell .fragment }
653createOrders :: [Coffee] -> Reader Int [Order]
654```
656```{ .haskell .fragment }
657mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
658```
660```{ .haskell .fragment }
661createOrders = mapM createOrder
662```
664---
666```{ .haskell }
667createOrders :: [Coffee] -> Reader Int [Order]
668createOrders = mapM createOrder
669```
671[Все `id` будут одинаковые.]{ .fragment }
673[`Reader` эквивалентно глобальной **константе**.]{ .fragment }
675[Айдишники -- скорее глобальная **переменная**.]{ .fragment }
677[-- Но у нас же нет переменных!]{ .fragment }
679[-- Да, нет!]{ .fragment }
681---
683## State!
685```{ .haskell .fragment }
686data State s a = ... -- s -- само состояние
688get :: State s s
689put :: s -> State s ()
690```
692```{ .haskell .fragment }
693data State s a = State { runState :: s -> (a, s) }
695get :: State s s
696get = State (\s -> (s, s))
698put :: s -> State s ()
699put s = State (\_ -> ((), s))
700```
702---
704```{ .haskell }
705data State s a = State { runState :: s -> (a, s) }
706```
708```{ .haskell .fragment }
709class Monad (State s) where
710 return x = State (\s -> (x, s))
712 (>>=) :: State s a -> (a -> State s b) -> State s b
713 (State f) >>= g = State go
714 where
715 go s = runState (g a) s'
716 where
717 (a, s') = f s
718```
720---
722### Айдишники!
724```{ .haskell .fragment }
725getNewId :: State Int Int
726getNewId = do
727 newId <- get
728 put (newId + 1)
729 return newId
730```
732[-- Это какой-то процедурный языке получается!]{ .fragment }
734[-- Лучше!*]{ .fragment }
736```{ .haskell .fragment }
737createOrder :: Coffee -> State Int Order
738createOrder coffee = do
739 newId <- getNewId
740 return (Order coffee newId)
742createOrders :: [Coffee] -> State Int [Order]
743createOrders = mapM createOrder
744```
746---
748## Еще монады!
750```{ .haskell .fragment }
751class Monad [] where
752 return x = [x]
754 (>>=) :: [a] -> (a -> [b]) -> [b]
755 [] >>= _ = []
756 (a : aa) >>= f = f a <> (a >>= f)
757```
759[Контекст недетерменированности (нескольких вариантов)]{ .fragment }
761```{ .haskell .fragment }
762grid = do
763 x <- [1..5]
764 y <- [1..5]
765 return (x, y)
767-- [(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),(3,1),(3,2),(3,3),(3,4),(3,5),(4,1),(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)]
768```
770---
772Тривиальная монада
774```{ .haskell .fragment }
775data Identity a = Identity { runIdentity :: a }
777class Monad Identity where
778 return x = Identity x
780 (>>=) :: Identity a -> (a -> Identity b) -> Identity b
781 (Identity a) >>= f = Identity (f a)
782```
784---
786```{ .haskell }
787class Applicative m => Monad m where
788 return :: a -> m a
789 (>>=) :: m a -> (a -> m b) -> m b
790```
792[Монада -- перегрузка композиции функций.]{.fragment }
794```{ .haskell .fragment }
795class Functor m => Applicative m where
796 pure :: a -> m a
797 (<*>) :: m (a -> b) -> m a -> m b
798```
800[Аппликативный функтор -- перегрузка применения функций.]{.fragment }
802[-- Почему не `(a -> b) -> f a -> f b`.]{.fragment }
804[-- Это `fmap`. (И функции нескольких аргументов)]{.fragment }
806---
808```{ .haskell }
809(a -> b) -> f a -> f b
810```
812```{ .haskell .fragment }
813(a -> (b -> c)) -> f a -> f (b -> c)
814```
816```{ .haskell .fragment }
817getMarkup :: Env Markup
818getPrice :: Env Price
819getPayment :: Markup -> Price -> Payment
820```
822```{ .haskell .fragment }
823payment :: Env Payment
824payment = fmap getPayment getMarkup <*> getPrice
825```
827```{ .haskell .fragment }
828payment = fmap getPayment getMarkup <*> getPrice
829-- ^-------------^
830-- Env Markup -> Env (Price -> Payment)
831```
833```{ .haskell .fragment }
834(<$>) = fmap
835```
837```{ .haskell .fragment }
838payment = getPayment <$> getMarkup <*> getPrice
839```
841---
843```{ .haskell }
844(<*>) :: m (a -> b) -> m a -> m b
845mf <*> ma = do
846 f <- mf
847 a <- ma
848 return (f a)
849```
851```{ .haskell .fragment }
852ap :: Monad m => m (a -> b) -> m a -> m b
853ap mf ma = do
854 f <- mf
855 a <- ma
856 return (f a)
857```
859```{ .haskell .fragment }
860instance Monad ... where ...
862instance Applicative ... where
863 pure = return
864 (<*>) = ap
865```