`enumerate` function for non-infinite custom types - proposal

[Janiczek]

tl;dr

I propose the compiler would expose a “magical” function enumerate : Type a -> List a (for lack of better syntax) that would enumerate non-infinite types into a list:

type MyType
    = Foo
    | Bar Baz

type Baz
    = A
    | B
    | C

enumerate Baz
--> [A, B, C]

enumerate MyType
--> [Foo, Bar A, Bar B, Bar C]

---

Motivation

I’m regularly encountering situations where I have a custom type for which I need all its values to be processed (shown, aggregated, …). For example this thread.

Currently there is no way to enumerate such types, so I need to create the list manually. The danger of that is that when I extend the custom type, I forget to add a value to that manually created list.

With the enumerate function I’d be able to do this and be absolutely sure that I can’t forget about adding a new value anywhere:

parser : Parser (Route -> a) a
parser =
    enumerate Route
        |> List.map routeToParser
        |> Url.Parser.oneOf


routeToParser : Route -> Parser (Route -> a) a
routeToParser route =
    case route of
        NotFound -> notFound
        Home -> home

---

Ways to create the list semi-safely

a) introduce a redundant definition that uses case ... of to warn me that I need to add a new value

parser : Parser (Route -> a) a
parser =
    Url.Parser.oneOf
        [ notFound
        , home
        ]


{-| This is only here to make sure I don't forget to add the new route's parser.
-}
parserFailsafe : Route -> String
parserFailsafe route =
    case route of
        NotFound ->
            "yes I have added the new parser to `parser` above"

        Home ->
            "yes I have added the new parser to `parser` above"

b) create the list of values myself with a case ... of and slightly convoluted logic

nextType : Route -> Maybe Route
nextType : route = 
  case route of 
    NotFound -> Just Home
    Home -> Nothing


makeAllRoutes : Maybe Route -> List Route
makeAllRoutes mbroute = 
  case mbroute of
    Nothing -> []
    Just route -> route :: makeAllRoutes (nextType route)


allRoutes : List Routes
allRoutes = makeAllRoutes NotFound

I’ve come to realize this one doesn’t have any benefit over the first option and is slightly more complicated.

---

Concerns

Q: what about (effectively) infinite types, ie. Maybe Int or this ?

type MyType
    = Foo
    | Bar Int

A: The compiler would simply not allow using enumerate on that type. Would throw eg. a compiler error about infinite lists.

Q: What about parameterized types? eg. Maybe a
A: The only allowed usages would be with concrete types:

• enumerate (Maybe Bool) would be OK
• enumerate Maybe wouldn’t
• enumerate (Maybe a) wouldn’t

Q: There is no support in the compiler for such reflection! (a Type -> Value function)
A: Yeah, this would probably be the first such thing. But everything this function would need seems to be already in place / at least theoretically knowable.

• Is the type infinite? We can check that using set membership: is any of the “participating” types Int, Float, String, Char? (maybe I missed some?)
• Is the result of the enumerate call actually used anywhere? Dead code elimination tells us that.
• If the type is not infinite and the result is actually used, the compiler can generate a JS value with the actual list, potentially inline, potentially reusing it in multiple places.

---

Pros

• Type safety for when you need to enumerate all values of a custom type (this is fairly common). This would eliminate the need to make the list yourself and possibly forget to add a value when you expand the custom type.

---

Cons

• Slightly magical/non-explicit language feature
• Possibly hard to implement? I don’t really know.
• Doesn’t work on all types, but - well, there’s no way it possibly could in a strict language. But this limits the usefulness of the function and the number of usecases where this can be used.

[dillonkearns]

We generate these automatically for GraphQL Enums in dillonkearns/elm-graphql: https://github.com/dillonkearns/elm-graphql/blob/master/examples/src/Swapi/Enum/Episode.elm#L17-L25

It’s really handy. But in the case of GraphQL enums, there are never any parameters so that simplifies it.

[klazuka]

In a similar way, I’d like to be able to enumerate just the “tag” portion of a custom type variant.

There are several places in my app where I define an entity that has different variants. e.g.

type Classifier
    = Regex { ... }
    | Drill { ... }
    | Javascript String
    | JsonPath String

Now let’s suppose that I want to show a dropdown where you can create a classifier by selecting one of these variants. I could have the dropdown’s backing list be a list of strings to be displayed to the user. In which case I have the same problem that @Janiczek described: I must remember to add to the list whenever a new variant is added to the Classifier type. And when the user actually makes a selection, I must pattern match on the string to figure out which variant to create.

I run into similar problems with URL structure and routing. Let’s suppose that I want to have a URL which takes you to an editor page configured to create one of these variants. For example, #/classifiers/new/regex would create a new “regex” classifier. Again, I need to pattern match on a string to construct the appropriate variant.

