Elm-common-tests library + test results across the ecosystem

[Janiczek]

Hello all,

I just want to announce a small library that provides tests for your data structure implementations.

Right now it’s just Dict, but I’d like to extend it to other data structures.

Janiczek/elm-common-tests

---

What CommonTests.isDict will check and how it works underneath is comparison to elm/core Dict behaviour. We run the same actions on your Dict implementation and on the core Dict, and then check they arrived at the same results. (a.k.a. model based testing.)

The Dict API is conceptually separated into three categories:

1. Creation: empty, singleton, fromList
2. Updates: anything that takes a Dict and returns a Dict. insert, map, union, etc.
3. Queries: anything that returns a non-Dict. size, member, get, foldl, keys, toList, etc.

All of which are randomized and tested.

---

I’ve built on top of @miniBill’s work regarding categorizing the various Dict implementations, and went on to test them with this package. Here are the results:

Library	Module	Behaves like elm/core Dict?
edkelly303/elm-any-type-collections	Any.Dict
edkv/elm-generic-dict	GenericDict
matzko/elm-opaque-dict	OpaqueDict	update is buggy [1]
owanturist/elm-avl-dict	AVL.Dict
pzp1997/assoc-list	AssocList	Uses insertion order [2]
timo-weike/generic-collections	AutoDict
timo-weike/generic-collections	ManualDict
turboMaCk/any-dict	Dict.Any

---

Future work

The test results above seem to say, we’re doing pretty good!

But again, these test results check conformance to elm/core Dict behaviour. We should check it as well! Some unit tests do exist already, but we could write some property based tests to perhaps help uncover some more bugs. (Indeed there are some^[3].)

If anybody feels compelled to work on that Dict test suite with me (might be a nice intro to property based tests), send me a message somewhere! We can brainstorm the properties together and then implement them.^[4]

---

1. More specifically, the paths Just -> Nothing and Nothing -> Just don’t remove and insert elements respectively. Tracked in a GitHub issue. ↩︎

2. This is not necessarily a bug, but it’s a difference from elm/core Dict. It might be unexpected behaviour for those depending on Dicts being sorted by keys. ↩︎

3. Not that this one in particular could be caught by an unit/property-based test suite: it only shows up with --optimize! ↩︎

4. I can’t promise PRs to elm/core being merged, of course ↩︎

[lue-bird]

List of dicts looks pretty complete. A few other ones I know of (that might not fit the fuzzing format)

• escherlies/elm-ix-dict: IxDict → key derived from element
• joneshf/elm-tagged: Tagged.Dict → simple wrapper
• jjant/elm-dict: AllDict → basically just constructs one big function
• lue-bird/elm-keysset: KeySet (and KeysSet) → key derived from element, no stored function

[Janiczek]

Thank you! I have tried to implement the tests for some of those, but the tests do make some assumptions like being able to hardcode String keys and Int values, and having a toList. I believe I could get around both of these though

[rupert]

Interesting. I did something similar when writing tests for my Trie implementation. You can find my version of the Dict interface here:

elm-scotland/elm-tries/blob/1.0.1/tests/DictIface.elm#L29

I had a few more type variables that you, since I also generalized the comparable key type, and needed a load more to generalize operations over multiple Dicts (diff and merge) with the same key and datum types.

I also added another type variable x to make the Dict interface extensible, since I was taking the view that a Trie is a Dict extended with some other operations. https://github.com/elm-scotland/elm-tries/blob/1.0.1/tests/TrieIface.elm#L14

Its a fairly good way to proceed for testing I think, a bit overkill for applications. However with @jhbrown’s type hiding with continuations idea, its possible sometimes to drop many of the type variables. Operations over multiple data structures might not work with that idea though, unless they go through the interface rather than direct to the implementation. In the case of Dict that might be ok, since diff and merge can be implemented in terms of foldl and remove, but of course not all Dict implementation might want to do it that way.