🗃️ Non-empty AVL-tree-based look-up. Elements and keys can be of any type

insert, elementRemove, element, end runtime is log n

import KeySet exposing (KeySet)
import Stack
import User exposing (User(..))


users : Emptiable (KeySet User User.ByName) never_
users =
    KeySet.fromStack User.byName
        (Stack.topBelow
            (User { name = "Alice", age = 28, height = 1.65 })
            [ User { name = "Bob", age = 19, height = 1.82 }
            , User { name = "Chuck", age = 33, height = 1.75 }
            ]
        )

where

module User exposing (ByName, User(..), byName)


import KeySet
import Order


type User
    = User { name : String, age : Int, height : Float }


type ByName
    = ByName


byName : KeySet.Sorting User String ByName
byName =
    KeySet.sortingKey .name
        { tag = ByName
        , order = String.Order.greaterEarlier (Char.Order.alphabetically Case.lowerUpper)
        }

Configure what's considered a key inside a KeySet

Create using sortingKey, as shown in

• KeySet example
• readme example

You can just ignore the Typed thing but if you're curious → typed-value

By which aspect = key and in which key Order the elements are sorted

For example, to create a Sorting to use with a simple set, use

sortingKey identity ..tag..order..

more in

• KeySet example
• readme example

KeysSet containing a single given element

Convert to a KeysSet, ignoring elements whose keys already exist earlier in the Stack

Keyset.fromStack User.ByHandle
    (Stack.topBelow
        { handle = "cr", shown = "chris \\o/" }
        [ { handle = "ann", shown = "Ann in stand by" }
        , -- ↓ won't be part of the KeySet
          { handle = "cr", shown = "creeper" }
        ]
    )

Convert to a KeysSet, ignoring elements whose keys already exist earlier in the List

For construction, use fromStack, proving to the compiler what you already know

Number of elements in the KeysSet. Runtime 1

KeySet.only "Hello"
    |> KeySet.size
--> 1

Access the element associated with a given key. If no element with the given key is not present, Emptiable.empty

import Emptiable exposing (Emptiable, filled, fillMap)
import Stack
import KeySet exposing (KeySet)
import Case
import Char.Order
import String.Order


type alias Animal =
    { name : String
    , kind : AnimalKind
    }


type AnimalKind
    = Mouse
    | Cat


animals : Emptiable (KeySet Animal { byName : () }) never_
animals =
    KeySet.fromStack animalByName
        (Stack.topBelow
            { name = "Tom", kind = Cat }
            [ { name = "Jerry", kind = Mouse }
            ]
        )


-- should be opaque and should use an opaque tag
animalByName : KeySet.Sorting Animal String { byName : () }
animalByName =
    KeySet.sortingKey .name
        { tag = { byName = () }
        , order =
            String.Order.greaterEarlier (Char.Order.alphabetically Case.lowerUpper)
        }


animals |> KeySet.element animalByName "Tom" |> fillMap .kind
--> filled Cat


animals |> KeySet.element animalByName "Jerry" |> fillMap .kind
--> filled Mouse


animals |> KeySet.element animalByName "Spike" |> fillMap .kind
--> Emptiable.empty

Get the element associated with a key at the end looking in a given Direction

• minimum → end Down
• maximum → end Up

KeySet is empty → Nothing

import Linear exposing (Direction(..))
import Emptiable exposing (Emptiable)
import Stack
import KeySet exposing (KeySet)
import Case
import Char.Order
import String.Order




type alias User =
    { name : String
    , age : Int
    , height : Float
    }


users : Emptiable (KeySet User { userByName : () }) never_
users =
    KeySet.fromStack userByName
        (Stack.topBelow
            { name = "Bob", age = 19, height = 1.82 }
            [ { name = "Alice", age = 28, height = 1.65 }
            , { name = "Chuck", age = 33, height = 1.75 }
            ]
        )


-- ↓ and tag should be opaque
userByName : KeySet.Sorting User String { userByName : () }
userByName =
    KeySet.sortingKey .name
        { tag = { userByName = () }
        , order =
            String.Order.greaterEarlier (Char.Order.alphabetically Case.lowerUpper)
        }


users |> KeySet.end Down
--> { name = "Alice", age = 28, height = 1.65 }


users |> KeySet.end Up
--> { name = "Chuck", age = 33, height = 1.75 }

Notice how we safely avoided returning a Maybe through the use of Emptiable ... Never

