FP_HSE2020Fall_10pr

Fp10pr.hs

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
-}