[Agda] --without-K option too restrictive?

Andreas Abel andreas.abel at ifi.lmu.de
Wed May 29 22:52:46 CEST 2013


The error comes from universe polymorphism: Agda complains about 
Level.zero not being pattern, although Level.zero is only visible in the 
debug printing -v tc.lhs.split.well-formed:20.

I don't think that levels should keep one from matching on refl here. 
--without-K seems overly strict here.

If I remove universe polymorphism by hand (see attached file), I see a 
different error:

The variables
   A
which are used (perhaps as constructor parameters) in the index
expressions
   x ∷ xs
are free in the parameters
   {List A}
   ys
when checking that the pattern refl has type
_≡_ {List A} ys (x ∷ xs)

This one is more comprehensible.  However, still --without-K is too 
restrictive.

Have not we discussed this before?  I am having a dejavu here, but 
cannot find traces of this discussion in my email archive.

Cheers,
Andreas

On 29.05.13 10:23 PM, Andreas Abel wrote:
> The error message is confusing:
>
> The indices
>    x ∷ xs
> are not constructors (or literals) applied to variables (note that
> parameters count as constructor arguments)
>
> First, it uses plural for a single index (I am changing this right now).
>   Further, it is not a true statement, because x :: xs  _is_ a
> constructor applied to variables.  Whatever it wants to tell me, I do
> not get it.
>
> On 29.05.13 8:59 PM, Nils Anders Danielsson wrote:
>> On 2013-05-29 17:26, Andrés Sicard-Ramírez wrote:
>>> Why the --without-K option rejects the following proof
>>>
>>> foo : {A : Set}(xs ys : List A) → P xs ys → Q xs ys
>>> foo xs .(x ∷ xs) (x , refl) = helper x xs
>>>
>>> if I can prove foo using only subst
>>>
>>> foo' : {A : Set}(xs ys : List A) → P xs ys → Q xs ys
>>> foo' xs ys (x , h) =
>>>    subst (λ ys' → length xs < length ys') (sym h) (helper x xs)
>>>
>>> ?
>>
>> The --without-K flag is documented in the release notes of Agda 2.3.2:
>>
>>
>> http://wiki.portal.chalmers.se/agda/uploads/Main.Download/release-notes-2-3-2.txt
>>
>>
>>
>

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/
-------------- next part --------------
{-# OPTIONS --without-K --show-implicit #-}
{-# OPTIONS -v tc.lhs.split.well-formed:100 #-}
-- Andres Sicard, 2013-05-29
module WithoutKRestrictiveNoUniPoly where

data ℕ : Set where
  zero : ℕ
  suc  : ℕ → ℕ

data _≤_ : ℕ → ℕ → Set where
  z≤n : ∀ {n} → zero ≤ n
  s≤s : ∀ {n m} → n ≤ m → suc n ≤ suc m

_<_ : ℕ → ℕ → Set
n < m = suc n ≤ m

refl≤ : ∀ (n : ℕ) → n ≤ n
refl≤ zero    = z≤n
refl≤ (suc n) = s≤s (refl≤ n)

data List (A : Set) : Set where
  []  : List A
  _∷_ : (x : A) (xs : List A) → List A

length : {A : Set} → List A → ℕ
length []       = zero
length (x ∷ xs) = suc (length xs)

record Σ (A : Set) (B : A → Set) : Set where
  constructor _,_
  field
    proj₁ : A
    proj₂ : B proj₁

data _≡_ {A : Set}(a : A) : A → Set where
  refl : a ≡ a

subst : {A : Set}(P : A → Set){a b : A} → a ≡ b → P a → P b
subst P refl x = x

sym : {A : Set}{a b : A} → a ≡ b → b ≡ a
sym refl = refl

P : {A : Set} → List A → List A → Set
P xs ys = Σ _ (λ x → ys ≡ (x ∷ xs))

Q : {A : Set} → List A → List A → Set
Q xs ys = (length xs) < (length ys)

helper : {A : Set}(y : A)(xs : List A) → (length xs) < (length (y ∷ xs))
helper y []       = s≤s z≤n
helper y (x ∷ xs) = s≤s (refl≤ _)

-- Why the --without-K option rejects the following proof

foo : {A : Set}(xs ys : List A) → P xs ys → Q xs ys
foo xs .(x ∷ xs) (x , refl) = helper x xs

-- if I can prove foo using only subst

foo' : {A : Set}(xs ys : List A) → P xs ys → Q xs ys
foo' xs ys (x , h) =
  subst (λ ys' → length xs < length ys') (sym h) (helper x xs)


More information about the Agda mailing list