ποΈ 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 MaybeWe 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
KeysSetcan never be emptyand
-> Emptiable (KeysSet ...) Possibly
Emptiable (KeysSet ...) possiblyOrNever -> ...
which say: the
KeysSetcan possibly be empty.emptiness-typedlets us conveniently use one API for both non-empty and emptiable types. -
the types of key counts like
N2can be found inbounded-nat. No need to understand the details; type inference has your back. -
Wanna dig a bit deeper? Giving an
OrderingorMappinga unique tag is enabled bytyped-value: convenient control of reading and writing for tagged things.
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 .symboltype 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'"
}
]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 }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.
- π¦ multiple possible
log nkeys - β 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 -> keyfunction as part of a givenKey- π simpler type
- π simpler internals :)
- same idea is also implemented in
- no stored function but tags to ensure the given
Keysare 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,folddon't needMaybe - π§©
allowable-state - π§©
emptiness-typed
comparableKey- examples
- π requires a new
Dict/Setwrapper 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
comparableork -> k -> Orderor a wrapper)key -> key -> Order- examples
- π simple to create
- see for example
Order's prior art
- see for example
- π simple type
- π not limited to
comparablekeys. 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
toComparableimplementation not returning a uniquecomparablefor all keys - π slightly less performant when
toComparableneeds 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
comparablekeys. 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-collectionsAny.Set,Any.Dictwith atoComparablefunction- π dead code elimination doesn't work
- π obscure API and interface type
miniBill/elm-generic-dictGenericDictGenericSetwith atoComparablefunction- π 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
insertfrom 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
clearto 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
- π
nruntime - π no setup
- π simple type
- tagging keys and the structure
- examples
- idea is quite similar to
KeysSetbut - π relies on
comparable - π everyone can tag without the tag name so only security by a bit more obscurity
- just the function
key -> Maybe valueinstead of a data structure- examples
- π
>= nruntime - π 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
- set with multiple elements per key (= multi-set/bag) add? or is this already covered good enough
- β¨ your idea