I've posted before about the connection between some data structures and certain algebraic structures. The other day I noticed something odd, and which is probably not very useful, but may turn out to be interesting. An algebra for a monad can be considered a model of some algebraic structure. This means that we could use monads to describe data structures, as well as modeling computational contexts! Given an operator with the correct properties the monad could describe lists, sets, multi-sets, etc. Note that we could use the list monad to describe lists, so naively there may be a chicken and egg problem, but thats not really the point. The only really interesting thing here is that if we can describe the operator with the correct axioms we could describe a set structure that is not describable as a "polynomial type" using the sum and product from the theory of combinatorial species. This is because sets are non-regular species and are taken as the primitive species E.
Perhaps other structures could be described this way? I really like rigorous descriptions of data structures like this because they give deep meaning to things that are common-place for programmers, and a way to reason about and manipulate the structures in a less ad-hoc way. Probably this is either well known or not useful, but I have no real way of knowing which.
No comments:
Post a Comment