如何实现索引核心风格的索引状态monad？

Question

我试图理解index-core风格中的索引monad .我陷入了一个悖论,即在构建一些例子之前我无法理解这些原则,在理解这些原理之前我无法构建例子.

我正在尝试构建一个索引状态monad.到目前为止,我的直觉告诉我它应该是这样的

type a :* b = forall i. (a i, b i)
newtype IState f a i = IState { runIState :: f i -> (a :* f) }

并且我可以通过适当的设置f = Identity和选择来恢复"受限制"状态monad a:

type IState' s s' a = IState Identity (a := s') s

但我感到很失落.有人可以确认我的线路正确吗？

我在索引的延续monad上使用类似的问题作为指导,但我认为它不够接近.

Answer 1

我们可以从链接的索引答案中复制加布里埃尔的论点Cont。如果标准索引状态 monad 是

State s s' a = s -> (a, s')

然后我们分阶段概括它。首先通过使用Identity来反映具体类型s并s'作为索引类型空间中的纤维Identity。

State s s' a = s          -> (a, s')
             ~ Identity s -> (a, Identity s')

然后通过将值类型概括a为索引类型以及“目标”索引，类型s'。

             ~ Identity s -> (a   , Identity s')
             ~ Identity s -> (a s', Identity s')

然后使用存在类型来擦除目标索引。我们稍后会恢复它。

data a :* b = forall i . P (a i) (b i)

  Identity s -> (a s', Identity s') 
~ Identity s -> P a Identity

最后，我们会注意到Identity是状态空间的索引类型和a值空间的索引类型，所以我们可以写IState为

newtype IState s -- indexed state space
               a -- indexed value space
               i -- index
  = IState { runIState :: s i -> a :* s }
--   State { runState  :: s   -> (a, s) }        for comparison

为什么使用存在量化对而不是普遍量化对？第一个推动来自这样一个事实：与 相关的指数a在 中出现为正值IState，而在 中出现为负值ICont。第二个提示来自写作returnI。如果我们使用通用量化版本并尝试写returnI

newtype IState' s a i = IState' { runIState' :: s i -> (forall i . (a i, s i)) }

returnI :: a i -> IState' s a i
returnI a = IState' (\si -> (?forget a, ?forget si))

我们需要这个forget函数来忘记有关索引的所有信息。

但是，如果我们改为使用存在量化对，则由该返回对的构造函数（即值的实现者IState）来选择索引。这让我们可以实例化IFunctor并IMonad

instance IFunctor (IState s) where
  -- fmapI :: (a :-> b) -> IState s a :-> IState s b
  fmapI phi (IState go) = IState $ \si -> 
    case go si of 
      P ax sx -> P (phi ax) sx

instance IMonad (IState s) where
  -- returnI :: a :-> IState s a
  return ai = IState (\si -> P ai si)

  -- bindI :: (a :-> IState s b) -> (IState s a :-> IState s b)
  bindI f m = IState $ \s ->
    case runIState m s of
      P ax sx -> runIState (f ax) sx

使用这个存在对的唯一缺点是它......实际使用起来相当困难。例如，我们真的希望能够使用“指向”索引类型构造函数(:=)来修复已知索引并从存在对中投影。

one :: (a := i :* b) -> a
two :: (a := i :* b) -> b i

不幸的是，即使我们知道存在主义是什么，Haskell 也不够聪明，无法强制存在主义，因此第二个预测的实现令人不快

one :: (a := i :* b) -> a
one (P (V a) _) = a

two :: (a := i :* b) -> b i
two (P _ s) = unsafeCoerce s

最后，证据就在布丁中。我们可以用来IState实现我们习惯看到的状态效果的标准补充。

-- Higher order unit type
data U1 a = U1

put :: s i -> IState s U1 j
put s = IState (\_ -> P U1 s)

get :: IState s s i
get = IState (\s -> P s s)

并使用它们来实现一些通用的高阶组合器，例如修改（它需要显式类型签名，但您可以通过一些思考从实现中手动计算）

modify :: (s :-> s) -> IState s U1 i
modify f = get ?>= put . f

然而，除此之外，我们还有其他表示组合器的方法，由于 的限制，这些组合器的索引更加明确(:=)。这对于传递有关索引的更多信息很有用。

put' :: s i1 -> IState s (() := i1) i
put' s = IState (\_ -> P (V ()) s)

get' :: IState s (s i := i) i
get' = IState (\s -> P (V s) s)

modify' :: (s -> s) -> IState (s := j) (() := j) i
modify' f = get >>= put' . V . f

modify'' :: (s i -> s k) -> IState s (() := k) i
modify'' f = get' >>= put' . f

最后，我们可以使用所有这些来实现一个示例。例如，我们可以通过文件句柄状态构建索引类型，但这并不是非常有用。

data Open
data Closed
data Any a

data St where
  So :: Int -> St Open
  Sc ::        St Closed
  Sa :: a   -> St (Any a)

getAny :: St (Any a) -> a
getAny (Sa a) = a

然后我们就可以构建

open :: String -> File Closed Open ()
open name = put' (SOpen $ getHandle name) where
  getHandle = length

close :: File Open Closed ()
close = put' SClosed

getHandle :: File Open Open Int
getHandle = do
  SOpen i <- get'
  return i

putA :: a -> File x (Any a) ()
putA a = put' (SAny a)

在哪里

open "foo" >> close                -- typechecks
open "foo" >> close >> close       -- fails
open "foo" >> getHandler >> close  -- typechecks
open "foo" >> close >> getHandler  -- fails

和类似的事情

> one $ runIState (do putA 4
                      sa <- get'
                      return (getAny sa)) Sc
4
> one $ runIState (do putA ()
                      sa <- get'
                      return (getAny sa)) Sc
()
> one $ runIState (do putA 4
                      putA ()
                      sa <- get'
                      return (getAny sa)) Sc
()

所有工作。