Remove 'containers' from dependencies

[chshersh]

To remove containers from dependencies we need to rewrite two functions:

• unionWith
• fromSortedList

unionWith

Rewrite this to something more efficient:

1. Allocate new mutable vectors of length n+m.
2. Traverse input vectors simultaneously, copying elements in the right order. We should be able to take advantage of the fact that the elements are in a particular order. For regular sorted vectors it's very simple, for our cache-friendly order it can be tricky, but should be possible (I hope)
3. While doing this, count the actual amount of elements copied (it can be less than n+m due to conflicts). Shrink the mutable vector.
4. Freeze and return.

fromSortedList

Rewrite into the following way:

1. Allocate two mutable arrays of length n: one for original list and second one for result.
2. Rewrite current algorithm inside monad and change array in-place.
3. Freeze and return.

[C37H40O9]

What other functions, besides const, can be used with unionWith?

[int-index]

What other functions, besides const, can be used with unionWith?

For the Identity-parametrized version of unionWith,

unionWith :: (forall x. x -> x -> x) -> TMap -> TMap -> TMap

we may use

1. \x _ -> x to prefer elements from the first map (left-biased union)
2. \_ x -> x to prefer elements from the second map (right-biased union)

---

For the f-parametrized version of unionWith,

unionWith :: (forall x. f x -> f x -> f x) -> TypeRepMap f -> TypeRepMap f -> TypeRepMap f

When f is a GADT, we can match. For instance,

data F a where
  FInt :: Int -> F Int
  FBool :: Bool -> F Bool

With this, we can write more interesting combining functions:

combine (FInt a) (FInt b) = FInt (a + b)
combine (FBool a) (FBool b) = FBool (a || b)

---

We can make both versions more useful by providing the Typeable key to the caller:

unionWith :: (forall x. Typeable x => x -> x -> x) -> TMap -> TMap -> TMap
unionWith :: (forall x. Typeable x => f x -> f x -> f x) -> TypeRepMap f -> TypeRepMap f -> TypeRepMap f

This should be possible after #49

[ChrisPenner]

Closed by #93 , still needs a new version to be cut and uploaded to hackage though 😄