I think you're off to a good start with this insert signature:
insert :: a -> C a -> Maybe (C a)
"Insert element `a` into structure `C a` and return a new structure if the
insertion was successful."
It looks like you're following the lead of some common haskell data
structures (eg, containers:Data.Set.insert
http://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Set.html#g:5
).
What does this lack?
---
If you want the container to be implicit in the arguments (albeit, explicit
in the return value), then your second formulation works:
data C a = C {
insert :: a -> Maybe (C a),
remove :: Maybe (a, C a)
}
To implement this you could make a constructor that has an internal data
structure, and then constructs a `C` by closing over the internal
structure. In this way, your `C` is really just an API and you'll have an
internal implementation of insert & remove that take the internal structure
as an explicit argument. That's a bunch of extra work for a minor
convenience, so I'd recommend starting with the version that takes an
explicit argument (first in this email).
On Sun, Dec 13, 2015 at 1:36 PM, Roman Cheplyaka
You may want to specify:
1. whether you want the symmetry to be present in the API, the internal representation, or both 2. what exactly your C type is lacking. It looks like a valid model of what you described, even if somewhat object-oriented one.
You may also be interested in combinatorial species. That theory specifically considers functorial shapes containing a specific number of holes and/or elements. I think Brent Yorgey has some articles and/or code relating species to Haskell.
On 12/13/2015 10:15 PM, martin wrote:
Hello all,
here is a problem where I did not manage to find a suitable abstraction. The main idea goes like this:
a List (and many other containers) can be seen as something containing "stuff". There is a function (:) that unconditionally adds an element to the container and returns a new container
Now suppose the container has the possiblility to refuse having another element added to it, e.g. because it has only limited "space". In that case the corresponding function would have a signature of insert :: a -> C a -> Maybe (C a). If an item can successfully be added, then the returned container will be less space avaiable.
I'd like stuff and space to be symmetrical (maybe there lies the first flaw, because I can enumerate the elements, but I cannot enumerate the space). A symmetry like electrones and holes.
I started like this
data C a = C { insert :: a -> Maybe (C a), remove :: Maybe (a, C a) }
but I could not implement anything sensible on top of this.
I'd be happy to hear any comments on this, including loud thinking and random ramblings.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe .
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe