Set.Any

A set of unique values. Similar to elm/core Set but allows arbitrary data given a function for converting to comparable can be provided.

Insert, remove, and query operations all take O(log n) time.

Converting Types to Comparable

When writing a function for conversion from the type you want to use within a set to comparable it's very important to make sure every distinct member of the type produces different value in the set of comparables. Functions satisfying this property are called injective.

Take for instance those two examples:

We can use store Bool in Set (No matter how unpractical it might seem)

boolToInt : Bool -> Int
boolToInt bool =
    case bool of
        False -> 0
        True -> 1


empty boolToInt
|> insert True
|> member True
--> True

or Maybe String.

comparableKey : Maybe String -> (Int, String)
comparableKey maybe =
    case maybe of
        Nothing -> (0, "")
        Just str -> (1, str)


empty comparableKey
    |> insert (Just "foo")
    |> member (Just "foo")
--> True

Note that we give Int code to either constructor and in case of Nothing we default to "" (empty string). There is still a difference between Nothing and Just "" (Int value in the pair is different). In fact, you can "hardcode" any value as the second member of the pair in case of Nothing but empty string seems like a reasonable option for this case. Generally, this is how I would implement toComparable function for most of your custom data types. Have a look at the longest constructor, Define tuple where the first key is int (number of the constructor) and other are types within the constructor and you're good to go.

AnySet

type AnySet comparable t

= AnySet (AnyDict comparable t ())

Represents a set of unique values.

Be aware that AnySet stores a function internally. If you want to use (==) for comparing two AnySets use toSet function to convert them to regular Set first.

Build

empty : (a -> comparable) -> AnySet comparable a

Create an empty set.

** Note that it's important to make sure every key is turned to different comparable.** Otherwise keys would conflict and overwrite each other.

singleton : a -> (a -> comparable) -> AnySet comparable a

Create a set with one value.

** Note that it's important to make sure every key is turned to different comparable.** Otherwise keys would conflict and overwrite each other.

insert : a -> AnySet comparable a -> AnySet comparable a

Insert a value into a set.

remove : a -> AnySet comparable a -> AnySet comparable a

Remove a value from a set. If the value is not found, no changes are made.

removeAll : AnySet comparable a -> AnySet comparable a

Remove all entries from AnySet.

Useful when you need to create new empty AnySet using same comparable function for key type.

toggle : a -> AnySet comparable a -> AnySet comparable a

Toggle a value in a set. If it's not found, it's inserted, else it's removed.

Query

isEmpty : AnySet comparable a -> Bool

Determine if a set is empty.

member : a -> AnySet comparable a -> Bool

Determine if a value is in a set.

size : AnySet comparable a -> Int

Determine the number of elements in a set.

Combine

union : AnySet comparable a -> AnySet comparable a -> AnySet comparable a

Get the union of two sets. Keep all values.

intersect : AnySet comparable a -> AnySet comparable a -> AnySet comparable a

Get the intersection of two sets. Keeps values that appear in both sets.

diff : AnySet comparable a -> AnySet comparable a -> AnySet comparable a

Get the difference between the first set and the second. Keeps values that do not appear in the second set.

Lists

toList : AnySet comparable a -> List a

Convert a set into a list, sorted from lowest to highest.

fromList : (a -> comparable) -> List a -> AnySet comparable a

Convert a list into a set, removing any duplicates.

Transform

map :

(b -> comparable2)

-> (a -> b)

-> AnySet comparable a

-> AnySet comparable2 b

Map a function onto a set, creating a new set with no duplicates.

foldl : (a -> b -> b) -> b -> AnySet comparable a -> b

Fold over the values in a set, in order from highest to lowest.

foldr : (a -> b -> b) -> b -> AnySet comparable a -> b

Fold over the values in a set, in order from lowest to highest.

filter : (a -> Bool) -> AnySet comparable a -> AnySet comparable a

Only keep elements that pass the given test.

partition :

(a -> Bool)

-> AnySet comparable a

-> ( AnySet comparable a, AnySet comparable a )

Create two new sets. The first contains all the elements that passed the given test, and the second contains all the elements that did not.

Set

toSet : AnySet comparable a -> Set comparable

Convert AnySet to elm/core Set of comparable

Modules

Set.Any

turboMaCk/any-set/1.1.2