Proposal for new API

[stoeffel]

Proposal for new API

We've now used List.Zipper in many places of our application (87 modules depend on it).
I've created a draft of an API that solves all our use cases, while hiding the implementation, reducing the api surface and hopefully making finding elements easier. This issue is meant as a starting point for a discussion about the api, I really like this package and the data-structure has proofen to be super useful. Thanks for all your work on this @wernerdegroot!

Type

type Zipper a as an opaque type. (I totally agree with #10)

Constructing

    singleton : a -> Zipper a
    append : List a -> Zipper a -> Zipper a
    prepend : List a -> Zipper a -> Zipper a

This allows for simpler construction of a zipper. No Maybe!
In all our use-cases we want a zipper and we know that we have elements.
We added two different wrappers around toList and withDefault in our codebase to make this easier. I'm happy to keep toList though if you think it's useful.
This might also address #15

    singleton 0
        |> append [1,2,3]

Accessors

    before : Zipper a -> List a
    current : Zipper a -> a
    after : Zipper a -> List a
    toList : Zipper a -> List a

Same as before.

Mapping

    map : (a -> b) -> Zipper a -> Zipper b
    -- we have a use-case where we use `http://package.elm-lang.org/packages/elm-community/list-extra/6.1.0/List-Extra#findIndex` to get the index, but it would be nicer to just use `indexedMap`.
    indexedMap : (Int -> a -> b) -> Zipper a -> Zipper b
    -- The nice thing about this api is that you can map everything from `a -> b` and still have different functions for the different parts.
    type alias Format a b =
      { before : List a -> List b
      , current : a -> b
      , after : List a -> List b
      }
    format : Format a b -> Zipper a -> Zipper b

Formatting everything at once.
We could provide a defaultFormatter with everything set to identity so a user can update that record with the one they wanna change.
SelectList has mapBy, but I kinda like format better. http://package.elm-lang.org/packages/rtfeldman/selectlist/1.0.0/SelectList#mapBy

Moving around

    previous : Zipper a -> Maybe (Zipper a)
    next : Zipper a -> Maybe (Zipper a)
    first : Zipper a -> Zipper a
    last : Zipper a -> Zipper a
    -- find is used as a movement (we don't return the found element, like one would expect from find)
    -- we only use `find << first` in our codebase (in ~50 places)
    -- but I think it's better to be explicit and call `first` first.
    nextUntil : (a → Bool) → Zipper a → Maybe (Zipper a)
    previousUntil : (a → Bool) → Zipper a → Maybe (Zipper a)

New sub module: List.Zipper.Circular there is http://package.elm-lang.org/packages/maorleger/elm-infinite-zipper/2.1.0/List-InfiniteZipper, but it would be super useful (I've got one newer use-case) to have the same type for this.

    -- moving wraps around edges
    previous : Zipper a -> Zipper a
    next : Zipper a -> Zipper a
    nextUntil : (a → Bool) → Zipper a → Maybe (Zipper a) -- we still need a maybe here, if we don't find an element
    previousUntil : (a → Bool) → Zipper a → Maybe (Zipper a)

moveUntil replaces all find functions.

I hope you don't mind this proposal and I'm looking forward to discussing this.

[stoeffel]

Might be nice to have a selectAt : Int -> Zipper a -> Maybe (Zipper a) as well. HT @terezka

[wernerdegroot]

Nice to hear you are happy with the library! I'm always open to suggestions that make the library better.

Let's discuss these, one at a time.

Constructing

Great suggestions! I like append and prepend, and I can imagine that these make a lot of cases involving Maybe easier.

I've been struggling with all the Maybes myself quite a lot. Let me share some thoughts I have that might be more versatile than adding convenience functions like append and prepend. I am curious what you think of these ideas.

Conceptually I see a difference between a Zipper pointing at an element, and a Zipper pointing between elements.

• The former allows to you to get the element without using a Maybe. Constructing a Zipper requires a non-empty list, though.

  In short, it is the Zipper this library currently provides.

• The latter can always be constructed, even from an empty list. When constructing from a non-empty list, the Zipper will point before the first element.

  A Zipper pointing between elements is also quite natural when inserting elements.

I would like to have both. I would also like to switch between those two naturally.

Is this something that appeals to you? (If we can maintain an easy to use API, of course.) Or do you prefer the convenience methods?

[wernerdegroot]

This might also address #15

I see I have neglected an issue! Let's tackle that one after this one.

[stoeffel]

Conceptually I see a difference between a Zipper pointing at an element, and a Zipper pointing between elements.

I saw that difference as well. I think in most of our use-cases this would be solve with the functions I proposed in Moving around (nextUntil, selectAt).

The latter can always be constructed, even from an empty list. When constructing from a non-empty list, the Zipper will point before the first element.

I think I wouldn't like having this in the Zipper lib. I think it should only work with non-empty lists and I think the most expressive way to construct a Zipper is with singleton and append.

We use list-selection at NRI in some cases where we don't always have a selected item.
http://package.elm-lang.org/packages/NoRedInk/list-selection/latest

[jwoudenberg]

Just wanted to quickly chime in that I like this proposal a lot. In particular I like the separate module with the circular functions, allowing you to use the same datastructure in a different way.

Conceptually I see a difference between a Zipper pointing at an element, and a Zipper pointing between elements.

This is a cool concept! I wonder if it needs to be the same data structure though. Keeping both structures separate might keep both their implementations simpler.

[wernerdegroot]

I saw that difference as well. I think in most of our use-cases this would be solve with the functions I proposed in Moving around (nextUntil, selectAt).

This is a cool concept! I wonder if it needs to be the same data structure though. Keeping both structures separate might keep both their implementations simpler.

This will definitely be a different data structure! I'll try to implement this in a separate pull request and 1) see if I can easily maintain the current API 2) see if you guys like it above what we currently have.

Great suggestions! I like append and prepend, and I can imagine that these make a lot of cases involving Maybe easier.

I have thought about it some more and am a little worried people might interpret append and prepend to mean "append or prepend relative to the current element", like the proposal for insertAfter and insertBefore (#15). What do you guys think?

The functions insertAfter and insertBefore are arguably more powerful, as they allow the proposal for append and prepend to be implemented as:

append elems = last >> insertAfter elems
prepend elems = first >> insertBefore elems

[stoeffel]

This will definitely be a different data structure! I'll try to implement this in a separate pull request and 1) see if I can easily maintain the current API 2) see if you guys like it above what we currently have.

SGTM!

The functions insertAfter and insertBefore are arguably more powerful, as they allow the proposal for append and prepend to be implemented as:

append elems = last >> insertAfter elems

That would change the focus in the Zipper though. The new Zipper would point to the last element.

append or prepend relative to the current element

I'm not super worried about people not understanding append and prepend, because it's the same as for List. Maybe appendList/prependList would be better though.

I'm more worried that people don't understand insertAfter that's not clear to me where this inserts.

[wernerdegroot]

That would change the focus in the Zipper though. The new Zipper would point to the last element.

I'm not super worried about people not understanding append and prepend, because it's the same as for List. Maybe appendList/prependList would be better though.

To me, a Zipper is all about the element with the focus. It's its unique selling point as it were.

In my experience, but admittedly my experience is limited to hobby projects, all List-operations are better achieved by transforming the Zipper to a List (en then possibly back again) instead of duplicating the List-interface for Zipper. I am curious what your experience with Zippers is. Do you often feel you need to access the "undelying" List often?

If the primary use case for append is constructing with the pattern singleton 1 |> append [2, 3, 4] I think we would be better served with a constructor fromCons : a -> List a -> Zipper a.

P.S. I hope I don't come across as unwilling to implement your proposal, as it is very welcome. I just want to make sure we keep the library lean and focussed.

[stoeffel]

I hope I don't come across as unwilling to implement your proposal, as it is very welcome. I just want to make sure we keep the library lean and focussed.

Not at all! I was hoping to start a discussion with this and didn't expect you to just blindly go with it. Sorry was pretty busy the last week. Will take some time next week and reply and add some more thoughts. We don't have to hurry with this :-).

[stoeffel]

To me, a Zipper is all about the element with the focus. It's its unique selling point as it were.

Agreed and also but less the nonempty-properties that come with it.

In my experience, but admittedly my experience is limited to hobby projects, all List-operations are better achieved by transforming the Zipper to a List (en then possibly back again) instead of duplicating the List-interface for Zipper. I am curious what your experience with Zippers is. Do you often feel you need to access the "undelying" List often?

Totally agree.

If the primary use case for append is constructing with the pattern singleton 1 |> append [2, 3, 4] I think we would be better served with a constructor fromCons : a -> List a -> Zipper a.

You might be right on this. I'm happy with fromCons. Additionally, it's always the case that you want the first element to have the focus, and if not you can use nextUntil : (a → Bool) → Zipper a → Maybe (Zipper a) (from the proposal) to change the selection using a predicate.

[wernerdegroot]

You might be right on this. I'm happy with fromCons. Additionally, it's always the case that you want the first element to have the focus, and if not you can use nextUntil : (a → Bool) → Zipper a → Maybe (Zipper a) (from the proposal) to change the selection using a predicate.

Awesome! Let's start with fromCons then.

[wernerdegroot]

Mapping

    map : (a -> b) -> Zipper a -> Zipper b
    -- we have a use-case where we use `http://package.elm-lang.org/packages/elm-community/list-extra/6.1.0/List-Extra#findIndex` to get the index, but it would be nicer to just use `indexedMap`.
    indexedMap : (Int -> a -> b) -> Zipper a -> Zipper b
    -- The nice thing about this api is that you can map everything from `a -> b` and still have different functions for the different parts.
    type alias Format a b =
      { before : List a -> List b
      , current : a -> b
      , after : List a -> List b
      }
    format : Format a b -> Zipper a -> Zipper b

Formatting everything at once.
We could provide a defaultFormatter with everything set to identity so a user can update that record with the one they wanna change.
SelectList has mapBy, but I kinda like format better. http://package.elm-lang.org/packages/rtfeldman/selectlist/1.0.0/SelectList#mapBy

What made you decide on the name Format (as that seems quite an overloaded name)?

[stoeffel]

What made you decide on the name Format (as that seems quite an overloaded name)?

We used this name for similar function in a different datastrucutre, but I don't have a strong opinion on the name maybe mapWith would be okay as well. But we just had an other use-case for this, which I don't exactly recall, but @jwoudenberg might be able to explain. I think this is really useful because it allows you to map everything to a different type.

I think the usecase was something like:

zipper
|> mapWith { before = (,) LT, current = (,) EQ, after = (,) GT }

[stoeffel]

different thought I had:

What if we would change next/previous to be more explicit in when it reaches the end of the zipper, instead of encoding that info in a Maybe?

next : Zipper a -> (Position, Zipper)
-- where Position is
type Positing = Already Position | Start | Inside | End

or maybe a better solution would be to do:

next : Zipper a -> Zipper a
-- and have a function that you could use before moving like 
position : Zipper a -> Position
-- where Position is
type Position = Start | Between | End
-- so a user can choose to ignore the position and just call next regardless
-- or call `position` before moving.

[wernerdegroot]

We could even make it generic in what the result of next/previous is:

type Movement = Previous | Next
type alias Mover a r = Movement -> Zipper a r -> r
type Zipper a z = Zipper (List a) a (List a) (Mover a z)

next : Zipper a z -> z
next ((Zipper _ _ _ m) as z) = m Next z

That way, a next that results in a Zipper a, a next that results in a Maybe (Zipper a) and a next that results in a (Position, Zipper a) could all co-exist. And users of this library could even add their own different behaviour.

We might be burdening the users of the library a lot with this decision though.

[wernerdegroot]

And users of this library could even add their own different behaviour.

I even think we can implement a circular Zipper this way, so that would also be a plus.

[wernerdegroot]

I've been playing with the idea of a Mover. I have two choices:

1. make it part of the Zipper, so that you get a Zipper a m (like my example above). The type signature of some functions gets a little harder, but the way you use those functions doesn't.
2. make it something external that you have to pass manually to each function. This resembles a typeclass somewhat. The downside is that you have the pass it along manually each time, the upside is that you make the choice how you want to move around as late as possible.

Any input?

[jwoudenberg]

And users of this library could even add their own different behaviour.

I've built custom behavior on top of the current Zipper on a number of occasions and found it pretty easy to do so. If the intent of abstracting out a Mover is to make it easier to define custom behavior for the Zipper I don't see many benefits over the current situation, whereas complicating the type signature seems to me a big disadvantage.

With regards to the circular movement. Given a choice between this API:

-- Move to the previous element
List.Zipper.previous zipper
-- Move to the previous element, wrapping around to the last element if none exists
List.Zipper.Circular.previous zipper

And this API:

-- Move to the previous element
List.Zipper.next Previous zipper
-- Move to the previous element, wrapping around to the last element if none exists
List.Zipper.next PreviousCircular zipper

I think the former is much clearer.

[stoeffel]

I totally agree with Jasper's comment ☝️

[stoeffel]

closing because of inactivity