[Agda] Just getting into dependent typing

Luke Palmer lrpalmer at gmail.com
Mon Feb 25 19:22:10 CET 2008


Hi Everybody,

First I'd like to say that Agda is a very cool piece of software.
After seeing some of the things it and related software like Epigram
can do, I'm convinced that given 20 years, such features might make it
into mainstream languages.  :-)

I've read a bunch of the examples, and to get my hands dirty, I tried
to write a simple if function which propogates its condition to the
cases.  But I've been unable to get it to work, and more worrying, it
seems that things are typechecking which should not.  I'm looking for
some help finding out where the gaps in my understanding of dependent
types are.  Here's a sketch of my code:

Absurd, Unit, Bool, Maybe defined as expected.

  Pred : Bool -> Set
  Pred True  = Unit
  Pred False = Absurd

  if_then_else_ : {P : Bool -> Set} -> (b : Bool) -> P True -> P False -> P b
  if True  then t else f = t
  if False then t else f = f

  {- I also tried this:
  if_then_else_ : {a : Set} -> (b : Bool) -> ({_ : Pred b} -> a) ->
({_ : Pred (not b)} -> a) -> a
  if True  then t else f = t {unit}
  if False then t else f = f {unit}
  -}

  isJust : {a : Set} -> Maybe a -> Bool
  isJust (Just _) = True
  isJust Nothing = False

  fromJust : {a : Set} -> (x : Maybe a) -> {_ : Pred (isJust x)} -> a
  fromJust (Just x) {unit} = x
  fromJust Nothing  {}

  mapMaybe : {a b : Set} -> (a -> b) -> Maybe a -> Maybe b
  mapMaybe f m = if (isJust m) then Just (f (fromJust m)) else Nothing

Obviously mapMaybe could be written better using case analysis, but
the point of the exercise was not to.

Anyway, this compiles fine, but doesn't seem to run fine.

Main> mapMaybe not (Just False)
_63 not (Just False)
Main> mapMaybe not Nothing
_63 not Nothing

I assume that _63 is a variable generated by an implicit argument.
But shouldn't it fail to compile if it was unable to deduce it?  What
is yet more distressing is the fact that this implementation of
mapMaybe compiles:

  mapMaybe' f m = Just (f (fromJust m))

Which shows me that all my if magic was doing nothing.

So two questions:  why is this "incorrect" code compiling, and how
would an experienced dependent typer implement an if construct which
communicates its condition to its branches (if possible)?

Thanks,
Luke


More information about the Agda mailing list