After having run into this problem several times, I’ve started creating a separate custom type which matches the original type but discards the runtime data associated with each variant. So for the Classifier type described above, I would also create a type like so:

type ClassifierTag
    = RegexTag
    | DrillTag
    | JavascriptTag
    | JsonPathTag

and I would also define a value which enumerates all of the possible tags:

allTags = [ RegexTag, DrillTag, JavascriptTag, JsonPathTag, RemoteTag ]

and define a mapping to/from strings:

tagToString : ClassifierTag -> String
stringToTag : String -> Maybe ClassifierTag

---

It would be nice if there was a way to annotate a custom type in such a way that the Elm compiler could synthesize the “tag” type and functions defined above. And in the cases that @Janiczek described, you could also synthesize a function that enumerates all variants of the main type, not just the tags.

[albertdahlin]

What about this idea: Introduce the enum keyword?

This would create a normal custom type but be restricted to finite types as well as creating the enumerate list generator.

enum MyType
    = Foo
    | Bar Baz

enum Baz
    = A
    | B
    | C

Thoughts

I think the intent of the type is communicated in a clearer way which is very helpful when you are a team working on the same project.
Sometimes the type declaration lives in one module but used all across the code base.

This could also be used as a pseudo-typeclass, similar to how comparable or number works today. However I can not really come up with a problem where that would be useful.

It might be harder to understand for beginners. We already have type alias and type which can be confusing at first.
But then on the other hand, you still need to understand the concept of infinite vs finite types anyway if you want to use enumerate.

[pit]

Hi @Janiczek, if you slightly change the signature of the next... functions in your example b) to Maybe a -> Maybe a, it’s possible to write a generic enumerate function:

type Baz
    = A
    | B
    | C

bazIterator : Maybe Baz -> Maybe Baz
bazIterator b =
    case b of
        Just A  -> Nothing
        Just B  -> Just A
        Just C  -> Just B
        Nothing -> Just C

enumerate : (Maybe a -> Maybe a) -> List a
enumerate iterator =
    let
        addNextValue : List a -> List a
        addNextValue list =
            case list |> List.head |> iterator of
                Just nextValue ->
                    nextValue :: list |> addNextValue

                Nothing ->
                    list
    in
    addNextValue []

enumerate bazIterator
--> [A, B, C]

In this Ellie I added an example for something like your nested type MyType, but I doubt that this would scale to more complex types.

For @klazuka: with an iterator function signature of Maybe a -> Maybe ( a, String ) it should be possible to write an extended version of enumerate which generates the list together with the two conversion functions:

extendedEnumerate : (Maybe a -> Maybe ( a, String )) -> ( List a, a -> String, String -> Maybe a )
extendedEnumerate iterator =
    ...

[opvasger]

Ive tried to simplify a bit - let me know what you think

-- Order!

type alias Order a =
    a -> Maybe a

enumerateFrom : a -> Order a -> List a
enumerateFrom previous toNext =
    case toNext previous of
        Just next ->
            next :: enumerateFrom toNext next

        Nothing ->
            []

-- Colors!

type Color
    = Blue
    | Green
    | Red
    | Yellow

alphabeticalOrder : Order Color
alphabeticalOrder color =
    case color of
        Blue ->
            Just Green

        Green ->
            Just Red

        Red ->
            Just Yellow

        Yellow ->
            Nothing

colors : List Color
colors =
    enumerateFrom Blue alphabeticalOrder

[ianmackenzie]

I think I like the idea of an enum keyword, and in that case you might not even need a special enumerate function…in the same way that

type alias Person =
    { firstName : String
    , lastName : String
    }

introduces both a Person type alias and an associated Person function of type String -> String -> Person,

enum Currency
    = Usd
    | Eur
    | Cad
    | Jpy

could introduce both a Currency type and an associated Currency value equal to

[ Usd, Eur, Cad, Jpy ]

so that you could write

List.map currencyString Currency

If you want to get a bit more clever, the Currency value could alternatively be equal to

{ values = [ Usd, Eur, Cad, Jpy ] }

so that you could write the slightly more natural-reading

List.map currencyString Currency.values

In fact maybe you don’t even need a separate enum keyword…maybe any type CustomType definition where every constructor is a plain value results in a corresponding CustomType value of type { values : List CustomType }.

Caveat: either of these approaches would mean that you couldn’t have an enum of the form

type Something
    = Something
    | SomethingElse
    | AnotherThing

since then Something already exists as a value as well as a type. That seems kind of OK though - if there’s one ‘special’ or ‘default’ entry like that, then it seems less likely that it would make sense to map over all values in a way that treats them equally.