Map with fixed set of keys

[acoustic sapphire]

Trying to figure out a good way to model the concept of a fixed number of "slots" that can either hold something or not.

➡️ Tried using List(a), but it either requires a lot of let assert or dealing with Result(a, Nil) everywhere because technically the index might be out of bounds (annoying for "get and update" operations in particular). Also means when you delete an element it can change which slot(/index) other elements are in, which isn't a deal-breaker but would be nice to avoid.

➡️ Started looking into a #(Option(a), Option(a), Option(a)) tuple, but couldn't work out how to do "insert this element into the first empty slot" without either a big pattern-match on every possible combination of Some and None, or re-introducing the let assert/Result issues by going through a list.

➡️ Now looking at a Map(ID, a) with:

type ID {
  Slot1
  Slot2
  Slot3
}

...but once again got stuck on "insert element into first empty slot". To determine whether all slots are already filled, I'd want to iterate all the constructors of ID, which I think just has to be a hard-coded list since you can't get the type info at runtime; but then if (say) I add a Slot4 later, the code would still compile but the "insert" function would incorrectly act like there were only 3 slots.

Very possible there are other, better options (heh) I'm missing here.

[timber birch]

what should the api look like?

[vale willow]

Are you making a ring buffer?

[acoustic sapphire]

I think the most convenient would be (a being the element type, d the whole data structure, id being the identifier for which slot it's in)

pub fn insert(items: d, item: a) -> Result(#(d, id), Nil)
pub fn get(items: d, slot: id) -> Option(a) // or `Result(a, Nil)`
pub fn put(items: d, slot: id, item: a) -> d
pub fn delete(items: d, slot: id) -> d

(delete doesn't care if it wasn't there to begin with)

[acoustic sapphire]

I don't think so!

[vale willow]

I'd probably use this

pub opaque type Slots(id, element) {
  Slots(capacity: Int, data: Map(id, element)
}

[timber birch]

yeah asserts in the internal implementation are fine

aka you can be certain the internal repr is valid and not deal with the results from the Map

[acoustic sapphire]

well, I don't think using Map would require any asserts, but is it possible to solve the issue of needing to duplicate the list of id constructors to find whether all slots are occupied?

oh, are you saying that could be done by looking at the capacity

...but then that's sort of the same problem, whatever number you define for the capacity has to line up with the number of id constructors, but nothing enforces that it does

[vale willow]

Oh sorry I assumed it was an int, and then wrote my type really badly

[acoustic sapphire]

oh, it could very well be, actually

so in more concrete terms Slots(capacity: Int, data: Map(Int, a))?

[vale willow]

aye

id < 0 or id >= capacity is invalid, so a no-op or crash or whatever

[acoustic sapphire]

ah, yeah, that's why I was moving towards using an ID type with fixed number of constructors

in fact I guess Map(Int, a) basically is the List(a) approach but with slot assignment preservation, doesn't solve having to assert or Result everywhere when you get or update elements

[vale willow]

If like type Id { A B C D E F } then Map(Id, e) would do the trick, no?

[acoustic sapphire]

right, but then we come back to the issue of, how do I know where the first free slot is / whether there is one

[vale willow]

Oh right, the push operation

[acoustic sapphire]

at the very least it seems like it would require a constant storing the number of constructors for ID, which could then get out of sync with the actual number if you weren't careful (the compiler wouldn't catch it for you)

and probably, a hard-coded list of the actual constructors

[vale willow]

let used = d |> map.keys |> set.from_list
all_keys |> list.find(fn(k) { !set.contains(used, k) })

[timber birch]

define an ordering function for them (largest first), then map.keys() |> list.sort |> list.first

[vale willow]

Or you could maintain a list and push/pop

Few ways to do it, depends on what insertion order you want I think

[acoustic sapphire]

I'm a little confused now. is this assuming I initialize the map with all the keys it could have, and then the value type is Option(a)? if so doesn't that just move the "duplicate the list of ID constructors" problem over there?

[timber birch]

pub fn put(items: d, slot: id, item: a) -> d
what does put do if the slot is, say E but the map is only filled up to C?

it can be sparse?

but you want to know where the first available slot is so you can implement insert? is that right

[acoustic sapphire]

ideally I would like it to be sparse because then it means put can't error, even though in practice I will only be using put to update an already-occupied slot

oh, well, actually it needs to be sparse anyway because you can delete items

and ideally deleting should not reshuffle the keys assigned to other existing items

[timber birch]

is it polymorphic over id or are you defining the id yourself like with that ID type in OP?

[acoustic sapphire]

I'm defining the ID myself as in the example

this is making me think perhaps the best option would be some kind of sparse List underneath with convenience functions that accept an ID rather than an index and thus can't error

so it might look like [Some(item1), Some(item2)] and then if you put into Slot3 it expands the list, or if you delete Slot1 it becomes [None, Some(item2)]

ack, still need that constant that duplicates the ID constructors though...

perhaps I was unfair to the tuple approach... it's not so bad with only 3 elements

case slots {
  #(None, b, c) -> Ok(#(Some(new_item), b, c))
  #(a, None, c) -> Ok(#(a, Some(new_item), c))
  #(a, b, None) -> Ok(#(a, b, Some(new_item)))
  _all_filled -> Error(Nil)
}

thinking it's either that or make a few extra functions to untangle the Result spaghetti from using List