Need ideas how to model the lack of something

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Need ideas how to model the lack of something

Martin Drautzburg
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Sumit Sahrawat, Maths & Computing,
 IIT (BHU)
You can implement a structure which hides a max length and a length inside it, whose record accessors are not exported.

Also, rather than thinking of insert and remove as operations *inside* the structure, think of them separately. Define just the data structure first, and then define the operations afterwards. This separates the interface and implementation, allowing you to change the structure without changing the API.

On 14 December 2015 at 01:45, martin <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



--
Sumit Sahrawat,

Junior - Mathematics and Computing,
Indian Institute of Technology - BHU,
Varanasi, India

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Roman Cheplyaka-2
In reply to this post by Martin Drautzburg
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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> .
>


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Patrick Redmond
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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> .
>



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Kim-Ee Yeoh
Administrator
In reply to this post by Martin Drautzburg

On Mon, Dec 14, 2015 at 3:15 AM, martin <[hidden email]> wrote:
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.

And the reason you're stuck implementing anything sensible on top of this is because you've written an OOP-style specification of a data structure.

You might want to review how Haskell declares data types.

-- Kim-Ee

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Joachim Durchholz
Am 14.12.2015 um 01:28 schrieb Kim-Ee Yeoh:

> On Mon, Dec 14, 2015 at 3:15 AM, martin <[hidden email]> wrote:
>
>> 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.
>>
>
> And the reason you're stuck implementing anything sensible on top of this
> is because you've written an OOP-style specification of a data structure.

Mmm... this is the second time this has been raised.
What's the problem with OOP style? Something specific with Haskell,
something about OOP in general, something else?

Regards,
Jo
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Martin Drautzburg
In reply to this post by Patrick Redmond
Am 12/13/2015 um 11:57 PM schrieb Patrick Redmond:
> 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."

This way I'd have to be explicit about what C really is, don't I? Data.Set certainly has a very explicit data structure
under the hood. I was hoping to express the idea of "something that can be inserted to and removed from" without
specifying how the data is actually stored.

But maybe that's a bad point to start from. At least this is where the trouble started when I tried to implement
something on top of it. I just didn't have enough "flesh" to work with.




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Patrick Redmond
Replies inline.

On Sunday, December 13, 2015, martin <[hidden email]> wrote:
Am 12/13/2015 um 11:57 PM schrieb Patrick Redmond:
> 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."

This way I'd have to be explicit about what C really is, don't I? Data.Set certainly has a very explicit data structure
under the hood. I was hoping to express the idea of "something that can be inserted to and removed from" without
specifying how the data is actually stored.

Use a typeclass. 

But maybe that's a bad point to start from. At least this is where the trouble started when I tried to implement
something on top of it. I just didn't have enough "flesh" to work with.

Yes, you will have to write a concrete implementation anyway, so start with that. Make an explicit data structure, with concretely typed functions to manipulate it.

When you have two of these explicit implementations, make a typeclass and provide two instances - one which delegates to each of the implementations.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Thomas Koster
In reply to this post by Joachim Durchholz
On Mon, Dec 14, 2015 at 3:15 AM, martin <[hidden email]> wrote:
> 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.

Am 14.12.2015 um 01:28 schrieb Kim-Ee Yeoh:
> And the reason you're stuck implementing anything sensible on top of this
> is because you've written an OOP-style specification of a data structure.

On 14 December 2015 at 17:28, Joachim Durchholz <[hidden email]> wrote:
> Mmm... this is the second time this has been raised.
> What's the problem with OOP style? Something specific with Haskell,
> something about OOP in general, something else?

Nothing nefarious: Object-oriented style in Haskell is wordy and
unnatural for no other reason than that Haskell is a functional
programming language and not an object-oriented language. Haskell is
not a multi-paradigm language like Scala.

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Joachim Durchholz
Am 15.12.2015 um 01:40 schrieb Thomas Koster:

> On Mon, Dec 14, 2015 at 3:15 AM, martin <[hidden email]> wrote:
>> 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.
>
> Am 14.12.2015 um 01:28 schrieb Kim-Ee Yeoh:
>> And the reason you're stuck implementing anything sensible on top of this
>> is because you've written an OOP-style specification of a data structure.
>
> On 14 December 2015 at 17:28, Joachim Durchholz <[hidden email]> wrote:
>> Mmm... this is the second time this has been raised.
>> What's the problem with OOP style? Something specific with Haskell,
>> something about OOP in general, something else?
>
> Nothing nefarious: Object-oriented style in Haskell is wordy and
> unnatural for no other reason than that Haskell is a functional
> programming language and not an object-oriented language.

I see Kim-Ee Yeoh stating that Martin is stuck without a way forward due
to using OO style, which seems more serious than just "wordy and unnatural".
Or am I misreading his words, and that "OO-style" reference was just
descriptive rather than presenting the base cause of Martin's problems?

Regards,
Jo

