Блог

Я только что попал в Monads и пытался преобразовать простую функцию Фибоначчи в новую, используя Monads. В дополнение к получению числа Фибоначчи, я также хочу получить количество рекурсий. Итак, в основном я пытаюсь объединить две функции

 rec :: Int -> Int
rec n
  | n == 0 = 0
  | n == 1 = 0
  | otherwise = fib (n-1)   fib (n-2)   2

fib :: Int -> Int
fib n
  | n == 0 = 0
  | n == 1 = 1
  | otherwise = fib (n-1)   fib (n-2)
 

к чему-то вроде этого

 import Control.Monad

newtype Test a b = Test { getTest :: (b, a -> a) }
  deriving Functor

gett :: Test a b -> (b, a -> a)
gett =  getTest

instance Applicative (Test a) where
   pure = return
   (<*>) = liftM2 ($)

instance Monad (Test a) where
   return :: b -> Test a b
   --something like ?: return b = Test $ (b,a -> a) 

   (>>=) :: Test a b -> (b -> Test a c) -> Test a c
   --something like ?: Test b >>= f = Test $  a -> gett(f a)

add :: (a -> a) -> Test a ()
-- something like ?: add a = Test a ()

getFib :: Test a b -> b   --getFib (fib 10) -> 55
getFib = fst . getTest

getRec :: Test a b -> a -> a  --getRec (fib 10) 0 -> 176
getRec = snd . getTest

fib :: Int -> Test Int Int
fib n
  | n == 0 = return 0
  | n == 1 = return 1
  | otherwise = do
                a <- fib (n-1)
                add ( 2)
                b <- fib (n-2)
                return (a b)
 

Я застрял на реализации return bind теста newType и add. Моя идея заключается в том, что тестовая монада будет накапливать тестовую функцию и фокусироваться на вычислении b. Приветствуется любой указатель.

Ваша монада по сути является Writer (Endo a) монадой, вплоть до изоморфизма.

Предложенные вами определения в основном верны:

 instance Monad (Test a) where
   return :: b -> Test a b
   --something like ?: 
   return b = Test $ (b,a -> a) 
 

Да, это правильно. Идентификатор является нейтральным элементом моноида endo.

    (>>=) :: Test a b -> (b -> Test a c) -> Test a c
   --something like ?: 
   Test b >>= f = Test $  a -> gett(f a)
 

Нет, это неверно, поскольку вы отбрасываете значение b и не создаете пару. Вы хотите что-то вроде

 Test (x, f) >>= g = Test (x', f' . f)    -- or f . f'
   where Test (x', f') = g x
 

Вместо,

 add :: (a -> a) -> Test a ()
-- something like ?: 
add a = Test a ()
 

выглядит правильно.

Тем не менее, вот несколько предложений:

• Для вашего fib примера использование вашей монады кажется излишним. Вы используете Writer (Endo a) , когда Writer (Sum Int) будет достаточно. Вместо того, чтобы хранить функцию a -> a в вашем монадическом типе, вы можете просто сохранить Int и суммировать ее, >>= чтобы получить правильное количество.
• Вы можете повторно использовать монады из библиотек. Прямо сейчас вы изобретаете их заново. Тем не менее, то, что вы делаете прямо сейчас, — отличное упражнение для понимания того, как работают библиотеки, так что это совсем не бессмысленно!