Why does Idris2 not reduce this function call within the type? - Stack Overflow

admin2025-04-17  3

I expected lemma4 to reduce so that Refl would work but when trying that I get Error: While processing right hand side of lemma4. Can't solve constraint between: [p] and expanded_shape (DimSame Scalar p).

import Data.Vect
import Data.Nat

%default total

Shape : Nat -> Type
Shape n = Vect n Nat

data Array : Type -> Shape n -> Type where
    FromElem : e -> Array e []
    FromVec : Vect n (Array e s) -> Array e (n::s) 

data Broadcastable : Shape n1 -> Shape n2 -> Type where
    Scalar : Broadcastable [] []
    Dim1Left : {s1, s2: Shape n} -> Broadcastable s1 s2 -> (r: Nat) -> Broadcastable (1::s1) (r::s2)
    DimSame : {s1, s2: Shape n} -> Broadcastable s1 s2 -> (p: Nat) -> Broadcastable (p::s1) (p::s2)
    AppendLeft: {s1, s2: Shape n} -> Broadcastable s1 s2 -> (v: Vect nv Nat) -> Broadcastable (v ++ s1) s2
    Reflect : Broadcastable s1 s2 -> Broadcastable s2 s1

prf : Broadcastable [4, 8, 9, 1] [1, 4]
prf = ?hole 

max_comm : (a, b : Nat) -> maximum a b = maximum b a
max_comm Z Z = Refl
max_comm Z (S b) = Refl
max_comm (S a) Z = Refl 
max_comm (S a) (S b) = cong S (max_comm a b)

maxSame : (a: Nat) -> maximum a a = a
maxSame Z = Refl
maxSame (S a) = cong S (maxSame a) 

maxSucc : (n: Nat) -> (maximum (S n) n) = S n
maxSucc Z = Refl
maxSucc (S n) = cong S (maxSucc n) 

succInjective : {a: Nat} -> {b: Nat} -> S a = S b -> a = b
succInjective prf = cong pred prf

maxIDK : (a: Nat) -> (b: Nat) -> maximum a b = a -> maximum (S a) b = S a
maxIDK a Z prf = Refl
maxIDK (S a) (S b) prf = cong S (maxIDK a b (succInjective prf)) 
maxIDK Z b prf = rewrite prf in Refl

max_plus_b : (a, b : Nat) -> maximum (a + b) b = a + b
max_plus_b Z b = maxSame b 
max_plus_b (S a) b = (maxIDK (a + b) b (max_plus_b a b)) 


lemma : (nv, n2 : Nat) -> plus nv (maximum n2 n2) = maximum (plus nv n2) n2
lemma nv n2 = rewrite (max_plus_b nv n2) in (rewrite (maxSame n2) in Refl) 

expanded_shape : {s1: Shape n1} -> {s2: Shape n2} -> Broadcastable s1 s2 -> Shape (maximum n1 n2)
expanded_shape Scalar = []
expanded_shape (Dim1Left b r) = r::(expanded_shape b)
expanded_shape (DimSame b p) = p::(expanded_shape b)
expanded_shape (Reflect b) = rewrite (max_comm n1 n2) in (expanded_shape b)
expanded_shape (AppendLeft {nv} b v) = rewrite sym (lemma nv n2) in (v ++ expanded_shape b)

lemma4 : (p: Nat) -> expanded_shape (DimSame Scalar p) = [p] 
lemma4 p = ?lemma4_rhs

I also tried rewriting:

expanded_shape_scalar_nil : expanded_shape Scalar = []
expanded_shape_scalar_nil = Refl

lemma4 : (p: Nat) -> expanded_shape (DimSame Scalar p) = [p]
lemma4 p =
  rewrite expanded_shape_scalar_nil in Refl

but same issue.

转载请注明原文地址:http://anycun.com/QandA/1744903293a89253.html