Best way to test if empty dict/set/etc.?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Jonathan Leivent
I noticed that a lot of the opaque data structures don't have an
is_empty predicate.  What is the best way to test if one of these is
empty?  Preferably an O(1) test, not size(X)==0 (unless that is O(1)),
because the structure might be quite large.

One way I thought of is to use fold on a function that just throws:

   is_empty(Dict) ->
     catch dict:fold(fun (_,_) -> throw(false) end, true, Dict).

But that is disturbingly ugly.  Is there a preferred way to do this?

Thanks.
Jonathan Leivent

Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Rapsey-2
Check the implementation of those data structures. There is always a
function that could tell you if it is empty or not. If size would not
be a O(1) call, it would probably say calc_size or something.
dict:size is O(1).

On Fri, May 31, 2013 at 12:17 AM, Jonathan Leivent <jleivent> wrote:

> I noticed that a lot of the opaque data structures don't have an is_empty
> predicate.  What is the best way to test if one of these is empty?
> Preferably an O(1) test, not size(X)==0 (unless that is O(1)), because the
> structure might be quite large.
>
> One way I thought of is to use fold on a function that just throws:
>
>   is_empty(Dict) ->
>     catch dict:fold(fun (_,_) -> throw(false) end, true, Dict).
>
> But that is disturbingly ugly.  Is there a preferred way to do this?
>
> Thanks.
> Jonathan Leivent
> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions

Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Vance Shipley-2
In reply to this post by Jonathan Leivent
On Thu, May 30, 2013 at 06:17:37PM -0400, Jonathan Leivent wrote:
}  I noticed that a lot of the opaque data structures don't have an
}  is_empty predicate.  What is the best way to test if one of these
}  is empty?  Preferably an O(1) test, not size(X)==0 (unless that is
}  O(1)), because the structure might be quite large.

With gb_trees and gb_sets size/1 is O(1).  These opaque data structures
happen to be tuples where the first element is the size:

     1> G1 = gb_trees:empty().  
     {0,nil}
     2> G2 = gb_trees:insert(foo, 1, G1).
     {1,{foo,1,nil,nil}}
     3> G3 = gb_trees:insert(bar, 2, G2).
     {2,{foo,1,{bar,2,nil,nil},nil}}
     4> gb_sets:from_list([1,2,3,4,5]).
     {5,{3,{2,{1,nil,nil},nil},{5,{4,nil,nil},nil}}}

I have in the past cheated by using clause heads which pattern match
based on the size of the data structures (e.g.):

     handle_call(Request, From, State) when element(1, State) > ?MAX ->

--
        -Vance

Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Kostis Sagonas-3
On 05/31/2013 09:03 AM, Vance Shipley wrote:
> On Thu, May 30, 2013 at 06:17:37PM -0400, Jonathan Leivent wrote:
> }  I noticed that a lot of the opaque data structures don't have an
> }  is_empty predicate.  What is the best way to test if one of these
> }  is empty?  Preferably an O(1) test, not size(X)==0 (unless that is
> }  O(1)), because the structure might be quite large.
>
> With gb_trees and gb_sets size/1 is O(1).  These opaque data structures
> happen to be tuples where the first element is the size:

I am afraid this statement (relying on the structure being a tuple)
breaks the opacity of the data structure.  So does your call to
element/2 below.

> I have in the past cheated by using clause heads which pattern match
> based on the size of the data structures (e.g.):
>
>       handle_call(Request, From, State) when element(1, State)>  ?MAX ->

So, this cannot possibly be the proper answer to Jonathan's question.

Since I've also stumbled across something analogous in the past, IMO the
proper solution is to extend the API of these opaque data structures
(these modules) by providing is_empty/1 functions for them.

I am sure the OTP folks would welcome a patch.

Kostis


Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Vance Shipley-2
On 05/31/2013 09:03 AM, Vance Shipley wrote:
}  With gb_trees and gb_sets size/1 is O(1).  These opaque data structures
}  happen to be tuples where the first element is the size:
   ^^^^^^^^^^^^

