動機

state monad是left 2 right，對應到iteration (左遞迴) reverse state monad是right 2 left，對應到recursion (右遞迴)

derive state monad

轉成iteration

def s(l):
    if not l:
        return 0
    else:
        return l[0] + s(l[1:])

def s2(l, acc=0):
    if not l:
        return acc
    else:
        return s2(l[1:], l[0] + acc)

把acc往下推

def s3(l):
    if not l:
        return lambda acc: acc
    else:
        return lambda acc: s3(l[1:])(l[0] + acc)

用成類似monad的樣子

def ret(acc):
    return acc

def bind(mx, f):
    return lambda acc: mx(f(acc))

def s4(l):
    if not l:
        #return ret(0)
        return ret
    else:
        return bind(s4(l[1:]), lambda acc: l[0] + acc)

def s2(l, acc=0):
    if not l:
        return acc
    else:
        return s2(l[1:], l[0] + acc)

到s4其實就推的差不多了，但是ret其實不符合monad的return定義 所以我們改一下

real state monad

def ret2(acc):
    return lambda ignored_acc: acc

def bind2(mx, f):
    return lambda acc: f(mx(acc))

def s5(l):
    if not l:
        return ret2(0)
    else:
        return bind2(s5(l[1:]), lambda acc: l[0] + acc)

def s(l):
    if not l:
        return 0
    else:
        return l[0] + s(l[1:])

如果去走一下整個過程會發現他與遞迴版的很像，因為0是從底部給，不像之前是依靠外面給

state monad

state monad其實就是會留一層acc在外層等人給 剩下就是找順序來，所以是left 2 right

newtype State s a = State { runState :: s -> (a,s) }

instance Functor (State s) where
  (<$>) :: (a -> b) -> State s a -> State s b
  (<$>) fn (State sa) = State (\s0 -> let (a, s1) = sa s0 in (fn a, s1))
 
instance Applicative (State s) where
  pure  :: a -> State s a
  pure a = State (\s -> (a,s))
  (<*>) :: State s (a -> b) -> State s a -> State s b
  (<*>) (State sa) (State sb) =
    State (\s0 -> let (fn, s1) = sa s0
                      (a,  s2) = sb s1
                  in (fn a, s2))

instance Monad (State s) where
  (>>=) :: State s a -> (a -> State s b) -> State s b
  (>>=) (State sa) fn =
    State (\s0 -> let (a, s1)  = sa s0 -- 先往下遞迴
                      State sb = fn a -- 拿到的往f灌
                  in sb s1) -- 接回去

reverse state monad

reverse的話就是先往右手邊遞迴，做出right 2 left的效果

instance Applicative (ReverseState s) where
  pure x = ReverseState $ (,) x
  mf <*> mx =
    ReverseState $ \s ->
      let (x, future) = runReverseState mx s -- 先往右遞迴
          (f, now) = runReverseState mf future -- 終於回來了，用前面的值灌回來
      in (f x, now)

如果用與前面一樣的想法(先做右邊)，去設計monad 會遇到一個問題

我們只有f要怎麼右遞迴

instance Monad (ReverseState s) where
  mx >>= f =
    ReverseState $ \s ->
      let (b, future) = runReverseState ?? s
          (a, now) = runReverseState mx future
      in (b, now)
  1. 我們目前的值，其實是在mx之中，所以要想方法拿到mx裡面的值
  2. 要拿mx的值要透過runReverseState
  3. 不是已經call過了嗎 (a, now) = runReverseState mx future

所以把這個值餵回去f就好了

instance Monad (ReverseState s) where
  mx >>= f =
    ReverseState $ \s ->
      let (b, future) = runReverseState (f a) s
          (a, now) = runReverseState mx future
      in (b, now)

Q: 怎麼可能有futrue又有a，這樣不是互相依賴嗎? A: haskell是lazy的

Ref

The Curious Time-Traveling Reverse State Monad You Could Have Invented The State Monad