Representing NonEmpty List as pair (a, List a)

Request Feedback
1

For a while, I had a feeling that using pair for representation of NonEmpty List in Elm would yield the most desirable properties. I’ve tried to explain my thought process around this in my last blogpost if you’re interested in reading the whole justification for such design.

Few days back with help from github@kubaracek, @kraklin and @Jan_Hrcek I’ve finally put together the library which does exactly that.

The main idea is ridiculously simple. Instead of defining custom type, following the example implementation from Haskell, we use simple type alias NonEmpty = (a, List a). The rest is just about implementing expected functions that work with this type alias.

At the moment the documentation of the package is primarily targeted towards folks who are already familiar with non-empty lists and focuses on trade-offs compare to more traditional implementation (the README.md part). I would like to gather some feedback about this idea and eventually do the release which would make the main README more helpful to the beginners.

Links:

I would be happy to react to any comment. That’s being said reddit is probably a better place for comments about the blog post itself.

11 Likes
2

Impressive docs and blog post. Top-quality material here! :raised_hands:

1 Like
3

One question: If nonempty list is better represented as an anonymous tuple, why not the zipper which only has one constructor, so could be a 3-tuple?

type Zipper a
    = Zipper (List a) a (List a)

Overall though, I get your argument about common types being more convenient if they are open. I used mgold/elm-nonempty-list quite extensively in some recent work, but it would not be too hard to change over to your package.

4

Good question, thanks for asking.

Quoting relevant part from post:

The library also comes with a zipper module. Unlike the NonEmpty , the Zipper type is opaque. Zipper type contains private data field users are not supposed to be able to mess with – therefore the opaque type is the right choice in this case.

More specifically in case of Zipper the list of previous values is stored in reverse order. This is to make movements of zipper O(1):

next : Zipper a -> Maybe (Zipper a)
next (Zipper p f n) =
    case n of
        [] ->
            Nothing

        h :: t ->
            Just <| Zipper (f :: p) h t

as you can see it just cons currently focus value on one hand and takes head of the other side as a new focus.

On the other hand, the cost of reversing the list is then payed in places where conversion between and from other data structure happens. for instance:

custom constructor

custom : List a -> a -> List a -> Zipper a
custom p f n =
    Zipper (List.reverse p) f n

and when converting back to non empty.

toNonEmpty : Zipper a -> NonEmpty a
toNonEmpty (Zipper p f n) =
    case List.reverse p of
        [] ->
            ( f, n )

        h :: t ->
            ( h, t ++ f :: n )

It didn’t seem like a good idea to expose constructor which is hiding this implementation detail to the users. The reason why I included the Zipper to the library was to make it clear that I’m not against usage of opaque types in general.

  1. I don’t think it would be good idea to expose implementation detail like this
  2. I didn’t feel that it’s worth doing linear append while moving the focus in zipper is worth it. Folks are expecting this operation to be constant time.

So this was sort of my reasoning. That being said I can imagine Zipper represented exactly as you describe provided the list of previous values won’t be reversed or it would be even using Array in its place. Anyway I usually don’t need to construct Zipper within some other library but I would often like to return non empty list (Like Err errors where I know the list of errors can’t be empty).

For example this was the issue in elm-street which finaly motivated me to implement the idea, that might provide some context to where might be NonEmpty defined as this useful.

EDIT:
Maybe additional clarification. Even though it might not seem like a big deal to make movement of focus more expensive, you need to consider that this function is reused in other functions. The simple example might be function for moving to the end or start of a Zipper. In app I’m working on we’re also using comonadic operations a lot (extend) which also call next for every position within the zipper. This is especially why I felt it’s important to keep these operations constant.

1 Like
5

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.