If you don't know whether the KeySet will be empty

users
    |> fillMap (\us -> us |> filled |> KeySet.end Up)
--: Emptiable element Possibly

Insert a given element. Replaces the element when there is a key collision

Remove its element whose key matches the given one. If the key is not found, no changes are made

Change the element for a given key in a given way

• The input is the same as asking for the element with the same key
• Outputting empty is the same as calling elementRemove with the same key

Operations with Emptiable that might be handy

• fillMap
• fillMapFlat
• fillElseOnEmpty
• filled

Change each element based on its current value. Runtime n * log n because mapped keys could be different (many other dicts/sets have runtime n)

Try to change each element based on its current value. Runtime n * log n just like KeySet.map because mapped keys could be different

{-| Keep only elements that pass a given test.
Often called "filter"
-}
when sorting isGood =
    KeySet.mapTry
        (\element ->
            if element |> isGood then
                Just element


            else
                Nothing
        )
        sorting

Combine with another KeySet. On key collision, keep the current KeySet's element

Keep only those elements whose keys don't appear in the given KeySet

Keep each element whose key also appears in a given KeySet

Most powerful way of combining 2 KeySets

Traverses all the keys from both KeySets from lowest to highest, accumulating whatever you want for when a key appears in either the FirstOrSecondOrBoth of the KeySets

You will find this as "merge" in most other dictionaries/sets

Unresolved element state while merging a "first" and "second" structure

• only in the First structure
• only in the Second structure
• in both FirstSecond

FirstSecond has a tuple instead of a more descriptive record to make matching easier

Convert to a List sorted by keys in a given Direction

import Linear exposing (Direction(..))
import Stack
import KeySet
import Case
import Char.Order
import String.Order


-- tag should be opaque in a separate module
nameAlphabetical : KeySet.Sorting String String { alphabetical : () }
nameAlphabetical =
    KeySet.sortingKey identity
        { tag = { alphabetical = () }
        , order = String.Order.greaterEarlier (Char.Order.alphabetically Case.lowerUpper)
        }


KeySet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeySet.toList Up
--> [ "Alice", "Bob" ]


KeySet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeySet.toList Down
--> [ "Bob", "Alice" ]

Fold over its elements from an initial accumulator value either

• Up from lowest key to highest
• Down from highest key to lowest

import Linear exposing (Direction(..))
import Stack
import Int.Order
import KeySet

KeySet.fromStack intIncreasing
    (Stack.topBelow 234 [ 345, 543 ])
    |> KeySet.foldFrom [] Down (::)
--> [ 234, 345, 543 ]

KeySet.fromStack intIncreasing
    (Stack.topBelow False [ True, False ])
    |> KeySet.foldFrom 0 Up (||)
--> True

-- ↓ and tag should be opaque
intIncreasing : KeySet.Sorting Int Int { increasing : () }
intIncreasing =
    KeySet.sortingKey identity
        { tag = { increasing = () }
        , order = Int.Order.increasing
        }

Fold, starting from one end element transformed to the initial accumulation value, then reducing what's accumulated in a given Direction

import Linear exposing (Direction(..))
import Stack
import Int.Order
import KeySet


KeySet.fromStack intIncreasing
    (Stack.topBelow 234 [ 345, 543 ])
    |> KeySet.foldOnto Stack.only Up Stack.onTopLay
--> Stack.topBelow 543 [ 345, 234 ]
--  the type knows it's never empty


-- ↓ and tag should be opaque
intIncreasing : KeySet.Sorting Int Int { increasing : () }
intIncreasing =
    KeySet.sortingKey identity
        { tag = { increasing = () }
        , order = Int.Order.increasing
        }

A simpler version is fold

KeySet.fold =
    KeySet.foldOnto identity

Fold, starting from one end as the initial accumulation value, then reducing what's accumulated in a given Direction

import Linear exposing (Direction(..))
import Stack
import KeySet
import Int.Order


KeySet.fromStack intIncreasing
    (Stack.topBelow 1 [ 2, 8, 16 ])
    |> KeySet.fold Down (\n soFar -> soFar - n)
--> 5


-- ↓ and tag should be opaque
intIncreasing : KeySet.Sorting Int Int { increasing : () }
intIncreasing =
    KeySet.sortingKey identity
        { tag = { increasing = () }
        , order = Int.Order.increasing
        }