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

Janiczek · December 17, 2022, 11:05pm

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:

Creation: empty, singleton, fromList
Updates: anything that takes a Dict and returns a Dict. insert, map, union, etc.
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]

More specifically, the paths Just -> Nothing and Nothing -> Just don’t remove and insert elements respectively. Tracked in a GitHub issue. ↩︎
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. ↩︎
Not that this one in particular could be caught by an unit/property-based test suite: it only shows up with --optimize! ↩︎
I can’t promise PRs to elm/core being merged, of course ↩︎

lue-bird · December 17, 2022, 11:49pm

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 · December 17, 2022, 11:57pm

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 · December 18, 2022, 11:27am

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

github.com

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


      
              , singletonEmptyStringContainsVal
              )
          
          
import Dict exposing (Dict)
          import Expect exposing (Expectation)
          import Fuzz exposing (Fuzzer)
          import Set exposing (Set)
          import Test exposing (Test, fuzz)
          
          

          
type alias IDict comparable v dict b dictb result x =
              { x
                  | empty : dict
                  , singleton : comparable -> v -> dict
                  , insert : comparable -> v -> dict -> dict
                  , update : comparable -> (Maybe v -> Maybe v) -> dict -> dict
                  , remove : comparable -> dict -> dict
                  , isEmpty : dict -> Bool
                  , member : comparable -> dict -> Bool
                  , get : comparable -> dict -> Maybe v
                  , size : dict -> Int

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.

system · December 28, 2022, 11:27am

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
New Dict implementation for Elm, now done Show and Tell	2	1260	December 5, 2017
Faster `Dict.intersect` Show and Tell	1	419	January 27, 2023
Introducing assoc-list, a Dict substitute with custom keys Request Feedback	6	2077	January 19, 2019
Video: Writing a property-based testing library from scratch in Elm Show and Tell	2	529	June 1, 2021
Elm-benchmark 2.0.0 Show and Tell	1	2143	December 23, 2017

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

Related topics