Skip to content

Instantly share code, notes, and snippets.

@deniok

deniok/Fp10pr.hs Secret

Created Nov 18, 2020
Embed
What would you like to do?
FP_HSE2020Fall_10pr
module Fp10pr where
import Control.Monad
--------------------------------------------------------
-- Разминка
{-
GHCi> Just 17 >>= \x -> Just (x < 21)
GHCi> [1,2,3] >>= \x -> [x, 10 * x]
GHCi> [1,2] >>= \n -> "ab" >>= \c -> return (n,c)
GHCi> (\bs -> do {b<-bs; when b []; return 42}) [True,False,False]
-}
-------------------------------------------------------
-- Монада списка
{-
Напишите реализацию функций filter и replicate,
используя монаду списка и do-нотацию.
-}
filter' p xs = do
undefined
replicate' n x = do
undefined
-------------------------------------------------------
-- Связь Monad и Functor
{-
Покажите, что оператор ($>) :: Functor f => f a -> b -> f b
из Data.Functor может быть выражен через монады:
-}
($>.) :: Monad m => m a -> b -> m b
xs $>. y = undefined
{-
Покажите, что каждая монада - это функтор.
Для этого выразите fmap через (>>=) и return:
-}
fmap' :: Monad m => (a -> b) -> m a -> m b
fmap' f xs = undefined
-------------------------------------------------------
-- Связь Monad и Applicative
{-
Покажите, что оператор (*>) :: Applicative f => f a -> f b -> f b!
может быть выражен через монады:
-}
(*>.) :: Monad m => m a -> m b -> m b
xs *>. ys = undefined
{-
Покажите, что liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
тоже может быть выражена через монады:
-}
liftA2' :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftA2' f xs ys = undefined
{-
GHCi> liftA2' (+) [10,20] [1,2]
[11,12,21,22]
-}
{-
Покажите, что каждая монада --- это аппликативный функтор.
Для этого выразите (<*>) :: Applicative f => f (a -> b) -> f a -> f b
на языке монад:
-}
(<*>.) :: (Monad m) => m (a -> b) -> m a -> m b
fs <*>. xs = do
undefined
{-
GHCi> Just (^2) <*>. Just 7
Just 49
-}
{-
Запишите эту реализацию (<*>.), через (>>=) и return, не используя do-нотацию.
-}
(<*>..) :: (Monad m) => m (a -> b) -> m a -> m b
fs <*>.. xs = undefined
-------------------------------------------------------
-- Монадические комбинаторы
{-
Вычислите значения выражений в GHCi:
-}
{-
GHCi> replicate 2 >=> replicate 3 $ 'x'
GHCi> (\x -> [x,x+10]) >=> (\x -> [x,2*x]) $ 1
GHCi> join ["aaa","bb"]
-}
{-
Выразите (>=>) через (>>=).
-}
(>=>.) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
g >=>. h = undefined
{-
Выразите join через (>>=).
-}
join' x = undefined
{-
GHCi> join' [[1,2],[3,4,5]]
[1,2,3,4,5]
-}
{-
Запишите join в do-нотации.
-}
join'' :: (Monad m) => m (m a) -> m a
join'' xss = do
undefined
{-
GHCi> join'' [[1,2],[3,4,5]]
[1,2,3,4,5]
-}
----------------------------------------
-- foldM
-- суммирование в пределах TinyInt (foldM в Maybe)
{-
GHCi> let isTiny x = x>=(-128) && x<128
GHCi> let (?+?) x y = let sum = x + y in if isTiny sum then Just sum else Nothing
GHCi> 3 ?+? 100
Just 103
GHCi> 90 ?+? 100
Nothing
GHCi> let sumTiny = foldM (?+?) 0
GHCi> sumTiny [1..15]
Just 120
GHCi> sumTiny [1..16]
Nothing
-}
-- (foldM в списках)
-- Описание доски
type Board = Int
-- Для данной конфигурации на доске
-- возвращает список всех достижимых за один ход конфигураций
next :: Board -> [Board]
next ini = filter (>= 0) . filter (<= 9) $ [ini+2, ini-1]
twoTurns :: Board -> [Board]
twoTurns ini = do
bd1 <- next ini
next bd1
threeTurns :: Board -> [Board]
threeTurns ini = do
bd1 <- next ini
bd2 <- next bd1
next bd2
doNTurns :: Int -> Board -> [Board]
doNTurns n ini = undefined
--------------------------------------------
-- Законы класса Monad
{-
В терминах композиций стрелок Клейсли законы класса Monad имеют особенно простой вид
(1) return >=> k == k
(2) k >=> return == k
(3) (u >=> v) >=> w == u >=> (v >=> w)
Переведите эти законы класса Monad на язык (>>=), используя написанную ранее
реализацию (>=>) через (>>=). В результате должны получится классические законы:
(1') return a >>= k == k a
(2') m >>= return == m
(3') (m >>= v) >>= w == m >>= (\x -> v x >>= w)
-}
{-
Выразите (>=>) через join (и fmap).
-}
(>=>..) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
g >=>.. h = undefined
{-
Переведите законы класса Monad на язык join и fmap,
используя представление (>=>) через join (и fmap).
В результате должны получится законы:
(1'') join . return == id
(2'') join . fmap return == id
(3'') join . join == join . fmap join
Совет: в преобразованиях можно использовать закон функторов
fmap (f . g) == fmap f . fmap g
и "свободные теоремы" для типов return и join
return . f == fmap f . return
join . fmap (fmap f) == fmap f . join
-}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment