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

import KeysSet exposing (KeysSet)
import Stack
import User exposing (User(..))


users : Emptiable (KeysSet User User.ByName) never_
users =
    KeysSet.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 Char.Order
import Keys exposing (Key, Keys)
import KeysSet
import Map exposing (Mapping)
import Order
import String.Order


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


type Name
    = Name


name : Mapping User Name String
name =
    Map.tag Data (\(User userData) -> userData.name)


type alias ByName =
    { name :
        Key
            User
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.Alphabetically Char.Order.LowerUpper)
                )
            )
            String
            (Up N0 To N0)
    }


byName : Keys User ByName N0
byName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( identity, Map.identity )
            (String.Order.earlier
                (Char.Order.alphabetically Char.Order.lowerUpper)
            )

KeysSet containing a single given element.

You don't need to provide Keys

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

KeysSet.fromStack User.byHandle
    (Stack.topBelow
        -- ↓ won't be part of the KeysSet
        { handle = "cr", shown = "chris \\o/" }
        [ { handle = "ann", shown = "Ann in stand by" }
        , { 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 about its (non-)emptiness

Number of elements in the KeysSet. Runtime 1

KeysSet.one { name = "Helium", symbol = "He", atomicNumber = 2 }
    |> KeysSet.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)
import Typed
import Stack
import N exposing (Up, To, N0, N1)
import Keys exposing (Keys, Key)
import KeysSet exposing (KeysSet)
import Map exposing (Mapping)
import Order
import Char.Order
import String.Order


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


type AnimalKind
    = Mouse
    | Cat


type alias ByName =
    { name :
        Key
            Animal
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.Alphabetically Char.Order.LowerUpper)
                )
            )
            String
            (Up N0 To N0)
    }


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


type Name
    = Name -- not exposed


name : Mapping Animal Name String
name =
    Map.tag Name .name


animalByName : Keys Animal ByName N1
animalByName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( .name, name )
            (String.Order.earlier
                (Char.Order.alphabetically Char.Order.lowerUpper)
            )


animals |> KeysSet.element ( animalByName, .name ) "Tom" |> Emptiable.map .kind
--> filled Cat


animals |> KeysSet.element ( animalByName, .name ) "Jerry" |> Emptiable.map .kind
--> filled Mouse


animals |> KeysSet.element ( animalByName, .name ) "Spike" |> Emptiable.map .kind
--> Emptiable.empty

The element associated with the lowest key

import Emptiable exposing (Emptiable)
import N exposing (Up, To, N0, N1)
import Stack
import KeysSet exposing (KeysSet)
import Map exposing (Mapping)
import Order
import Char.Order
import String.Order
import Keys exposing (Keys, Key)


users : Emptiable (KeysSet User ByName N1) never_
users =
    KeysSet.fromStack userByName
        (Stack.topBelow
            { name = "Bob", age = 19, height = 1.80 }
            [ { name = "Alia", age = 28, height = 1.69 }
            , { name = "Chucki", age = 33, height = 1.75 }
            ]
        )


users |> KeysSet.minimum ( userByName, .name )
--> { name = "Alia", age = 28, height = 1.69 }


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


type alias ByName =
    { name :
        Key
            User
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.Alphabetically Char.Order.LowerUpper)
                )
            )
            String
            (Up N0 To N0)
    }


type Name
    = Name -- not exposed


name : Mapping User Name String
name =
    Map.tag Name .name


userByName : Keys User ByName N1
userByName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( .name, name )
            (String.Order.earlier
                (Char.Order.alphabetically Char.Order.lowerUpper)
            )

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

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

users
    |> Emptiable.map (filled >> KeysSet.minimum ( userByName, .name ))
--: Emptiable element Possibly

The element associated with the greatest key

import Emptiable exposing (Emptiable)
import N exposing (Up, To, N0, N1)
import Stack
import KeysSet exposing (KeysSet)
import Map exposing (Mapping)
import Order
import Char.Order
import String.Order
import Keys exposing (Keys, Key)


users : Emptiable (KeysSet User ByName N1) never_
users =
    KeysSet.fromStack userByName
        (Stack.topBelow
            { name = "Bob", age = 19, height = 1.80 }
            [ { name = "Alia", age = 28, height = 1.69 }
            , { name = "Chucki", age = 33, height = 1.75 }
            ]
        )


users |> KeysSet.maximum ( userByName, .name )
--> { name = "Chucki", age = 33, height = 1.75 }


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


