Haskell 作为索引仿函数和单子的定理证明策略

Question

我正在尝试跟随 this blog post 在 Haskell 中制作一个简单的直觉定理证明语言。 van Bakel 先生建议使用索引单子来进行证明状态操作；这是索引 monad 的构建部分（相当于 Control.Monad.Indexed 中的定义）：

class IFunctor f where
  imap :: (a -> b) -> f j k a -> f j k b

class IFunctor m => IPointed m where
  ipure :: a -> m i i a

class IPointed m => IApplicative m where
  iap :: m i j (a -> b) -> m j k a -> m i k b

class IApplicative m => IMonad m where
  ibind :: (a -> m j k b) -> m i j a -> m i k b

ijoin :: IMonad m => m i j (m j k a) -> m i k a
ijoin = ibind id

infixr 1 =<<<
infixl 1 >>>=

(>>>=) :: IMonad m => m i j a -> (a -> m j k b) -> m i k b
m >>>= k = ibind k m

(=<<<) :: IMonad m => (a -> m j k b) -> m i j a -> m i k b
(=<<<) = ibind

我正在努力使用 Tactic 的以下定义正确实例化这些类：

data Tactic i j a = Tactic ((a -> j) -> i)

从 IFunctor 开始：

instance IFunctor Tactic where
  imap f (Tactic g) = Tactic (\ h -> g (h . f))

-- f :: a -> b
-- g :: (a -> j) -> i
-- h :: b -> j

现在要指出：

instance IPointed Tactic where
  ipure a = Tactic (\ h -> h a)

很简单。但是，我不能全神贯注于构建应用实例和单子实例。我对 monad 的猜测是

instance IMonad Tactic where
  ibind f (Tactic g) = Tactic (\ h -> imap g (imap h . f))

-- f :: a -> Tactic ((b -> k) -> j)
-- g :: (a -> j) -> i
-- h :: b -> k
-- RHS :: Tactic ((b -> k) -> i)

因为签名似乎已经签出。不过，我完全被应用实例难住了。

instance IApplicative Tactic where
  iap (Tactic f) (Tactic g) = Tactic (\ h -> ???)

-- f :: ((a -> b) -> j) -> i
-- g :: (a -> k) -> j
-- h :: b -> k
-- RHS :: Tactic ((b -> k) -> i)

你有什么建议？

编辑：我通过

获得了应用实例

instance IApplicative Tactic where
  iap (Tactic f) (Tactic g) = Tactic (\ h -> f (\ x -> g (h . x)))

-- f :: ((a -> b) -> j) -> i
-- g :: (a -> k) -> j
-- h :: b -> k
-- RHS :: Tactic ((b -> k) -> i)
-- x :: a -> b, h . x :: a -> k

感谢 Li-Yao 对 g 签名错误的提示，但我仍然停留在 bind 定义上。

Answer 1

提示：

评论中 g 的类型有错字（编辑：现已修复）
洞的类型是什么 ???？（查看下面的更多详细信息）
另一种方法是使用 imap 和 ibind 实现 iap，就像使用 fmap 和 [=22= 实现 (<*>) 一样]
Tactic 是延续 monad type Cont r a = (a -> r) -> r 的更多索引版本，所以如果您熟悉它，实现是相同的。

你可以 type-driven 编程 打个洞 _ 并查看编译器的错误信息。

instance IMonad Tactic where
  ibind f (Tactic g) = Tactic _

-- error: Found hole: _ :: (b -> k) -> i

当漏洞具有函数类型时，以 lambda 开头总是安全的：

instance IMonad Tactic where
  ibind f (Tactic g) = Tactic (\h -> _)

-- error: Found hole: _ :: i
-- Relevant bindings include
--        h :: b -> k
--        g :: (a -> j) -> i
--        f :: a -> Tactic j k b

产生 i 的唯一方法是将 g 应用于某些参数。

instance IMonad Tactic where
  ibind f (Tactic g) = Tactic (\h -> g _)

-- error: Found hole: _ :: a -> j

又是一个函数。

instance IMonad Tactic where
  ibind f (Tactic g) = Tactic (\h -> g (\a -> _))

-- error: Found hole: _ :: j
-- Relevant bindings include
--        a :: a
--        h :: b -> k
--        g :: (a -> j) -> i
--        f :: a -> Tactic j k b

没有明显的方法来生成 j，但是有一种方法可以使用我们刚刚介绍的 a 和 f :: a -> Tactic j k b（仔细检查后我们发现它实际上最终会产生 j）。然后我们可以 pattern-match 在结果 Tactic 上获得更多数据：

instance IMonad Tactic where
  ibind f (Tactic g) = Tactic (\h -> g (\a ->
    let Tactic p = f a in _))

-- error: Found hole: _ :: j
-- Relevant bindings include
--        p :: (b -> k) -> j
--        a :: a
--        h :: b -> k
--        g :: (a -> j) -> i
--        f :: a -> Tactic j k b

最后一步留作 reader 的练习。

Haskell 作为索引仿函数和单子的定理证明策略

Haskell theorem proving tactics as indexed functors and monads

monads

haskell

theorem-proving