Can I overload the count function in Clojure

Question

In Python if I want to customize the way to define how to find the size of an object I define a __len__ method for the class, which alters the behavior of the len function. Is there any way to do this in Clojure with the count function? If so, how?

Answer 1

By the way, you cannot override that function neither with with-redefs nor any related functionality. There is a hidden trick here: if you check the source code of the count function, you'll see an interesting inline attribute in its metadata:

(defn count
  "Returns the number of items in the collection. (count nil) returns
  0.  Also works on strings, arrays, and Java Collections and Maps"
  {
   :inline (fn  [x] `(. clojure.lang.RT (count ~x)))
   :added "1.0"}
  [coll] (clojure.lang.RT/count coll))

This attribute means the function's code will be inserted as-is into the resulting bytecode without calling the original function. Most of the general core functions have such attribute. So that's why you cannot override count, get, int, nth and so forth.

Answer 2

What does count mean for a graph?

What should count return for a graph? I can think of two equally obvious options -- the number of nodes in the graph or the number of edges. So perhaps count isn't very intuitive for graph.

Implementing Counted

Nevertheless, you certainly can define your own counted data structures in Clojure. The key is to implement the clojure.lang.Counted interface.

Now, if represent a graph via the following deftype:

(deftype NodeToEdgeGraph [node->neighbors]
  ...)

we can make it counted:

(deftype NodeToEdgeGraph [node->neighbors]
  clojure.lang.Counted
  (count [this]
    (count node->neighbors))
  ...)

This is if we are representing a graph as a map that maps each node to its set of "neighbors" (where a node is considered a "neighbor" if, and only if, there is an edge between the two), and we want count to return the number of nodes.

Alternatively, we can represent a graph as a set of pairs (either ordered, in the case of a directed graph; or unordered, in the case of an undirected graph). In this case, we have:

(deftype EdgeGraph [edges]
  ...)

And we can have count return the number of edges in the graph:

(deftype EdgeGraph [edges]
  clojure.lang.Counted
  (count [this]
    (count edges))
  ...)

So far, we have been using count on the underlying structure to implement count for the graph. This works because the underlying structure conveniently has the same count as the way we are counting each respective graph representation. However, there's no reason we couldn't use either representation with either way of counting. Also, there are other ways of representing graphs that might not align so nicely with the way we want to count. In these cases, we can always maintain our own internal count:

(deftype ???Graph [cnt ???]
  clojure.lang.Counted
  (count [this]
    cnt)
  ...)

Here, we rely on the implementation of the graph operations to maintain cnt appropriately.

Built-in or Custom Types?

Others have suggested using the built-in datastructures only to represent your graphs. Indeed, if you take a look at NodeGraph and EdgeGraph, you can see that count simply delegates to the underlying structure. So for these representations (and definitions of count), you could simply eliminate the deftype and implement your graph operations directly over maps / sets. However, let's take a look at some advantages to encapsulating graphs in a custom type:

• Ease of implementing alternative representations. With custom types, you can have an unlimited number of graph representations. All you need to do is define some protocols and define graph operations in terms of those protocols. While you can also extend protocols to built-in types, you are limited to only one representation / implementaton per built-in type. This might or might not be sufficient for you.
• Maintenance of internal invariants. With custom types, you have better control over the internal structure. That is, you can implement protocols / interfaces in a way that maintains any necessary internal invariants. For example, if you are implementing undirected graphs, you can implement NodeGraph in a way that ensures adding an edge from node A to node B also adds an edge from node B to node A. Likewise with removing an edge. With built-in types, these invariants can only be maintained by the graph functions you implement. The Clojure core functions will not maintain these invariants for you, because they know nothing about them. So if you hand your "graphs" (over built-in types) off to some function that calls non-graph functions on them, you have no assurance that you will get a valid graph back. On the other have, custom types only allow the operations you implement, and will perform them the way you implement them. As long as you take care that all the operations you implement maintain the proper invariants, you can rest assured that these invariants will always be maintained.

On the other hand, sometimes it is appropriate to simply use the built-in types. For instance, if your application only makes light use of graph operations, it might be more convenient to simply use built-in types. On the other hand, if your application is heavily graph-oriented and makes a lot of graph operations, it's probably better in the long run to implement a custom type.

Of course, you are not forced to choose one over the other. With protocols, you can implement graph operations for both built-in types as well as custom types. That way, you can choose between "quick and dirty" and "heavy but robust" depending on your application. Here "heavy" just means it might take a little more work to use graphs with functions implemented over Clojure collection interfaces. In other words, you might need to convert graphs to other types in some cases. This depends heavily on how much effort you put into implementing these interfaces for your custom graph types (and to the extent they make sense for graphs).

Answer 3

Your comment says you are dealing with graphs. Taking on board the good advice to use the standard data structures, let's consider how to represent them.

You would normally represent a graph as a map Node -> Collection of Node. For example,

(def graph {:a [:b], :b [:a :c]})

Then

(count graph)                 
=> 2

However, if you make sure that every node has a map entry, even the ones that have no afferent arcs, then all you have to do is count the graph's map. A function add the empty entries is ...

(defn add-empties [gm]
  (if (empty? gm)
    gm
    (let [EMPTY (-> gm first val empty)
          missing (->> gm
                     vals
                     (apply concat)
                     (remove gm))]
      (reduce (fn [acc x] (assoc acc x EMPTY)) gm missing))))

For example,

(add-empties graph)
=> {:a [:b], :b [:a :c], :c []}

and

(count(add-empties graph))
=> 3

Answer 4

This is a reasonable question to ask when you are moving from one paradigm to another i.e. OO to functional, but likely is not an issue. In languages like Clojure, you will normally start by working out how to represent your data in one of the existing data structures (Collections) rather than define a new structure to represent your data. The idea is to have only a few different data structures with a large number of well defined and understood functions which operate on those structures in an efficient and reliable manner. As a consequence, once you have decided on how to represent your graphs, you will likely find that doing something like counting the number of vertices is trivial - you will probably just need to use reduce with a very simple function that in turn uses other core functions, such as the existing count(). A key to becoming proficient in Clojure is in learning what the core functions are and what they do.

In an OO language, you encapsulate your data and hide it inside an object. This means you now need to define the methods to operate on the data inside that object. To support polymorphism, you will frequently do things like add an object specific size or length method. In Clojure, the underlying data structure is not hidden and is frequently built on one of the standard collection types, so you don't need tow rite a size/length function, you can use the standard count function. When the standard collections are not suitable and you need more, then you tend to look at things like protocols, where you can define your own specialised functions e.g. size.

In your case, a protocol or record is unlikely to be necessary - representing graphs is pretty much a natural fit for the standard collections and I woldn't be at all surprised if you could re-implement what you did in C or C++ with Clojure in a lot fewer lines and likely in a much more declarative and cleaner manner. Start by looking at how the standard Clojure collection types could be used to represent your graphs. Think about how you want to operate on the graphs and whether you are best representing the graph as nodes or verticies and then look at how you would answer questions like 'How many verticies are in this graph?" and see how you would get that answer just using the available built-in functions.

You do need to think about things differently when you move to a functional paradigm. There will be a point you get to that is a real "Aha" moment as that penny drops. Once it does, you will likely be very surprised how nice it is, but until that moment, you will likely experience a bit of frustration and hair pulling. The battle is worth it as you will likely find even your old imparative programming skills benefit and when you have to go back to C/C++ or Python, your code is even clearer and more concise. Try to avoid the temptation to reproduce what you did in C/Python in Clojure. instead, focus on the outcome you want to achieve and see how the supplied facilities of the language will help you do that.

Answer 5

sorry, not for existing collection types you don't control.

You can define your own count that is aware of your needs and use that in your code, though unfortunately clojure does not use a universal protocol for counting so there is nowhere for you to attach that will extend count on an existing collection.

If counted where a protocol rather than an interface this would be easier for you, though it long predates protocols in the evolution of the language.

If you are making your own collection type then you can of course implement count anyway you want.