There is no O(1) way of checking if a dict is nonempty

[imeckler]

You could do Dict.foldl (\_ _ _ -> True) False, but this is O(n).

[lachenmayer]

Looking at the source, it seems like isEmpty x = x == Dict.empty should always work.

The reason why the documentation states that "Dictionary equality with (==) is unreliable and should not be used" is that a Dict is a self-balancing red-black tree, and the distribution of red and black nodes depends on the insertion order.
That being said:

Dict.empty is defined as RBEmpty LBlack.
From a non-empty tree, the only way to arrive at an empty Dict is to remove an element.
Every remove operation performs blacken (here).
blacken will result in RBEmpty LBlack if the tree is empty (here).

I've only glanced at the code briefly, do let me know if you find a counter-example.
You're right though, Dict should have an isEmpty function, since List and String both contain one.

[lachenmayer]

Looking at the source, it seems like isEmpty x = x == Dict.empty should always work.

The reason why the documentation states that "Dictionary equality with (==) is unreliable and should not be used" is that a Dict is a self-balancing red-black tree, and the distribution of red and black nodes depends on the insertion order.
That being said:

Dict.empty is defined as RBEmpty LBlack.
From a non-empty tree, the only way to arrive at an empty Dict is to remove an element.
Every remove operation performs blacken (here).
blacken will result in RBEmpty LBlack if the tree is empty (here).

I've only glanced at the code briefly, do let me know if you find a counter-example.
You're right though, Dict should have an isEmpty function, since List and String both contain one.

[evancz]

I think the reason this function does not exist is because I wanted a uniform API across all the containers, but wasn't sure what that name should be / what all these libraries would look like. I think isEmpty is a nice way to go, so I think it's cool to add that as long as we do it in List, Dict, Set, and Array.

Can someone do a PR for this?

[evancz]

I think the reason this function does not exist is because I wanted a uniform API across all the containers, but wasn't sure what that name should be / what all these libraries would look like. I think isEmpty is a nice way to go, so I think it's cool to add that as long as we do it in List, Dict, Set, and Array.

Can someone do a PR for this?

[jvoigtlaender]

I think this issue can be closed.

[jvoigtlaender]

I think this issue can be closed.