type alias ByName =
    { name :
        Key
            User
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.Alphabetically Char.Order.LowerUpper)
                )
            )
            String
            (Up N0 To N0)
    }


type Name
    = Name -- not exposed


name : Mapping User Name String
name =
    Map.tag Name .name


userByName : Keys User ByName N1
userByName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( .name, name )
            (String.Order.earlier
                (Char.Order.alphabetically Char.Order.lowerUpper)
            )

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

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

users
    |> Emptiable.map (filled >> KeysSet.maximum ( userByName, .name ))
--: Emptiable element Possibly

Insert a given element. If the element you wanted to insert already has elements with a matching key (collisions), keep the existing collision elements instead. To replace collisions instead → insertReplacingCollisions

import BracketPair
import Emptiable


Emptiable.empty
    |> KeysSet.insertIfNoCollision BracketPair.keys
        { open = 'b', closed = 'C' }
    |> KeysSet.insertIfNoCollision BracketPair.keys
        { open = 'c', closed = 'A' }
    |> KeysSet.insertIfNoCollision BracketPair.keys
        { open = 'c', closed = 'C' }
    |> KeysSet.toList ( BracketPair.keys, .open )
--> [ { open = 'b', closed = 'C' }, { open = 'c', closed = 'A' } ]

Insert a given element. If the element you wanted to insert already has elements with a matching key (collisions), replace all collisions. To keep collisions instead → insertIfNoCollision

import BracketPair
import Emptiable


Emptiable.empty
    |> KeysSet.insertReplacingCollisions BracketPair.keys
        { open = 'b', closed = 'C' }
    |> KeysSet.insertReplacingCollisions BracketPair.keys
        { open = 'c', closed = 'A' }
    |> KeysSet.insertReplacingCollisions BracketPair.keys
        { open = 'c', closed = 'C' }
    |> KeysSet.toList ( BracketPair.keys, .open )
--> [ { open = 'c', closed = 'C' } ]

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

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }
    , { id = 1, char = 'B' }
    ]
    |> KeysSet.insertIfNoCollision Character.keys
        { id = 2, char = 'C' }
    |> KeysSet.remove ( Character.keys, .id ) 2
    |> KeysSet.toList ( Character.keys, .id )
--> [ { id = 0, char = 'A' }
--> , { id = 1, char = 'B' }
--> ]

Change the element with a given key in a given way Only actually alter the element if the result doesn't have existing elements with a matching key (collisions). To replace collisions with the result instead → elementAlterReplacingCollisions

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }, { id = 1, char = 'B' } ]
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | char = 'C' })
        -- gets changed
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | id = 0 })
        -- doesn't get changed
    |> KeysSet.toList ( Character.keys, .id )
    --> [ { id = 0, char = 'A' }, { id = 1, char = 'C' } ]

If you want to sometimes remove or insert a new value on empty for example, first ask for the element with the same key, then match the Emptiable and operate as you like

Change the element with a given key in a given way If the result has existing elements with a matching key (collisions), replace them. To not alter the element if there are collisions with the result instead → elementAlterIfNoCollision

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }, { id = 1, char = 'B' } ]
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | char = 'C' })
        -- gets changed
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | id = 0 })
        -- doesn't get changed
    |> KeysSet.toList ( Character.keys, .id )
    --> [ { id = 0, char = 'A' }, { id = 1, char = 'C' } ]

If you want to sometimes remove or insert a new value on empty for example, first ask for the element with the same key, then match the Emptiable and operate as you like

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)

If the keys of the mapped elements collide, there's no promise of which element will be in the final mapped KeysSet

Try to change each element based on its current value.

Runtime n * log n just like KeysSet.map because mapped keys could be different

If the keys of the mapped elements collide, there's no promise of which element will be in the final mapped KeysSet

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


            else
                Nothing
        )
        orderKey

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

(To instead replace current elements with incoming elements, swap the arguments)

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

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }
    , { id = 1, char = 'B' }
    , { id = 2, char = 'c' }
    , { id = 3, char = 'd' }
    ]
    |> KeysSet.except ( Character.keys, .id )
        (KeysSet.fromList Character.keys
            [ { id = 2, char = 'c' }
            , { id = 3, char = 'd' }
            , { id = 4, char = 'e' }
            , { id = 5, char = 'f' }
            ]
            |> KeysSet.toKeys ( Character.keys, .id )
        )
    |> KeysSet.toList ( Character.keys, .id )
