Может быть рекурсивным - PullRequest
Новая
       6

Может быть рекурсивным

3 голосов
/ 23 марта 2020

Может ли оператор рекурсивного выполнения быть десугарирован к серии операторов >>=? Если да, то как выглядит определение монады обратное состояние для >>=, когда оно не соответствует? 

instance MonadFix m => Monad (StateT s m) where
  return x = ...
  m >>= f = StateT $ \s -> do
    rec
      (x, s'') <- runStateT m s'
      (x', s') <- runStateT (f x) s
    return (x', s'')

1 Ответ

6 голосов
/ 23 марта 2020

Десугары с рекурсивным делом не только для серии вызовов >>=, но также, пока существует рекурсия, в вызов mfix. Именно в вызове mfix происходит вся рекурсивность через то, что технически называется "волшебная c волшебная пыль".

Если серьезно, то, как это происходит, отличается для каждой монады, и именно поэтому класс MonadFix, а не просто функция. Но важным моментом является то, что он может «магическим образом» передавать вам ваш собственный результат в качестве параметра, что возможно только из-за лени Haskell, и поэтому с ним нужно обращаться осторожно.

В общем, что-то вроде этого: 

do
    rec 
        x <- f y
        y <- g x
    return $ h x y

Desugars в это: 

mfix (\ ~(x, y) -> do
    x' <- f y
    y' <- g x'
    return (x', y')
)
>>= (\(x, y) -> h x y)

Таким образом, применительно к определению обратного состояния, это будет выглядеть так: 

m >>= f = StateT $ \s ->
  mfix (\ ~((x, s''), (x',s')) -> do
    (x0, s0'') <- runStateT m s'
    (x0', s0') <- runStateT (f x0) s
    return ((x0, s0''), (x0', x0'))
  )
  >>= (\(x, s''), (x',s') -> return (x', s''))

И отсюда мы можем просто отключить обычную do как обычно: 

m >>= f = StateT $ \s ->
  mfix (\ ~((x, s''), (x',s')) ->
    runStateT m s' >>= \(x0, s0'') ->
    runStateT (f x0) s >>= \(x0', s0') ->
    return ((x0, s0''), (x0', x0'))
  )
  >>= (\(x, s''), (x',s') -> return (x', s''))

(то есть, если я что-то не испортила - много галочек летает: -)

...