VerifiedFunctor - 证明映射 (map g) x = x

Question

我正在尝试证明关于 VerifiedFunctor 接口的声明（一个 Functor 其中 map 方法尊重身份和组合）：

interface Functor f => VerifiedFunctor (f : Type -> Type) where
    functorIdentity : {a : Type} -> (g : a -> a) -> ((v : a) -> g v = v) ->
                      (x : f a) -> map g x = x

这是声明（逻辑上说 map . map 对于两个给定的函子也尊重身份）：

functorIdentityCompose : (VerifiedFunctor f1, VerifiedFunctor f2) =>
                         (g : a -> a) -> ((v : a) -> g v = v) ->
                         (x : f2 (f1 a)) -> map (map g) x = x
functorIdentityCompose fnId prId = functorIdentity (map fnId) (functorIdentity fnId prId)

但是，我收到以下错误：

Type mismatch between
        (x : f1 a) -> map fnId x = x (Type of functorIdentity fnId prId)
and
        (v : f a) -> map fnId v = v (Expected type)

Specifically:
        Type mismatch between
                f1 a
        and
                f a

我试图指定所有隐式参数：

functorIdentityCompose : (VerifiedFunctor f1, VerifiedFunctor f2) =>
                         {a : Type} -> {f1 : Type -> Type} -> {f2 : Type -> Type} ->
                         (g : a -> a) -> ((v : a) -> g v = v) -> (x : f2 (f1 a)) ->
                         map {f=f2} {a=f1 a} {b=f1 a} (map {f=f1} {a=a} {b=a} g) x = x

...但是又出现了另一个错误：

When checking argument func to function Prelude.Functor.map:
        Can't find implementation for Functor f15

所以你知道这里有什么问题以及如何证明这个说法吗？

Answer 1

这是一个启发式方法：当 "obvious" 事情不起作用时...eta-expand！所以这有效：

functorIdentityCompose : (VerifiedFunctor f1, VerifiedFunctor f2) =>
  (g : a -> a) -> ((v : a) -> g v = v) ->
  (x : f2 (f1 a)) -> map (map g) x = x
functorIdentityCompose fnId prId x =
  functorIdentity (map fnId) (\y => functorIdentity fnId prId y) x

看起来完整的应用程序触发了实例搜索。

VerifiedFunctor - 证明映射 (map g) x = x

VerifiedFunctor - prove map (map g) x = x

proof

functor

theorem-proving

idris