--> [ { id = 0, char = 'A' }
--> , { id = 1, char = 'B' }
--> ]

Keep each element whose key also appears in a given KeysSet

Most powerful way of combining 2 KeysSets

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

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

A KeysSet sorted by the identity of one of the keys of the original set. Runtime is O(n).

Convert to a List sorted by a given key

import N exposing (Up, To, N0)
import Stack
import Map
import Order
import Char.Order
import String.Order
import Keys exposing (Keys, Key)
import KeysSet


nameAlphabetical : Keys.Identity String (String.Order.Earlier (Char.Order.Alphabetically Char.Order.LowerUpper))
nameAlphabetical =
    Keys.identity
        (String.Order.earlier
            (Char.Order.alphabetically Char.Order.lowerUpper)
        )


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeysSet.toStack ( nameAlphabetical, identity )
--> Stack.topBelow "Alice" [ "Bob" ]


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice", "Christoph" ])
    |> KeysSet.toStack ( nameAlphabetical, identity )
    |> Stack.reverse
--> Stack.topBelow "Christoph" [ "Bob", "Alice" ]

The cool thing is that information about (non-)emptiness is carried over to the stack

Use this to fold over its elements

import N exposing (Up, To, N0)
import Map
import Stack
import Order
import Int.Order
import Keys exposing (Keys, Key)
import KeysSet
import Linear exposing (Direction(..))


intIncreasing : Keys.Identity Int Int.Order.Increasing
intIncreasing =
    Keys.identity Int.Order.increasing


KeysSet.fromStack intIncreasing
    (Stack.topBelow 345 [ 234, 543 ])
    |> KeysSet.toStack ( intIncreasing, identity )
--> Stack.topBelow 234 [ 345, 543 ]
--  the type knows it's never empty


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

Convert to a List

import N exposing (Up, To, N0)
import Stack
import Keys exposing (Keys, Key)
import KeysSet
import Map
import Order
import Char.Order
import String.Order


nameAlphabetical : Keys.Identity String (String.Order.Earlier (Char.Order.Alphabetically Char.Order.LowerUpper))
nameAlphabetical =
    Keys.identity
        (String.Order.earlier
            (Char.Order.alphabetically Char.Order.lowerUpper)
        )


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


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeysSet.toList ( nameAlphabetical, identity )
    |> List.reverse
--> [ "Bob", "Alice" ]

to carry over information about (non-)emptiness → toStack

Using == on KeysSets will be slower than toList if you have more than 2 keys.

Fold over its elements from an initial accumulator value

import N exposing (Up, To, N0)
import Stack
import Map
import Order
import Int.Order
import KeysSet
import Keys exposing (Keys, Key)


KeysSet.fromStack intIncreasing
    (Stack.topBelow 234 [ 345, 543 ])
    |> KeysSet.foldFrom [] (::)
-- no! you shouldn't rely on order with fold


KeysSet.fromStack intIncreasing
    (Stack.topBelow 5 [ 7, -6 ])
    |> KeysSet.foldFrom 0 (+)
--> 6


intIncreasing : Keys.Identity Int Int.Order.Increasing
intIncreasing =
    Keys.identity Int.Order.increasing

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

import Stack
import KeysSet
import Int.Order


intIncreasing : Keys.Identity Int Int.Order.Increasing
intIncreasing =
    Keys.identity Int.Order.increasing


KeysSet.fromStack intIncreasing
    (Stack.topBelow 1 [ 2, 8, 16 ])
    |> KeysSet.fold (\n soFar -> soFar - n)
-- no! you shouldn't rely on order with fold

Fold, starting from one end element transformed to the initial accumulation value, then reducing what's accumulated.

import Stack
import N exposing (Up, To, N0)
import Map
import Order
import Int.Order
import Keys exposing (Keys, Key)
import KeysSet


KeysSet.fromStack intIncreasing
    (Stack.topBelow 234 [ 345, 543 ])
    |> KeysSet.foldFromOne Stack.one Stack.onTopLay
--> Stack.topBelow 543 [ 345, 234 ]
-- no! you shouldn't rely on order with fold
-- the type knows it's never empty


intIncreasing : Keys.Identity Int Int.Order.Increasing
intIncreasing =
    Keys.identity Int.Order.increasing

A simpler version is fold

KeysSet.fold =
    KeysSet.foldFromOne identity