git.iko.soy/ikoHSE/sc-lectures
on master help sign in
ikoHSE/sc-lectures/4.md
857 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 => Applicative f where
19 (<*>) :: f (a -> b) -> f a -> f b
20 pure :: a -> f a
21```
23```{ .haskell .fragment }
24class Applicative f => Monad f where
25 (>>=) :: f a -> (a -> f b) -> f b
26 return :: a -> f a
27```
29---
31## Either
33```{ .haskell }
34data Either a b = Left a | Right b
35```
37```{ .haskell .fragment }
38throwError :: e -> Either e a
39throwError = Left
40```
42```{ .haskell .fragment }
43data PaymentError = InsufficientBalance
45pay :: Balance -> Price -> Either PaymentError Balance
46pay balance price = do
47 let newBalance = balance - price
48 when (newBalance < 0) (throwError InsufficientBalance)
49 return newBalance
50```
52```{ .haskell .fragment }
53when :: (Applicative f) => Bool -> f () -> f ()
54when p s = if p then s else pure ()
55```
57---
59# State
61```{ .haskell }
62data State s a = State { runState :: s -> (a, s) }
63```
65```{ .haskell .fragment }
66get :: State s s
67get = State (\s -> (s, s))
69put :: s -> State s ()
70put s = State (\_ -> (_, s))
71```
73---
75```{ .haskell }
76getNewId :: State TransactionId TransactionId
77getNewId = do
78 newId <- get
79 put (succ newId)
80 return newId
82data Transaction = Transaction
83 { transactionId :: TransactionId,
84 transactionAmount :: Price
85 }
86```
88```{ .haskell .fragment }
89registerPayment :: Price -> State TransactionId Transaction
90registerPayment price = do
91 newId <- getNewId
92 return Transaction
93 { transactionId = newId
94 transactionAmount = price
95 }
96```
98---
100```{ .haskell }
101registerPayment :: Price -> State TransactionId Transaction
102pay :: Balance -> Price -> Either PaymentError Balance
103```
105```{ .haskell .fragment }
106payAndRegister balance price = do
107 newBalance <- pay balance price
108 transacation <- registerPayment price
109 return (newBalance, transaction)
110```
112```{ .haskell .fragment }
113(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
114```
116```{ .haskell .fragment }
117-- Такого нет
118(>=>)
119 :: (Monad m, Monad n)
120 => (a -> m b) -> (b -> n c) -> (a -> ? c)
121```
123[На каждый чих нужно создавать новый тип?]{.fragment}
125---
127Мы хотим:
1291. Отделить эффекты от конкретной монады
1302. Получить возможность комбинировать разные эффекты
132[(И чтобы не надо было на каждый случай новый тип создавать)]{.fragment}
134---
136```{ .haskell }
137registerPayment :: Price -> State TransactionId Transaction
138pay :: Balance -> Price -> Either PaymentError Balance
139```
141```{ .haskell .fragment }
142registerPayment
143 :: MonadState TransactionId m
144 => Price -> m Transaction
145pay
146 :: MonadError PaymentError m
147 => Balance -> Price -> m Balance
148```
150```{ .haskell .fragment }
151payAndRegister
152 :: (MonadState TransactionId m, MonadError PaymentError m)
153 => Balance -> Price -> m (Balance, Transaction)
154```
156---
158На самом деле мы хотим чтобы понятие "state" не было привязано к конкретной монаде.
160[Мы хотим чтобы "базовые операции" не были привязаны к конкретной монаде.]{.fragment}
162```{ .haskell .fragment }
163-- Было
164get :: State s s
165put :: s -> State s ()
166```
168```{ .haskell .fragment }
169-- Стало
170get :: MonadState s m => m s
171put :: MonadState s m => s -> m ()
172```
174---
176## MonadState
178---
180<!--
181```{ .haskell .fragment }
182class MonadState s m | m -> s where
183 get :: m s
184 put :: s -> m ()
185```
187[`m -> s` означает что для каждого `m` может быть строго один `s`.]{ .fragment }
189[(Это нужно чтобы когда вы делаете `get` было понятно что вам возвращать.)]{ .fragment } -->
190```{ .haskell }
191class Monad m => MonadState s m where
192 get :: m s
193 put :: s -> m ()
194```
196```{ .haskell .fragment }
197data State s a = State { runState :: s -> (a, s) }
199instance MonadState s (State s) where
200 get = State (\s -> (s, s))
201 put s = State (\_ -> ((), s))
202```
204```{ .haskell .fragment }
205getNewId :: MonadState TransactionId m => m TransactionId
206getNewId = do
207 newId <- get
208 put (succ newId)
209 return newId
210```
212```{ .haskell .fragment }
213registerPayment :: Price -> State TransactionId Transaction
214registerPayment price = do
215 newId <- getNewId
216 return Transaction
217 { transactionId = newId
218 transactionAmount = price
219 }
220```
222---
224## MonadError
226```{ .haskell .fragment }
227class Monad m => MonadError e m where
228 throwError :: e -> m a
229 catchError :: m a -> (e -> m a) -> m a
230```
232```{ .haskell .fragment }
233data Either e a = Left e | Right a
235instance MonadError e (Either e) where
236 throwError e = Left e
238 catchError (Left e) f = f e
239 catchError (Right a) _ = Right a
240```
242---
244Мы хотим:
2461. ~~Отделить эффекты от конкретной монады~~
2472. Получить возможность комбинировать разные эффекты
249---
251Начнем с функторов
253```{ .haskell .fragment }
254data Compose f g a = Compose { getCompose :: f (g a) }
255```
257```{ .haskell .fragment }
258type ErrorStateFunctor a =
259 Compose (Either PaymentError) (State TransactionId) a
260```
262```{ .haskell .fragment }
263-- Compose
264-- { getCompose ::
265-- Either PaymentError (State TransactionId a)
266-- }
267```
269```{ .haskell .fragment }
270instance (Functor f, Functor g) =>Functor (Compose f g) where
271 fmap f (Compose x) = Compose (fmap (fmap f) x)
272```
274[🎉]{ .fragment }
276[(`Applicative` тоже можно -- можете сами попробовать)]{ .fragment }
278---
280К монадам!
282```{ .haskell .fragment }
283instance (Monad f, Monad g) => Monad (Compose f g) where
284 return x = Compose (return (return x))
285 (Compose x) >>= f = ???
286```
288[😢]{ .fragment }
290[Все равно хочется!]{ .fragment }
292---
295```{ .haskell }
296data Compose f g a = Compose { getCompose :: f (g a) }
297```
299[Для такого не можем]{ .fragment }
302```{ .haskell .fragment }
303data ErrorState e s a =
304 ErrorState { runErrorState :: State s (Either e a) }
305```
307[А для такого можем!]{ .fragment }
309```{ .haskell .fragment }
310(State s (Either e a)) ~ (s -> Either e (a, s))
311```
313---
315```{ .haskell }
316data ErrorState e s a =
317 ErrorState { runErrorState :: State s (Either e a) }
318```
320[Хочется чтобы можно было не только `Either`!]{ .fragment }
322```{ .haskell .fragment }
323data State s a = State { runState :: s -> (a, s) }
324```
326```{ .haskell .fragment }
327data StateT s m a = StateT { runStateT :: s -> m (a, s) }
328```
330```{ .haskell .fragment }
331instance (Monad m) => Monad (StateT s m) where
332 return a = StateT $ \ s -> return (a, s)
334 m >>= f = StateT (\s -> do
335 (a, s') <- runStateT m s
336 runStateT (f a) s'
337 )
338```
341---
343## Transformers!
345![](images/transformer.gif){height=400px}
347---
349## Вернем операции!
351```{ .haskell }
352class Monad m => MonadState s m where
353 get :: m s
354 put :: s -> m ()
355```
357```{ .haskell .fragment }
358data StateT s n a = StateT { runStateT :: s -> n (a, s) }
359```
361```{ .haskell .fragment }
362instance Monad n => MonadState s (StateT s n) where
363 get = StateT (\s -> return (s, s))
364 put s = StateT (\_ -> return ((), s)
365```
367---
369## Error
371```{ .haskell .fragment }
372data ExceptT e n a = ExceptT { runExceptT :: n (Either e a) }
373```
375```{ .haskell .fragment }
376class Monad m => MonadError e m where
377 throwError :: e -> m a
378 catchError :: m a -> (e -> m a) -> m a
379```
381```{ .haskell .fragment }
382instance Monad n => MonadError e (ExceptT e n) where
383 throwError e = ExceptT (return (Left e))
385 catchError (ExceptT n) f = ExceptT $ do
386 x <- n
387 case x of
388 Left e -> runExceptT (f e)
389 Right a -> return (Right a)
390```
392---
394```{ .haskell }
395class Monad m => MonadError e m where
396 throwError :: e -> m a
397 catchError :: m a -> (e -> m a) -> m a
398```
400```{ .haskell .fragment }
401data PaymentError = InsufficientBalance
403pay :: MonadError e m => Balance -> Price -> m Balance
404pay balance price = do
405 let newBalance = balance - price
406 when (newBalance < 0) (throwError InsufficientBalance)
407 return newBalance
408```
410---
412## The states
415```{ .haskell .fragment }
416data State s a = State { runState :: s -> (a, s) }
417```
419```{ .haskell .fragment }
420data StateT s m a = StateT { runStateT :: s -> m (a, s) }
421```
423[🤔]{.fragment}
425---
427Напоминалочка:
429```{ .haskell .fragment }
430data Identity a = Identity { runIdentity :: a }
431```
433```{ .haskell .fragment }
434(Identity a) ~ a
435```
437```{ .haskell .fragment }
438data State s a = State { runState :: s -> (a, s) }
440data StateT s m a = StateT { runStateT :: s -> m (a, s) }
441```
443```{ .haskell .fragment }
444(StateT s Identity a) ~ (s -> Identity (a, s))
445```
447[🤔]{.fragment}
449```{ .haskell .fragment }
450(s -> Identity (a, s)) ~ (s -> (a, s)) ~ (State s a)
451```
453```{ .haskell .fragment }
454type State s a = StateT s Identity a
455```
457---
459```{ .haskell }
460data ExceptT e n a = ExceptT { runExceptT :: n (Either e a) }
462data StateT s m a = StateT { runStateT :: s -> m (a, s) }
464class Monad m => MonadError e m where
465 throwError :: e -> m a
466 catchError :: m a -> (e -> m a) -> m a
468class Monad m => MonadState s m where
469 get :: m s
470 put :: s -> m ()
471```
473Пришли к тому, с чего начинали, только еще сложнее
475---
4771. ~~Отделить эффекты от конкретной монады~~
4782. Получить возможность комбинировать разные эффекты
480---
482```{ .haskell }
483foo :: ExceptT Bool (State Char) Int
484foo = do
485 c <- get -- :: State Char Char
486 throwError True -- :: ExceptT Bool (State Char) Int
487```
489```{ .haskell .fragment }
490(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
492-- Такого нет
493(>=>)
494 :: (Monad m, Monad n)
495 => (a -> m b) -> (b -> n c) -> (a -> ? c)
496```
498```{ .haskell .fragment }
499lift :: State Char a -> ExceptT Bool (State Char) a
500```
502```{ .haskell .fragment }
503foo :: ExceptT Bool (State Char) Int
504foo = do
505 c <- lift get -- :: ExceptT Bool (State Char) Int
506 throwError True -- :: ExceptT Bool (State Char) Int
507```
509---
511```{ .haskell }
512class MonadTrans t where
513 lift :: (Monad m) => m a -> t m a
514```
516```{ .haskell .fragment }
517lift :: State Char a -> ExceptT Bool (State Char) a
518-- (m ) a -> (t ) (m ) a
519```
521```{ .haskell .fragment }
522instance MonadTrans (StateT s) where
523 lift m = StateT $ \ s -> do
524 a <- m
525 return (a, s)
526```
528```{ .haskell .fragment }
529instance MonadTrans (ExceptT e) where
530 lift m = ExceptT (fmap Right m)
531```
533```{ .haskell .fragment }
534foo :: ExceptT Bool (State Char) Int
535foo = do
536 c <- lift get
537 throwError True
538```
540---
542Но хочется чтобы без `lift` 🙂
544```{ .haskell .fragment }
545foo :: ExceptT Bool (State Char) Int
546foo = do
547 c <- get
548 throwError True
549```
551[Нужен инстанс `MonadState` для `ExceptT`]{ .fragment }
553```{ .haskell .fragment }
554instance MonadState s n => MonadState s (ExceptT e n) where
555 get = lift get
556 put s = lift (put s)
557```
559---
562```{ .haskell }
563registerPayment
564 :: State TransactionId m
565 => Price -> m Transaction
566pay
567 :: MonadError PaymentError m
568 => Balance -> Price -> m Balance
569```
571```{ .haskell .fragment }
572payAndRegister
573 :: (State TransactionId m, MonadError PaymentError m)
574 => Balance -> Price -> m (Balance, Transaction)
575payAndRegister balance price = do
576 newBalance <- pay balance price
577 transacation <- registerPayment price
578 return (newBalance, transaction)
579```
581---
583Как это "запускать"?
585```{ .haskell }
586payAndRegister
587 :: (State TransactionId m, MonadError PaymentError m)
588 => Balance -> Price -> m (Balance, Transaction)
589```
591```{ .haskell .fragment }
592myBalance :: Balance
593myPrice :: Price
595balanceAndTransaction
596 :: Either PaymentError (Balance, Transaction)
597```
599```{ .haskell .fragment }
600data ExceptT e n a = ExceptT { runExceptT :: n (Either e a) }
601data StateT s n a = StateT { runStateT :: s -> n (a, s) }
602```
605```{ .haskell .fragment }
606balanceAndTransaction =
607 runStateT 0 (payAndRegister myBalance myPrice)
608```
610---
612```{ .haskell }
613payAndRegister
614 :: (State TransactionId m, MonadError PaymentError m)
615 => Balance -> Price -> m (Balance, Transaction)
617data StateT s n a = StateT { runStateT :: s -> n (a, s) }
618```
620```{ .haskell .fragment }
621balanceAndTransaction
622 :: Either PaymentError (Balance, Transaction)
623balanceAndTransaction =
624 flip runStateT 0 (payAndRegister myBalance myPrice)
625```
627```{ .haskell .fragment }
628 flip runStateT 0 (payAndRegister myBalance myPrice)
629-- ^-------------^
630-- StateT TransactionId n a -> n a
631```
633```{ .haskell .fragment }
634-- (n a) ~ (Either PaymentError (Balance, Transaction))
635```
637```{ .haskell .fragment }
638flip runStateT 0 (payAndRegister myBalance myPrice)
639-- ^--------------------------------^
640-- StateT TransactionId
641-- (Either PaymentError)
642-- (Balance, Transaction)
643```
645---
647```{ .haskell }
648payAndRegister
649 :: (State TransactionId m, MonadError PaymentError m)
650 => Balance -> Price -> m (Balance, Transaction)
652data ExceptT e n a = ExceptT { runExceptT :: n (Either e a) }
653data StateT s n a = StateT { runStateT :: s -> n (a, s) }
654data Identity a = Identity { runIdentity :: a }
655```
657```{ .haskell .fragment }
658balanceAndTransaction
659 :: Either PaymentError (Balance, Transaction)
660balanceAndTransaction =
661 (runIdentity . runExceptT . flip runStateT 0)
662 (payAndRegister myBalance myPrice)
663```
665---
667А теперь мы пойдем в совершенно другом направлении!
669---
671## Напоминалочка
673```{ .haskell .fragment }
674class Show a where
675 show :: a -> String
676```
678```{ .haskell .fragment }
679data Foo = Bar { barInt :: Int }
680 deriving Show
681```
683```{ .haskell .fragment }
684show (Bar 8)
685-- Bar {barInt = 8}
686```
688---
690## Read
692Обратная операция к `show`
694```{ .haskell }
695read :: Read a => String -> a
696```
698```{ .haskell .fragment }
699class Read a where
700 readsPrec
701 :: -- | Приоритет контекста выражения
702 Int
703 -> String
704 -> [(a, String)]
705```
707```{ .haskell .fragment }
708data Foo = Bar { barInt :: Int }
709 deriving (Show, Read)
710```
712```{ .haskell .fragment }
713read "Bar {barInt = 8}"
714-- Bar { barInt = 8 }
715```
717---
719# Монады
7211. Базовые операции монады (эффекты)
723[`MonadState`, `MonadErrror`]{ .fragment }
7252. Конкретные монады (переносчик) (и способы их "разворачивать")
727[`StateT` (`runStateT`), `Either`, `ExceptT` (`runExceptT`)]{ .fragment }
729[Переводят эффекты в pure код]{ .fragment }
731---
733# Монада `IO`
735[Обладает только базовыми операциями]{ .fragment }
736[(Невозможно перевести в pure код)]{ .fragment }
738```{ .haskell .fragment }
739getLine :: IO String
741putStrLn :: String -> IO ()
742```
744```{ .haskell .fragment }
745type FilePath = String
747readFile :: FilePath -> IO String
749writeFile :: FilePath -> String -> IO ()
750```
752---
754```{ .haskell }
755add10FromConsole :: IO ()
756add10FromConsole = do
757 x <- getLine
758 let
759 n :: Int
760 n = read x
761 putStrLn (show (n + 10))
762```
764---
766"Разворачивать" `IO` умеет только рантайм.
768```{ .haskell .fragment }
769main :: IO ()
770main = add10FromConsole
771```
773```{ .fragment }
774> 10
77520
776```
778---
780```{ .haskell }
781-- Как 'read', но не взрывается в рантайме
782readMaybe :: Read a => String -> Maybe a
783```
785```{ .haskell .fragment }
786accumulateNums :: StateT Int IO ()
787accumulateNums = do
788 x <- lift getLine
789 case (readMaybe x :: Int) of
790 Nothing -> do
791 s <- get
792 lift (putStrLn (show s))
793 Just x' -> do
794 modify (+ x')
795 accumulateNums
796```
798```{ .haskell .fragment }
799main :: IO ()
800main = flip runStateT 0 accumulateNums
801```
803```{ .fragment }
804> 8
805> 3
806> a
80711
808```
810---
812```{ .haskell }
813accumulateNums :: StateT Int IO ()
814```
816```{ .haskell .fragment }
817-- Хочется так, но где тут взять 'IO'?
818accumulateNums :: MonadState Int m => m ()
819```
821[Трансформера `IO` нет.]{ .fragment }
823[Тогда `lift`!]{ .fragment }
825[Но `lift` поднимает строго на один уровень.]{ .fragment }
827---
829```{ .haskell }
830class MonadIO m where
831 liftIO :: IO a -> m a
832```
834```{ .haskell .fragment }
835accumulateNums :: (MonadState Int m, MonadIO m) => m ()
836accumulateNums = do
837 x <- liftIO getLine
838 case (readMaybe x :: Int) of
839 Nothing -> do
840 s <- get
841 liftIO (putStrLn (show s))
842 Just x' -> do
843 modify (+ x')
844 accumulateNums
845```
847```{ .haskell .fragment }
848main :: IO ()
849main = flip runStateT 0 accumulateNums
850```
852```{ .fragment }
853> 8
854> 3
855> a
85611
857```