#haskell
#haskell
Вопрос:
Я только что попал в 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. Приветствуется любой указатель.
Комментарии:
1. Экземпляр может быть получен с
-XDerivingVia
помощью :newtype Test a b = .. deriving (Functor, Foldable, Applicative, Monad, MonadFix, MonadZip) via Writer (Endo a)
. Вы можете запросить дополнительные экземпляры с помощью команды ghci::instances Writer (Endo _)
Ответ №1:
Ваша монада по сути является 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
и суммировать ее,>>=
чтобы получить правильное количество. - Вы можете повторно использовать монады из библиотек. Прямо сейчас вы изобретаете их заново. Тем не менее, то, что вы делаете прямо сейчас, — отличное упражнение для понимания того, как работают библиотеки, так что это совсем не бессмысленно!