Unordered Zipper-style data structure

Hi all,

I have some unordered data in the form of key:value pairs, where one pair will always be in focus.

One way to code this would be to store the key:value pairs in a Dict along with the selected key:

type alias Model = {
    inFocus : Key
    data : Dict Key Value

This has a couple of downsides:

  • This enables a Key without a matching Value to be in focus!
  • This adds an extra layer of nesting, so any view or update code that has to use the in-focus Value requires an extra step of getting-or-setting.

This seems like a similar problem to that solved by the Zipper data structure (Elm package). However, a Zipper operates on an ordered list of items, and here we have unordered associative data. So, while a Zipper makes a distinction between unfocused items before and after the cursor, I only care about the item and the rest.

I could create a similar data structure like so:

type DictZipper k v =
    DictZipper (k, v) (Dict k v)

But I wanted to know whether such a thing already existed, whether there is a well-studied alternative that I ought to be looking at instead, or if anyone has come across a similar problem before.

1 Like

The list-extra api has the idea of a non-empty list.

Your API, to me, sounds like a non-empty dict. You are guaranteed to always have some element, organized as the default, and that’s the important requirement.

If you really only need a safe non-empty Dict where location of a focus element in the whole structure doesn’t matter → KeySet should do the job

users : Emptiable (KeySet User User.ByEmailHostFirst) neverEmpty_
users =
    KeySet.fromStack User.byEmailHostFirst
            (User { name = "Fred", email = })
            [ User { name = "Ann", email = }
            , User { name = "Bright", email = }

allowing safe access operations like

users |> KeySet.end Down -- minimum
--> { name = "Ann", email = } no Maybe

From what I inferred you actually want to keep the focus on the same element even if you insert elements, in which case a non-empty dict is not enough.

Thanks @z5h and @lue-bird - I think a non-empty dict doesn’t quite meet the requirements, but please correct me if this is wrong.

  • I want to be able to access the focus element, specifically (rather than just making sure an element exists)
  • I want to be able to swap the focus element

For example, if you were using tabs to structure your program UI, you might use a data structure like the one outlined in the opening post to keep track of the data within each tab, and whichever tab is in focus.

You get those features quite naturally by default when you guarantee that an element exists.
Here’s a bit of code. (Assuming you can code the rest.)

    The easiest (only) way to ensure we have a non-empty mapping (a dict)
    is to have one explicit (key,value), plus a separate (possibly empty) Dict).
type alias NonEmptyDict k v =
    ( ( k, v ), Dict k v )

    If we want to make one from a (possibly empty) dict, we need to specify/guarantee
    a default element. Since we can always get that element, you can consider it as the
    "default" or "focused" element. 
    We take the necessary step of ensuring we aren't duplicating the key.
fromDict : ( comparable, v ) -> Dict comparable v -> NonEmptyDict comparable v
fromDict ( focusedKey, focusedValue ) dict =
    ( ( focusedKey, focusedValue ), dict |> Dict.remove focusedKey )

  There are different ways of coding a setFocus, here we accept a key 
  and if we can find the key/value, then it becomes focused in the return,
  otherwise we get a nothing.
  One could instead accept a key/value and guarantee a result back.  
setFocus : comparable -> NonEmptyDict comparable v -> Maybe (NonEmptyDict comparable v)
setFocus key ( ( currentFocusKey, currentFocusValue ), dict ) =
    if key == currentFocusKey then
        Just ( ( currentFocusKey, currentFocusValue ), dict )

        Dict.get key dict
                (\newFocus ->
                    ( ( key, newFocus ), Dict.insert currentFocusKey currentFocusValue dict )


Thanks @z5h - yes, you’re right. And I see that List.NonEmpty has an analogous replaceHead function too.

1 Like

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