[Haskell-cafe] Need ideas how to model the lack of something

Patrick Redmond plredmond at gmail.com
Sun Dec 13 22:57:09 UTC 2015


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 <roma at 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 at haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > .
> >
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151213/cf983584/attachment.html>


More information about the Haskell-Cafe mailing list