Proposal: pattern for dealing with empty lists

[ianmackenzie]

Background

Many functions in Elm that work with Lists work equally well with empty and non-empty lists, for example:

• List.sum returns 0 for an empty list
• List.map returns an empty list if given an empty list
• Html.div does what you’d expect if given empty lists for attributes and/or children

However, other functions only really make sense for non-empty lists, and have a couple main ways of expressing/dealing with that:

1. Return a Maybe: List.maximum has the signature List comparable -> Maybe comparable, returning Nothing for an empty list
2. Require an explicit ‘first item’ argument: Random.uniform has the signature a -> List a -> Generator a, forcing you to call it as Random.uniform x [ y, z ] instead of Random.uniform [ x, y, z ]

Either one of these could have been written the other way:

• List.maximum could have had the signature comparable -> List comparable -> comparable
• Random.uniform could have had the signature List a -> Maybe (Generator a)

Approach (1) is a bit simpler at first glance, but forces you to deal with a Maybe even if you can guarantee the list is non-empty. Approach (2) looks a bit weird, and doesn’t handle the empty list case at all, but lets you avoid the Maybe. (There’s also the third approach of using a dedicated non-empty list type like mgold/elm-nonempty-list, but I wanted to see how much could be done without requiring a separate type.)

Proposal

It occurred to me that we might be able to get the best of both worlds by adding (perhaps in the list-extra package) a function

ifNonEmpty : (a -> List a -> b) -> List a -> Maybe b
ifNonEmpty function list =
    case list of
        first :: rest ->
            Just (function first rest)

        [] ->
            Nothing

and then following a convention of using approach (2) instead of (1) anywhere that we write a function that requires a non-empty list. We could then write code like

import List.Extra as List

List.maximum 2 [ 1, 3 ]
--> 3

-- Read as "if the list is non-empty, returns its maximum"
List.ifNonEmpty List.maximum [ 2, 1, 3 ]
--> Just 3

List.ifNonEmpty List.maximum []
--> Nothing

[ 2, 1, 3 ]
    |> List.filter (\n -> n < 3)
    |> List.ifNonEmpty List.maximum
--> Just 2

[ 2, 1, 3 ]
    |> List.filter (\n -> n > 3)
    |> List.ifNonEmpty List.maximum
    |> Maybe.withDefault -1
--> -1

which to me seems like a pretty nice way to handle both possibly-empty and guaranteed-non-empty lists of values.

Thoughts?

What do you think? Are there places where this breaks down or becomes awkward? If people like the idea, then I’d be happy to make a PR to list-extra, and start updating my own packages to use form (2). (This whole train of thought was kicked off when trying to come up with a nice solution to this elm-geometry issue).

[ianmackenzie]

And just to be clear: I’m not actually proposing any immediate changes to Elm’s core libraries. I think this is something that we could experiment with and perhaps gradually adopt as a community, and if the experiment is successful then maybe a future version of Elm could update functions like List.maximum to use the new pattern. (I only used that function as an example since I think most people are familiar with what it does!)

[francescortiz]

Cool. I totally agree with what you say. Just a simple detail: I believe that in order to be grammatically correct the name of the function should either be ifNonempty or ifNotEmpty. And, to avoid confusion with the elm-nonempty-list package, I would go for ifNotEmpty. Thanks for the post

[Sebastian]

I wouldn’t like a function like List.maximum 2 [ 1, 3 ]. Where do I get that 2 from if you are dealing with data coming from an external source?

If you have a default value, why not?:

List.maximum [1,3] |> Maybe.withDefault 2

[ianmackenzie]

Using Maybe.withDefault in concert with the current List.maximum doesn’t work, since

List.maximum [ 1, 2 ] |> Maybe.withDefault 3

will give you 2, not 3 as expected. If you’re dealing with data coming from an external source (or any other list that may be empty), then (with this proposed approach) you would write something like

listOfInts |> List.ifNotEmpty List.maximum

to give you a Maybe Int, just like List.maximum works now. Basically, this proposal would mean that the current

List.maximum listOfInts

would have to be replaced by

List.ifNotEmpty List.maximum listOfInts

if you wanted the result as a Maybe Int, but with the advantage that you could also just write

List.maximum first rest

to get a plain Int if you happened to have an initial value (perhaps because you’ve already done some pattern-matching on a list, or you’re constructing a list in a way that you have a known first value, etc.)

[ianmackenzie]

@francescortiz I think I agree, List.ifNotEmpty is probably better =)

[Sebastian]

Could the same result be achieved by having a function like this?

usingDefault op default list =
   case op (default::list) of
      Just v ->
         v
      Nothing ->
         default

max = 
    usingDefault List.maximum 3 [1, 2]

Then you wouldn’t need to change existing functions

[francescortiz]