P.S.: I'm not trying to criticize anything, just trying to understand
what the issue is.
Is there a webpage like "Haskell for OO-warped minds" that explains how
to transition one's idioms? I have a good grasp of Haskell in-the-small,
but I haven't had an opportunity to learn the larger-scale issues, so
I'm probably just being dense and would like to change that.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Carlo Hamalainen-2
On 15/12/2015 15:33, Joachim Durchholz wrote:
> I see Kim-Ee Yeoh stating that Martin is stuck without a way forward
> due to using OO style, which seems more serious than just "wordy and
> unnatural".
> Or am I misreading his words, and that "OO-style" reference was just
> descriptive rather than presenting the base cause of Martin's problems?

The OP originally wrote an insert function with this type:

insert :: a -> Maybe (C a)

which sort of looks like an insert function from an OO language where
the self object is implicit. In functional style it should be

insert :: a -> C a -> Maybe (C a)

Another way: it's impossible to implement

insert :: a -> Maybe (C a)
insert a = ???

because there is no 'C a' to modify.

--
Carlo Hamalainen
http://carlo-hamalainen.net


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Darren Grant-2

'insert' is a record accessor, so there is an implied (C a).

Cheers,
D

On Dec 15, 2015 00:02, "Carlo Hamalainen" <[hidden email]> wrote:
On 15/12/2015 15:33, Joachim Durchholz wrote:
> I see Kim-Ee Yeoh stating that Martin is stuck without a way forward
> due to using OO style, which seems more serious than just "wordy and
> unnatural".
> Or am I misreading his words, and that "OO-style" reference was just
> descriptive rather than presenting the base cause of Martin's problems?

The OP originally wrote an insert function with this type:

insert :: a -> Maybe (C a)

which sort of looks like an insert function from an OO language where
the self object is implicit. In functional style it should be

insert :: a -> C a -> Maybe (C a)

Another way: it's impossible to implement

insert :: a -> Maybe (C a)
insert a = ???

because there is no 'C a' to modify.

--
Carlo Hamalainen
http://carlo-hamalainen.net


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Martin Drautzburg
In reply to this post by Joachim Durchholz
Am 12/15/2015 um 08:33 AM schrieb Joachim Durchholz:

>> On 14 December 2015 at 17:28, Joachim Durchholz <[hidden email]> wrote:
>>> Mmm... this is the second time this has been raised.
>>> What's the problem with OOP style? Something specific with Haskell,
>>> something about OOP in general, something else?

>
> P.S.: I'm not trying to criticize anything, just trying to understand what the issue is.
> Is there a webpage like "Haskell for OO-warped minds" that explains how to transition one's idioms? I have a good grasp
> of Haskell in-the-small, but I haven't had an opportunity to learn the larger-scale issues, so I'm probably just being
> dense and would like to change that.

I'd be interested in that "Haskell for OO-warped minds" too.

As for my specific question, here's what I believe I've learned.

Abstract classes or interfaces are commonplace in the OO world. But even there you have to provide a concrete
implementation eventually. While you can program in a similar style in haskell by using typeclasses, haskellers tend to
start with a concrete implementation and then use typeclasses to express commonalities of concrete implementations.

While some data types, particularly those which wrap functions (the simplest of which is probably the state monad), look
like they are providing an abstract interface to a computation, they are actually concrete things. Or take the List data
type: it is not just something you can prepend an element to, express an empty list and split it into head and tail, but
really a concrete thing, which allows implementing these operations. You could implement these three operations (:,
head, tail) and the constant [] on top of other data structures, but this would not make them a List.

Some time ago I asked the question, whether you have a choice between using a newtype/data or a typeclass and if so
which is the preferred approach. The answer was yes, these two concepts can occasionally replace each other and "short
answer: use data". This was one reason why I didn't even try to use a typeclass in my problem here. Now I believe that I
misread "short answer: use data" as using the "data" keyword. What it really meant is: "be concrete".

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Thomas Koster
In reply to this post by Joachim Durchholz
On Mon, Dec 14, 2015 at 3:15 AM, martin <[hidden email]> wrote:
> 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.

Am 14.12.2015 um 01:28 schrieb Kim-Ee Yeoh:
> And the reason you're stuck implementing anything sensible on top of this
> is because you've written an OOP-style specification of a data structure.

On 14 December 2015 at 17:28, Joachim Durchholz <[hidden email]> wrote:
> Mmm... this is the second time this has been raised.
> What's the problem with OOP style? Something specific with Haskell,
> something about OOP in general, something else?

On 15 December 2015 at 11:40, Thomas Koster <[hidden email]> wrote:
> Nothing nefarious: Object-oriented style in Haskell is wordy and
> unnatural for no other reason than that Haskell is a functional
> programming language and not an object-oriented language. Haskell is
> not a multi-paradigm language like Scala.

On 15/12/2015 15:33, Joachim Durchholz wrote:
> I see Kim-Ee Yeoh stating that Martin is stuck without a way forward
> due to using OO style, which seems more serious than just "wordy and
> unnatural".
> Or am I misreading his words, and that "OO-style" reference was just
> descriptive rather than presenting the base cause of Martin's problems?

Sorry, my answer was specifically to your question: "What's the
problem with OOP style [in Haskell]?" It doesn't help Martin.

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Need ideas how to model the lack of something

Tillmann Rendel-6
In reply to this post by Martin Drautzburg
Hi,

martin wrote:
> 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.

Looks reasonable to me. What do you want to implement on top of it?

For starters, here are three values of this type:

stack ::

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe