[Agda] A problem with instance arguments and function application.

effectfully effectfully at gmail.com
Thu Apr 2 17:23:50 CEST 2015


Hello. I encountered a problem while playing with instance arguments.
I have a usual hierarchy Monad <: Applicative <: Functor. Here is the
definition of the Monad for example:


record Monad {α} (M : Set α -> Set α) : Set (suc α) where
  infixl 1 _>>=_

  field
    return : ∀ {A} -> A -> M A
    _>>=_  : ∀ {A B} -> M A -> (A -> M B) -> M B

  instance
    Monad<:Applicative : Applicative M
    Monad<:Applicative = record { pure = return ; _<*>_ = λ mf mx ->
mf >>= λ f -> mx >>= return ∘ f }
open Monad {{...}}


I wrote a polyvariadic variant of the liftA function:


record _~>_ {α β} (A : Set α) (B : Set β) : Set (α ⊔ β) where
  constructor rec
  field apply : A -> B

instance
  Id : ∀ {α} {A : Set α} -> A ~> A
  Id = rec id

  Fmap : ∀ {α γ} {A B : Set α} {C : Set γ} {F : Set α -> Set α}
       -> {{_ : F B ~> C}} {{_ : Applicative F}} -> (A -> B) ~> (F A -> C)
  Fmap {{rec r}} = (λ f x -> r (f <$> x))

  Ap : ∀ {α γ} {A B : Set α} {C : Set γ} {F : Set α -> Set α}
     -> {{_ : F B ~> C}} {{_ : Applicative F}} -> F (A -> B) ~> (F A -> C)
  Ap {{rec r}} = (λ f x -> r (f <*> x))

liftA : ∀ {α γ} {A B : Set α} {C : Set γ} {F : Set α -> Set α}
      -> {{_ : F B ~> C}} {{_ : Applicative F}} -> (A -> B) -> F A -> C
liftA = _~>_.apply Fmap


I.e. lift a function using _<$>_ and then apply _<*>_ to all arguments
recursively until the type becomes (A -> A) for some A. Agda happily
accepts these definitions:

    test-1 : List ℕ -> List ℕ
    test-1 = liftA suc

    test-2 : List ℕ -> List ℕ -> List ℕ
    test-2 = liftA _+_

But

    test-3 : List (ℕ × ℕ)
    test-3 = liftA _,_ (1 ∷ 2 ∷ 3 ∷ []) (4 ∷ 5 ∷ [])

results in unresolved metas. Which can surprisingly be fixed by
inserting _$_ like this:

    test-3 : List (ℕ × ℕ)
    test-3 = (liftA _,_ $ (1 ∷ 2 ∷ 3 ∷ [])) $ (4 ∷ 5 ∷ [])

I.e. (f x y) doesn't typecheck, while (f x $ y) typechecks. (f x) has
a functional type, and _$_ explicitly clarifies that, but it should be
clear from the fact that (f x) is applied to (y). So is it a
unification defect?

I'm using Agda 2.4.2.2. The code:
https://github.com/effectfully/random-stuff/blob/master/stuff/liftA.agda

Thanks for the attention.


More information about the Agda mailing list