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).

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 <roma@ro-che.info> wrote:

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