Result instead of Maybe for List.head and the like

[jvoigtlaender]

Continuing from here.

List.head currently has type List a -> Maybe a, and similarly Maybe appears in return types of other functions like Array.get.

Seeing the Maybe as signalling partiality of these functions (e.g., sometimes there is no head, so the function would fail, but instead is signalling the partiality in its return type for explicit treatment by the consumer), one wonders why not Result is used instead. (Keeping Maybe for characteristic uses of a data structure nature, rather than of a partial function nature. E.g., an optional value from a .json file would still be represented as a Maybe.)

One issue with this is performance: Does it have a bad impact on performance in typical uses of the function (maybe many of them throughout some recursion in a program) if the type of head is changed to List a -> Result T a for some type T?

Another issue is what the type T should be. Possible options:

• T = String, and List.head returns something like Err "head of empty list" in the failing case, Array.get returns something like Err "invalid index" or Err "lookup failed at index 17" on failure, etc.
• T is some dedicated union type which represents different failure causes. It could also be several different union types, e.g., one for errors possible on lists, one for errors possible on arrays, etc. Something like the various union types in this GHC base module.
• T = (), and the consumer becomes responsible for filling in specific "error messages" if desired. As in Result.map2 f (...) (Result.formatError (always "head of empty list") (List.head l)).
• T is chosen differently depending on what kind of additional information can meaningfully be provided in case of failure of specific functions. For example, for List.head the type T would indeed be () like in the previous point, but for Array.get the type T would be Int in order to easily give access to the index which led to the failure. One could then, analogously to above, write Result.map2 f (...) (Result.formatError (always "something went wrong with getting") (Array.get some-expression a)), but would also have the option of writing something like Result.map2 f (...) (Result.formatError (\i -> "lookup at index " ++ toString i ++ " failed") (Array.get some-expression a)).

[rgrempel]

One consideration which I think is significant here is internationalization. Not that the error type should do it, but that the error type should make it easy to do. This, I think, argues against making the error type a String (e.g. "head of empty list"), because that is awkward to match for translation purposes.

That is, it is brittle and inefficient to match the English string to translate to another language -- it would be better if the error were something like:

type ListError
    = HeadOfEmptyList
    | ... other errors

... and then one could pattern-match efficiently to translate for the GUI.

In fact, even the 'base case' of an English-only app is far better off with an actual error type than a String. Consider index-out-of-bounds for Array.get. If the error is a String, then you either have to just display that string in the GUI, or parse it to display something that fits your context better. Whereas, if it is something like this:

type ArrayError
    = IndexOutOfBounds Int Int
    | ... other errors

... then even in the English-only case you can construct whatever phrase for your GUI is most meaningful. (Note that the two Ints in this example would represent the requested offset and the maximum offset).

I suppose that, for convenience, one could add a function like this:

arrayErrorString : ArrayError -> String

... in order to provide a kind of default string representation.

[rtfeldman]

+1 for T being contextual based on the function.

I wasn't really conceptually in favor of this until I read the idea of "List gets () but Array gets Int" - which seems like a nice improvement over the status quo.

Not sure how much the perf difference will matter in practice; I'd assume this wouldn't affect pattern matching, which will presumably be responsible for most list-splitting operations in practice anyway?

[evancz]

Alright, added this to #322. The pattern is to close the issue so it does not count towards our "open bugs" and then continue any discussion or exploration of this here.

Not sure how much the perf difference will matter in practice

Next step is to measure it then. Pattern matching is the same, but you are now allocating strings (or something) for every Nothing that can happen. Add to that that we are already allocating an extra block for every Maybe in the first place. Maybe it is fine, but I'd like to have some data on this. The danger here is memory use, not "performance" in the sense of "how good are my instructions?".

I know that Jane Street has had issues with this. I think this is the library that does these tricks, but I cannot find the supporting docs right now. Maybe their case is a bit different? Can someone research this more thoroughly so we know its relevance here?

[rebelwarrior]

BTW the documentation for filterMap presumes toInt will give a Maybe. I submitted a pull request to fix that so that it works on the present release, at least until this gets resolved.
fixes error on documentation for filterMap #569