On Fri, May 31, 2013 at 09:25:48AM +0200, Kostis Sagonas wrote:
}  I am afraid this statement (relying on the structure being a tuple)
}  breaks the opacity of the data structure.  So does your call to
}  element/2 below.
 
Indeed, I made that point.  My answer was in the first sentence.  
The rest of my post was unecessary editorializing.

}  Since I've also stumbled across something analogous in the past,
}  IMO the proper solution is to extend the API of these opaque data
}  structures (these modules) by providing is_empty/1 functions for
}  them.
 
Only if they are bifs will it help with my (unsolicited) example.
Sometimes it's just too compelling to resist taking advantage
of knowing how the opaque data structures work.

--
        -Vance

Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Jonathan Leivent
In reply to this post by Kostis Sagonas-3
On 05/31/2013 03:25 AM, Kostis Sagonas wrote:
> ...
> Since I've also stumbled across something analogous in the past, IMO the
> proper solution is to extend the API of these opaque data structures
> (these modules) by providing is_empty/1 functions for them.

I feel better knowing that I wasn't just missing some obvious is_empty
substitute.  I also agree with your sentiment about keeping opaque
structures "opaque" - and the documentation implies a similar sentiment
("The representation of a dictionary|set is not defined.").

In an off-list post, it was pointed out that the structures that are
missing is_empty predicates (dict, orddict, sets, ordsets) are also
missing any API function to peek at or take an arbitrary element
(similar to queue:peek or queue:out) - which could be used as an
is_empty substitute (a more useful one at that).

Another problem with relying on either size(X) or the representation
itself is that dict and orddict (likewise set and ordset) have identical
APIs apparently to allow for substitution of one for the other with
minimal code churn (other than the == vs. =:= issue).  But their
representations (and the performance of size) differ.

> I am sure the OTP folks would welcome a patch.

Maybe that's the answer.  But, the lack of an is_empty predicate for
dict/sets has existed in Erlang for so long!?

-- Jonathan


Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Fred Hebert
In reply to this post by Jonathan Leivent
Most of these data structures have a 'new' or 'empty'  function call
that creates an empty/blank data structure.

I then just compare things like MyDict =:= dict:new() to know if it's
empty. I'm not aware of a case where this doesn't work, but it makes a
very subtle assumption that *might* break opacity: it assumes that the
data structure doesn't keep internal statistics or traces of content it
has seen before but is no longer there.

Regards,
Fred.

On 05/30, Jonathan Leivent wrote:

> I noticed that a lot of the opaque data structures don't have an
> is_empty predicate.  What is the best way to test if one of these is
> empty?  Preferably an O(1) test, not size(X)==0 (unless that is
> O(1)), because the structure might be quite large.
>
> One way I thought of is to use fold on a function that just throws:
>
>   is_empty(Dict) ->
>     catch dict:fold(fun (_,_) -> throw(false) end, true, Dict).
>
> But that is disturbingly ugly.  Is there a preferred way to do this?
>
> Thanks.
> Jonathan Leivent
> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions

Reply | Threaded
Open this post in threaded view
|

Best way to test if empty dict/set/etc.?

Jonathan Leivent
On 05/31/2013 11:19 AM, Fred Hebert wrote:
> Most of these data structures have a 'new' or 'empty'  function call
> that creates an empty/blank data structure.
>
> I then just compare things like MyDict =:= dict:new() to know if it's
> empty. I'm not aware of a case where this doesn't work, but it makes a
> very subtle assumption that *might* break opacity: it assumes that the
> data structure doesn't keep internal statistics or traces of content it
> has seen before but is no longer there.

I wasn't sure about whether the equality test would always work, either.
  Does the documentation ever mention whether or not equality tests on
opaque structures is expected to work?

However, for sets/ordsets, maybe this is both O(1) and opaque:

   is_empty(S) -> sets:is_subset(S, sets:new()).

-- Jonathan