Attached (if I don't forget to attach it) is a partial program with
two approaches to the type 'List containing some particular element
X'. The first approach, which works fine, is the 'explicit' one with a
constructor 'here' for the distinguished element (which might as well
be omitted since you know it's there) and 'there' which is an ordinary
cons.

The second approach is implicit in the sense that it has a single
constructor which takes a plain list X along with a proof that the
element 'x' lies in it. It does this by virtue of a boolean function
'contains' which checks if an element is in a list, and the So B type
which only has inhabitants in the So true case. My attempt to do this
was based on my hazy memory of a lunchtime discussion at APPSEM 03 so
apologies if I got it wrong....

[Aside: there is something unsettling about the fact that the explicit
version can be defined without needing equality, but the implicit
version requires me to make an explicit equality function a
parameter...]

It appears to type check, anyhow.

However, I can't write even the simplest functions.  ilccons is
intended to be a cons operation, but to complete it I need some way to
provide epigram with the proof that (contains x l => contains x (cons
y l)); this is indeed an easy proof, requiring only one unwrapping of
contains. I'm not really surprised not to be able to do this.

There is something more surprising at work in itoe, though. itoe was
intended to convert explicit lists into implicit lists. At one point,
it is considering the case that the implicit list was empty. If you
put the cursor in the shed "itoe (lcc eq nil oh') []" then horace
tells you the surprising fact that "oh' : So false". Really? Who
authorised horace to apply the So constructor to false? Why can't it
see that this case is a dead-end? (it seems to me similar to the vec
zero X cases, which epigram does understand to be dead ends).

The other cases are the same problem as ilccons: how to provide proofs
to epigram that the evaluation of contains (...) will be true.

Jules

------------------------------------------------------------------------------
                                          (   n : Nat   !
data (---------!  where (------------! ;  !-------------!
     ! Nat : * )        ! zero : Nat )    ! suc n : Nat )
------------------------------------------------------------------------------
data (----------!  where true : Bool ;  false : Bool
     ! Bool : * )                                   
------------------------------------------------------------------------------
     (   X : *    !                            ( x : X ;  xs : List X !
data !------------!  where (--------------! ;  !----------------------!
     ! List X : * )        ! nil : List X )    !  cons x xs : List X  )
------------------------------------------------------------------------------
                            (  x : X        !    ( x : X                    !
                            !               !    !                          !
     (    x : X    !        !  l : List X   !    ! y : X ;  l : EListCont x !
data !-------------!  where !---------------! ;  !--------------------------!
     ! EListCont x !        ! here l :      !    ! there y l : EListCont x  )
     !  : *        )        !   EListCont x )                                
------------------------------------------------------------------------------
     ( X : * ;  x : X ;  l : EListCont x !        
let  !-----------------------------------!        
     !        eforget l : List X         )        
                                                  
     eforget l <= rec l                           
     { eforget x' <= case x'                      
       { eforget (here l) => cons x l             
         eforget (there y l) => cons y (eforget l)
       }                                          
     }                                            
------------------------------------------------------------------------------
     ( eq : X -> X -> Bool ;  x : X ;  l : List X !       
let  !--------------------------------------------!       
     !           contains eq x l : Bool           )       
                                                          
     contains eq x l <= rec l                             
     { contains eq x' x <= case x                         
       { contains eq x' nil => false                      
         contains eq x' (cons x xs) <= case (eq x x')     
         { contains eq x' (cons x xs) => true             
           contains eq x' (cons x xs) => contains eq x' xs
         }                                                
       }                                                  
     }                                                    
------------------------------------------------------------------------------
     ( B : Bool !                        
data !----------!  where (--------------!
     ! So B : * )        ! oh : So true )
------------------------------------------------------------------------------
                                ( eq : X -> X -> Bool                     !
                                !                                         !
                                ! x : X                                   !
                                !                                         !
     (      x : X      !        ! l : List X ;  oh : So (contains eq x l) !
data !-----------------!  where !-----------------------------------------!
     ! IListCont x : * )        !        lcc eq l oh : IListCont x        )
------------------------------------------------------------------------------
     ( x : X ;  y : X ;  l : IListCont x !                        
let  !-----------------------------------!                        
     !      icons y l : IListCont x      )                        
                                                                  
     icons y l <= case l                                          
     { icons y (lcc eq l oh')                                     
         [=>lcc eq (cons y l) (oh : So(contains eq x (cons y l)))]
     }                                                            
------------------------------------------------------------------------------
     ( x : X ;  il : IListCont x !                                           
let  !---------------------------!                                           
     !   itoe il : EListCont x   )                                           
                                                                             
     itoe il <= rec il                                                       
     { itoe x' <= case x'                                                    
       { itoe (lcc eq l oh') <= case l                                       
         { itoe (lcc eq nil oh') []                                          
           itoe (lcc eq (cons x xs) oh') <= case eq x' x                     
           { itoe (lcc eq (cons x xs) oh') => here xs                        
             itoe (lcc eq (cons x xs) oh') [=> there x (itoe (lcc eq xs oh))]
           }                                                                 
         }                                                                   
       }                                                                     
     }                                                                       
------------------------------------------------------------------------------
     ( eq : X -> X -> bool ;  x : X ;  l : EListCont x !
let  !-------------------------------------------------!
     !             etoi eq l : IListCont x             )
                                                        
     etoi eq l <= rec l                                 
     { etoi eq x' <= case x'                            
       { etoi eq (here l) [=>lcc eq (cons x l) oh]      
         etoi eq (there y l) []                         
       }                                                
     }                                                  
------------------------------------------------------------------------------

Reply via email to