🗃️ KeysSet
lookup for multiple arbitrary keys. safe. log n
🌏 Let's build a country lookup with .code
and .flag
as keys
KeysSet.fromList keys
[ { flag = "🇦🇺", code = "AU", name = "Australia" }
, { flag = "🇦🇶", code = "AQ", name = "Antarctica" }
, { flag = "🇱🇧", code = "LB", name = "Lebanon" }
]
type alias Country =
{ flag : String, code : String, name : String }
With a key to compare against, you can find the matching element
in log n
time:
|> KeysSet.element (key .flag keys) "🇦🇶"
--→ Just { flag = "🇦🇶", code = "AQ", name = "Antarctica" }
|> KeysSet.element (key .code keys) "LB"
--→ Just { flag = "🇱🇧", code = "LB", name = "Lebanon" }
|> KeysSet.end (key .code keys) Down -- minimum
--→ { flag = "🇦🇶", code = "AQ", name = "Antarctica" } no Maybe
We supplied keys
to construct and operate on our KeysSet
,
so... Which aspects do we want it to be sorted by?
keys : Keys Country CountryKeys N2
keys =
Keys.for (\flag_ code_ -> { flag = flag_, code = code_ })
|> Keys.by ( .flag, flag )
(String.Order.earlier Char.Order.unicode)
|> Keys.by ( .code, code )
(String.Order.earlier (Char.Order.aToZ Order.tie))
KeysSet
holds no functions, so the Keys
have to be supplied on every operation.
To ensure these given Keys
are always the same for one KeysSet
,
we need some boilerplate,
attaching opaque tags:
type Flag =
-- ! no exposing (..) → only constructable in this module
Flag
flag : Mapping Country Flag String
flag =
Map.tag Flag .flag
type Code
-- no exposing (..)
= Code
code : Mapping Country Code String
code =
Typed.tag Code .code
type alias CountryKeys =
-- you can just infer this
{ flag : Key Country (Order.By Flag (String.Order.Earlier Char.Order.Unicode)) N2
, code : Key Country (Order.By Code (String.Order.Earlier (Char.Order.AToZ Order.Tie))) N2
}
Feels somewhat like "explicit typeclasses" :)
→ Solves problems listed in prior art alongside other goodies
🧩
-
when annotating a
KeysSet
, you'll run into types likeEmptiable (KeysSet ...) Never -> ...
-> Emptiable (KeysSet ...) never_
which say: the
KeysSet
can never be emptyand
-> Emptiable (KeysSet ...) Possibly
Emptiable (KeysSet ...) possiblyOrNever -> ...
which say: the
KeysSet
can possibly be empty.emptiness-typed
lets us conveniently use one API for both non-empty and emptiable types. -
the types of key counts like
N2
can be found inbounded-nat
. No need to understand the details; type inference has your back. -
Wanna dig a bit deeper? Giving an
Ordering
orMapping
a unique tag is enabled bytyped-value
: convenient control of reading and writing for tagged things.
another example: operator
import KeysSet exposing (KeysSet)
import Emptiable exposing (Emptiable)
import Possibly exposing (Possibly)
import Keys exposing (Key, key, Keys)
import Order
import String.Order
import Char.Order
import Map exposing (Mapping)
import N exposing (N2)
type alias Operator =
{ symbol : String, name : String, kind : OperatorKind }
operatorKeys : Keys Operator OperatorKeys N2
operatorKeys =
Keys.for (\symbol_ name_ -> { symbol = symbol_, name = name_ })
|> Keys.by ( .symbol, symbol )
(String.Order.earlier Char.Order.unicode)
|> Keys.by ( .name, name )
(String.Order.earlier (Char.Order.aToZ Order.tie))
type alias OperatorKeys =
{ symbol : Key Operator (Order.By Symbol (String.Order.Earlier Char.Order.Unicode)) String N2
, name : Key Operator (Order.By Name (String.Order.Earlier Char.Order.AToZ (Order.Tie))) String N2
}
operators : Emptiable (KeysSet Operator OperatorKeys N2) never_
operators =
KeysSet.fromStack operatorKeys
(Stack.topBelow
{ symbol = ">", name = "gt", kind = Binary }
[ { symbol = "<", name = "lt", kind = Binary }
, { symbol = "==", name = "eq", kind = Binary }
, { symbol = "-", name = "negate", kind = Unary }
]
)
nameOfOperatorSymbol : String -> Emptiable String Possibly
nameOfOperatorSymbol operatorSymbol =
operators
|> KeysSet.element (key .symbol operatorKeys) operatorSymbol
type Name
= Name
name : Mapping Operator Name String
name =
Map.tag Name .name
type Symbol
= Symbol
symbol : Mapping Operator Symbol String
symbol =
Map.tag Symbol .symbol
example: automatic answers
type alias ConversationStep =
{ youSay : String, answer : String }
type alias ByYouSay =
Key ConversationStep (Order.By YouSay (String.Order.Earlier (Char.Order.AToZ Order.Tie))) String N1
youSayKey : Keys ConversationStep ByYouSay N1
youSayKey =
Keys.oneBy youSay (String.Order.earlier (Char.Order.aToZ Order.tie))
answers : Emptiable (KeysSet ConversationStep ByYouSay N1) Possibly
answers =
KeysSet.fromList youSayKey
[ { youSay = "Hi"
, answer = "Hi there!"
}
, { youSay = "Bye"
, answer = "Ok, have a nice day and spread some love."
}
, { youSay = "How are you"
, answer = "I don't have feelings :("
}
, { youSay = "Are you a robot"
, answer = "I think the most human answer is 'Haha... yes'"
}
]
example: user
import Emptiable exposing (Emptiable)
import Stack
import KeysSet exposing (KeysSet)
import N exposing (N2)
import User exposing (User(..))
exampleUsers : Emptiable (KeysSet User User.Keys N2) never_
exampleUsers =
KeySet.fromStack User.keys
(Stack.topBelow
(User { name = "Fred", email = ..@out.tech.. })
[ User { name = "Ann", email = ..ann@mail.xyz.. }
, User { name = "Annother", email = ..ann@mail.xyz.. }
, User { name = "Bright", email = ..@snail.studio.. }
]
)
exampleUsers |> KeySet.size
--→ 3
exampleUsers |> KeySet.element User.keys ..ann@mail.xyz..
--→ Emptiable.filled { name = "Ann", email = ..ann@mail.xyz.. }
-- module User exposing (User(..), Keys, keys)
import KeySet
import Keys
import Order
import String.Order
import Char.Order
import Map exposing (Mapping)
import N exposing (N2)
import Email
type User
= User
{ email : Email
, name : String
, settings : Settings
}
type EmailTag
= Email
email : Mapping User EmailTag Email
email =
Map.tag Email (\(User userData) -> userData.email)
type NameTag
= Name
name : Mapping User NameTag String
name =
Map.tag Name (\(User userData) -> userData.name)
keys : Keys.Keys User Keys N2
keys =
Keys.for (\email_ name_ -> { email = email_, name = name_ })
|> Keys.by ( .email, email ) Email.byHostFirst
|> Keys.by ( .name, name )
(String.Order.earlier (Char.Order.aToZ Order.tie))
type alias Keys =
{ email : Key User (Order.By EmailTag Email.ByHostFirst) Email N2
, name : Key User (Order.By NameTag (String.Order.Earlier (Char.Order.AToZ Order.Tie))) String N2
}
-- module Email exposing (Email, byHostFirst, ByHostFirst)
type alias Email =
{ host : String, label : String }
type alias ByHostFirst =
Order.OnTieNext
(Order.By Email.HostTag (String.Order.Earlier (Char.Order.AToZ Order.Tie)))
(Order.By Email.LabelTag (String.Order.Earlier (Char.Order.AToZ Order.Tie)))
byHostFirst : Ordering Email ByHostFirst
byHostFirst =
Order.by Email.host
(String.Order.earlier (Char.Order.aToZ Order.tie))
|> Order.onTie
(Order.by Email.label
(String.Order.earlier (Char.Order.aToZ Order.tie))
)
import KeysSet exposing (KeysSet)
import Keys exposing (key)
import Emptiable exposing (Emptiable)
import Possibly exposing (Possibly)
import N exposing (N2)
type alias State =
{ users : Emptiable (KeysSet User UserKeys N2) Possibly
, activeUserName : String
}
initialState : State
initialState =
{ users = exampleUsers }
reactTo event =
case event of
Registered { name, email } ->
\state ->
case state.users |> KeysSet.element (key .name User.keys) name of
Emptiable.Filled _ ->
-- name taken already
Emptiable.Empty _ ->
case state.users |> KeysSet.element (key .email User.keys) email of
Emptiable.Filled _ ->
-- email taken already
Emptiable.Empty _ ->
{ state
| users =
state.users
|> KeysSet.insert User.keys
{ name = name
, email = email
, settings = defaultSettings
}
}
SettingsChanged settingsChange ->
\state ->
{ state
| users =
state.users
|> KeysSet.elementAlterIfNoCollision
(key .name User.keys)
state.activeUserName
(applySettingsChange settingsChange)
}
UserSwitched name ->
\state -> { state | activeUserName = name }
anti-example: partners, synonyms, opposites...
partnerKeys =
Keys.for
(\partner_ partnerOfPartner_ ->
{ partner = partner_, partnerOfPartner = partnerOfPartner_ }
)
|> Keys.by ( .partner, partner )
(String.Order...)
|> Keys.by ( .partnerOfPartner, partnerOfPartner )
(String.Order...)
partners =
KeysSet.fromList partnerKeys
[ { partner = "Ann", partnerOfPartner = "Alan" }
, { partner = "Alex", partnerOfPartner = "Alistair" }
, { partner = "Alan", partnerOfPartner = "Ann" }
-- wait, this is no duplicate and is inserted
]
A KeysSet
ony makes sense when the keys describe something different
Maybe take a look at graphs or elm-bidict instead.
goodies
- 🦄 multiple possible
log n
keys - ⚖ sorted by
Ordering key = ... key, key -> Order
- 👍 no reliance on
comparable
- 👍 no inconvenient
key -> String
- 👍 no extra type argument for
comparableKey
- 👍 highly customizable with stuff like
Order.reverse
- 👍 no reliance on
- 🔑
element -> key
function as part of a givenKey
- 👍 simpler type
- 👍 simpler internals :)
- same idea is also implemented in
- no stored function but tags to ensure the given
Keys
are the same- 👍 debugger, json import/export work
- 👍 lamdera works
- 👍 hot module reloading → never have an old model
- 👍 no accidental (==) crash
- 🗃 emptiability is part of the type
- just use the same API with emptiable or non-empty conveniently
- 👍 extra safety possible. Got enough elements? →
KeySet.minimum
,maximum
,foldFromOne
,fold
don't needMaybe
- 🧩
allowable-state
- 🧩
emptiness-typed
prior art
-
comparableKey
- examples
- 👎 requires a new
Dict
/Set
wrapper when its key contains a customtype
. Often more a hindrance than helpful - 👎 no way to provide a different sorting, e.g. saying
'a'
should be less than'A'
- using an ordering function (to
comparable
ork -> k -> Order
or a wrapper)-
key -> key -> Order
- examples
- 👍 simple to create
- see for example
Order
's prior art
- see for example
- 👍 simple type
- 👍 not limited to
comparable
keys. Therefore simpler while not relying on magic
-
... -> comparable
- examples
- 👎 no nice way to provide a different sorting, e.g. saying
'a'
should be less than'A'
- 👎 more prone to bugs in
toComparable
implementation not returning a uniquecomparable
for all keys - 👎 slightly less performant when
toComparable
needs to do heavy work (e.g. convert to a list) -
key -> String
- examples (in no specific order)
- 👍 avoid having an extra type variable
- 👎 requires more work
- custom ordering wrapper
- examples
- 👍 simple to create
- 👍 simple type
- 👍 not limited to
comparable
keys. Therefore simpler while not relying on magic - 👍 guided experience – no getting confused that a type aliases a function
choiceTypeOrder : Ordering ChoiceType choiceTypeOrder what the = ???
- 👎 libraries often duplicate the ordering wrapper API instead of using a pre-existing one
- build the complete API from a given function
- examples
-
edkelly303/elm-any-type-collections
Any.Set
,Any.Dict
with atoComparable
function- 👎 dead code elimination doesn't work
- 👎 obscure API and interface type
-
miniBill/elm-generic-dict
GenericDict
GenericSet
with atoComparable
function- 👎 code duplication
-
- using the constructed API is rather simple
- 👎 semantic versioning doesn't work
- 👍 simple type
- 👍 nicely compact
- 👍 functions aren't stored in the data structure
- using for example
insert
from the wrong API "instance" with a different function is still possible but less likely to happen in practice
- examples
- specify that users should wrap the dict/set type for a specific ordering (not code generation)
- 👍 simple type
- 👍 nicely compact
- 👍 functions aren't stored in the data structure
- 👎 quite a bit of manual labour without a clear need
- 👎 API changes to the original dict/set type do not get propagated
- stored in the data structure
- 👍 minimal clutter while still being explicit
- 👎 needs to be stored in the type →
==
among other things will fail - 👎 slightly more cluttered API including
clear
to only remove all elements but keep the function
- ordering given on every insertion/removal operation
- 👎 a tiny bit less compact
- 👎 no guarantee that the given functions are the same
between operations or
when trying to combine (
union
,intersection
, ...)
- ordering given on each access and operation
- 👎 a bit less compact
- 👎 no guarantee that the given functions are the same
-
- association-list
- examples
- 👎
n
runtime - 👍 no setup
- 👍 simple type
- tagging keys and the structure
- examples
- idea is quite similar to
KeysSet
but - 👎 relies on
comparable
- 👎 everyone can tag without the tag name so only security by a bit more obscurity
- just the function
key -> Maybe value
instead of a data structure- examples
- 👎
>= n
runtime - 👎 doesn't simplify it's structure. Every remove, insert, union, difference, adds to the function logic
- 👍 pretty easy to understand and build on with powerful features like assigning a specific value x whenever a condition is met
future ideas
- set with multiple elements per key (= multi-set/bag) add? or is this already covered good enough
- ✨ your idea