Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Idiomatic way of listing elements of a sum type in Idris

I have a sum type representing arithmetic operators:

data Operator = Add | Substract | Multiply | Divide

and I'm trying to write a parser for it. For that, I would need an exhaustive list of all the operators.

In Haskell I would use deriving (Enum, Bounded) like suggested in the following StackOverflow question: Getting a list of all possible data type values in Haskell

Unfortunately, there doesn't seem to be such a mechanism in Idris as suggested by Issue #19. There is some ongoing work by David Christiansen on the question so hopefully the situation will improve in the future : david-christiansen/derive-all-the-instances

Coming from Scala, I am used to listing the elements manually, so I pretty naturally came up with the following:

Operators : Vect 4 Operator
Operators = [Add, Substract, Multiply, Divide]

To make sure that Operators contains all the elements, I added the following proof:

total
opInOps : Elem op Operators
opInOps {op = Add} = Here
opInOps {op = Substract} = There Here
opInOps {op = Multiply} = There (There Here)
opInOps {op = Divide} = There (There (There Here))

so that if I add an element to Operator without adding it to Operators, the totality checker complains:

Parsers.opInOps is not total as there are missing cases

It does the job but it is a lot of boilerplate. Did I miss something? Is there a better way of doing it?

like image 842
blouerat Avatar asked Aug 16 '17 14:08

blouerat


1 Answers

There is an option of using such feature of the language as elaborator reflection to get the list of all constructors.

Here is a pretty dumb approach to solving this particular problem (I'm posting this because the documentation at the moment is very scarce):

%language ElabReflection

data Operator = Add | Subtract | Multiply | Divide

constrsOfOperator : Elab ()
constrsOfOperator = 
  do (MkDatatype _ _ _ constrs) <- lookupDatatypeExact `{Operator}
     loop $ map fst constrs

  where loop : List TTName -> Elab ()
        loop [] =
          do fill `([] : List Operator); solve
        loop (c :: cs) =
          do [x, xs] <- apply `(List.(::) : Operator -> List Operator -> List Operator) [False, False]
             solve
             focus x; fill (Var c); solve
             focus xs
             loop cs

allOperators : List Operator
allOperators = %runElab constrsOfOperator

A couple comments:

  1. It seems that to solve this problem for any inductive datatype of a similar structure one would need to work through the Elaborator Reflection: Extending Idris in Idris paper.
  2. Maybe the pruviloj library has something that might make solving this problem for a more general case easier.
like image 162
Anton Trunov Avatar answered Oct 26 '22 14:10

Anton Trunov