@Sebastian you are correct, but I think the goal is to propose a common pattern for non-empty lists. You can always hack and hack the hack, but having common patterns helps the Elm ecosystem stay simpler and clearer. As I see it, between the two options, @ianmackenzie proposed one is potentially more performant and allows for simpler implementations on complex situations, because you might have matched the list, but there is no way to avoid the need of matching a Maybe returned by a function. With the proposed approach, one match of the list allows to do all the operations you want without having to handle any Maybe.

[Sebastian]

I disagree that this is better, I think the function signature depends on what makes sense on each case. For me it makes sense that List.maximum returns a Maybe. Making something like List.maximum more awkward to use in the name of consistency, isn’t my idea of simpler and cleaner.

[Chadtech]

I have some feedback.

Background

Over in List.Extra we’ve had a few conversations about non-empty lists. What really brought our non-empty thoughts to a headway, was the observation from a few different people that groupWhile doesnt really make sense with a List a type since the lists themselves cant be empty (discussions: 0 , 1). We ended up changing groupWhile to use a non-empty list, and we decided to use a (a, List a) type to represent non-empty lists (instead of a new NonEmpty type, which would be opaque). We have a discussion thread (here) for future non-empty stuff, but we havent really acted on any of this, because for the most part we dont make changes until they become a problem or some outside contributor brings it up. One of my suggestions in those discussions was for these functions:

toNonEmpty : List a -> Maybe (a, List a)
fromNonEmpty : (a, List a) -> List a

which are really similar in spirit and name to your ifNonEmpty

Suggesiton: bundle non-empty list as a singular type (a, List a)

ifNonEmpty : ((a, List a) -> b) -> List a -> Maybe b

I really like the distinction between lists and non-empty lists, and so I also like the signature maximum : a -> List a -> a to the extent that it recognizes this distinction. But it does seem like most of us are thinking of non-empty lists as a distinct thing, and in practice Ive only ever seen the case where you have the first element and remaining elements moving along through your code together as a single group.

The classic non-empty type I am familiar with is its own type:

type NonEmptyList a = 
    NonEmptyList a (List a)

So, for those reasons, I think it would be more fitting for a non-empty list functions to operate on a (a, List a) than two separate arguments a -> List a ->.

[joelq]

I think it’s useful to think about the use-cases of various APIs. For the strategies you mention, the use cases seem to be:

1. a -> List a -> b is preferred with working with hardcoded list literals
2. List a -> Maybe b is preferred when dealing with unknown lists (e.g. API responses, user input)

This brings up a question:

Are there any functions that have an API designed for one use-case but whose actual usage is the other?

The old Random.Extra.sample is an example of this. It would return a Maybe even though I only ever used it with a hardcoded literal, forcing me to append Random.map (Maybe.withDefault default) to all those generators. By switching to API strategy #1, the new Random.uniform was a big quality of life improvement.

Perhaps there are other other functions that could be switched from strategy #1 to #2 (or vice versa) to better match their use-case?

This leads me to another question:

Are there any functions that are commonly used with both hard-coded literals and with unknown lists?

You probably never want to call List.maximum on a hard-coded literal because you already know the max and could just hard-code that instead. You might want to pick a random element out of a list of user inputs, but I’m guessing that is rare enough that having to manually handle the empty list is a one-off.

Functions that fall into this category are where your proposal would shine, because it allows them to play nicely with both use-cases.

I feel like gathering some stats would be really helpful for this discussion.

---

There’s another use-case that I haven’t talked about but you alluded to it as a possible strategy #3 - a non-empty list type. This is used for lists that have been pre-validated to match some business rules that require non-emptiness. The contents of these lists is still unknown though.

It is both reasonable to want to calculate the maximum of such a list and also to want it not to be a Maybe. The existence of this use-case points in favor of your proposal since there are now a class of functions we would like return a Maybe for unvalidated lists but not for validated lists.

---

[Erudition]

@joelq

There’s another use-case that I haven’t talked about but you alluded to it as a possible strategy #3 - a non-empty list type.

Hmm, did you read OP’s post? There already is a Nonempty type! And, it’s very common. I use that package in all of my projects.

[Erudition]

@Sebastian

Making something like List.maximum more awkward to use

max = List.maximum 1 [2, 3, 4, 5]
…is not more awkward than
max = Maybe.withDefault someDummyValue ( List.maximum [1, 2, 3, 4, 5] )

…but of course the point about hardcoded values applies.

[Erudition]

IMHO mgold’s Nonempty is the way to go, and should probably become core. People would just know whether they want a normal list or a non-empty list based on the name, and then choose the type they need, without any extra parameter massaging (even though evan recommends the func first [rest] paradigm in the docs).

I agree that it would be nice to have that type not be opaque, though, so I can casually switch to (Single, [List]) tuples and back whenever I want - especially since Nonempty doesn’t get List's syntax sugar.

[HappMacDonald]

Yeah, I’m really struggling to see the advantage of Nonempty being an ADT, like:

type NonEmptyList a =
NonEmptyList a (List a)

vs a simpler type alias, like:

type alias NonEmptyList a =
(a, (List a))

IIUC this latter has every concrete benefit that the former might offer us.