Heterogeneous Lists

harry

28 May 2013 28 May '13

7:36 a.m.

Every OO language which supports generics allows a declaration such as List<Show> alist, where Show is an interface. Any type implementing Show can be put in alist, and any Show operation can be performed on the alist's members. No casts, wrappers, or other special types and plumbing are needed. Why isn't it possible to do this directly in Haskell?

Show replies by date

Magnus Therning

28 May 28 May

8:04 a.m.

On Tue, May 28, 2013 at 9:36 AM, harry wrote:

...

Every OO language which supports generics allows a declaration such as List<Show> alist, where Show is an interface. Any type implementing Show can be put in alist, and any Show operation can be performed on the alist's members. No casts, wrappers, or other special types and plumbing are needed.

Why isn't it possible to do this directly in Haskell?

Just to make sure... I guess you've already read http://www.haskell.org/haskellwiki/Heterogenous_collections right? /M -- Magnus Therning OpenPGP: 0xAB4DFBA4 email: magnus@therning.org jabber: magnus@therning.org twitter: magthe http://therning.org/magnus

Mike Ledger

10:31 a.m.

With ConstraintKinds, ExistentialQuantification, StandaloneDeriving and FlexibleInstances, this works:

...

...
...
data Some f = forall a. f a => Some a deriving instance Show (Some Show) show ([Some [0..10], Some (), Some Nothing, Some "asdf"] :: [Some Show]) "[Some [0,1,2,3,4,5,6,7,8,9,10],Some (),Some Nothing,Some \"asdf\"]"

On Tue, May 28, 2013 at 6:04 PM, Magnus Therning wrote:

...

On Tue, May 28, 2013 at 9:36 AM, harry wrote:

...
Every OO language which supports generics allows a declaration such as List<Show> alist, where Show is an interface. Any type implementing Show can be put in alist, and any Show operation can be performed on the alist's members. No casts, wrappers, or other special types and plumbing are needed.

Why isn't it possible to do this directly in Haskell?

Just to make sure... I guess you've already read http://www.haskell.org/haskellwiki/Heterogenous_collections right?

/M

-- Magnus Therning OpenPGP: 0xAB4DFBA4 email: magnus@therning.org jabber: magnus@therning.org twitter: magthe http://therning.org/magnus

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

harry

1:41 p.m.

Magnus Therning writes:

...

Just to make sure... I guess you've already read http://www.haskell.org/haskellwiki/Heterogenous_collections right?

Yes, I'm asking why Haskell doesn't allow this directly. I'm already using a workaround.

Brent Yorgey

1:50 p.m.

On Tue, May 28, 2013 at 01:41:55PM +0000, harry wrote:

...

Magnus Therning writes:

...
Just to make sure... I guess you've already read http://www.haskell.org/haskellwiki/Heterogenous_collections right?

Yes, I'm asking why Haskell doesn't allow this directly. I'm already using a workaround.

This is probably not a good idea. Instead, why don't you explain to us what you are trying to accomplish, and perhaps we can suggest a better way that does not require heterogeneous lists? -Brent

Mateusz Kowalczyk

1:50 p.m.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 28/05/13 14:41, harry wrote:

...

Magnus Therning writes:

...
Just to make sure... I guess you've already read http://www.haskell.org/haskellwiki/Heterogenous_collections right?

Yes, I'm asking why Haskell doesn't allow this directly. I'm already using a workaround.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Simply because Haskell's lists are a homogeneous data structure by nature. Consider: data List a = Nil | Cons a List It doesn't do heterogeneous lists by default because it was never meant to. I don't see where the disappointment comes from. It's the same in majority of typed languages. I don't see why you would expect to be able to make have a heterogeneous list because you can do it with interfaces in some other language. To begin with, typeclasses are not interfaces. Just so you know, you're probably doing it wrong if you're using `a workaround' to have a heterogeneous list. - -- Mateusz K. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.19 (GNU/Linux) iQIcBAEBAgAGBQJRpLYdAAoJEM1mucMq2pqXzGIQAK4YapHZdtTdfUbFCZc90MF6 KbE5NmXswaKfgf+OU5Cs7fGG0dZahmeAEhFpZBVEUlnKXGT9hGiFQj7cm/4hK881 kGHWq5WlqGuzdnD9iTEG+IcLsqXQA1ZArObOFB2VL7dSzQHPhKHpnIshzID4osN6 QBo7fYvQ9H2Ng0sf5Cuo88ck0VGxKxvDPG8cg/6SpjH1EdPg3LlPiEYnZJoKbDnM G82IFctzANYuFbIXclD/DK6dlv/6newAR1Q5zXCD9ZQJv7y2z0mhA4gjbb4fUNGb 3y0wkj+srC6skC/1g871cQRC6u0aRSdGKYZIs2SwlKKFwUGftLlnq/KQukYuYuWi HB8H+jm3/tQDZEius9umVlQN6c56pglh+gY8p9bnAqOsw8gfSeM5qlEggSCs5wIh BpQBEOANMUKZRiRGrmx2FEl8IwdRcf5LUStFiI0EpabZDTpRQVRuG3K/LZpZS0em UPOfP/X0jDZAhxb/iiR91F+DnpzWrMkteP4mqQ9GpqY2RmXY3jw3B/1uC41mX17v NWfUULp4rRtcMPn2OvXYn28r3sCCO5D78rcGk2uv7Mmnb2HFq99XiaQG3Q7pzaB0 O4wePLuwFPZqefFuIl8WM68qjYFBeUJkOR3ik3Q1V2SftLMy8kFnDdz80DykOODw 2Sw+0P1Dyxk45ENu+Fry =rpvr -----END PGP SIGNATURE-----

Brent Yorgey

1:49 p.m.

On Tue, May 28, 2013 at 07:36:13AM +0000, harry wrote:

...

Every OO language which supports generics allows a declaration such as List<Show> alist, where Show is an interface. Any type implementing Show can be put in alist, and any Show operation can be performed on the alist's members. No casts, wrappers, or other special types and plumbing are needed.

Why isn't it possible to do this directly in Haskell?

I am not sure what you mean by asking "why". If you are simply implying that this is stupid and Haskell *should* be able to do this directly, then I would say that you need to spend more time learning to think through the lens of the abstractions Haskell *does* give you, and stop trying to think through an OOP lens. I can count on one finger the number of times I have wanted a heterogeneous collection like this --- it was a long time ago, and I was wrong. On the other hand, if you sincerely want to know why, it is simply that this kind of feature does not fit nicely within the space of the design decisions that were made when creating Haskell, for example: (1) All the elements of a list must have the same type. (2) A type class cannot be used as a type. (3) Haskell has no subtyping. And there are good reasons behind these decisions as well. For example, subtyping makes type inference nigh impossible. -Brent

harry

2 p.m.

Brent Yorgey writes:

...

On the other hand, if you sincerely want to know why, it is simply that this kind of feature does not fit nicely within the space of the design decisions that were made when creating Haskell, for example: (1) All the elements of a list must have the same type. (2) A type class cannot be used as a type. (3) Haskell has no subtyping. And there are good reasons behind these decisions as well. For example, subtyping makes type inference nigh impossible.

Yes, (2) is what I don't understand. I recently ran into this with a GUI application, where I needed to process a list of widgets that were members of the same typeclass, but I had to wrap them all because they were different types. So so rephrase my question, why can't type classes be used as a type? Is this an implementation issues, or is there a semantic problem with this? Creating an existential type and packing all the values seems like busy work which shouldn't be necessary, or at least something that the compiler should be doing for me.

Mateusz Kowalczyk

2:28 p.m.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 28/05/13 15:00, harry wrote:

...

Brent Yorgey writes:

...
On the other hand, if you sincerely want to know why, it is simply that this kind of feature does not fit nicely within the space of the design decisions that were made when creating Haskell, for example: (1) All the elements of a list must have the same type. (2) A type class cannot be used as a type. (3) Haskell has no subtyping. And there are good reasons behind these decisions as well. For example, subtyping makes type inference nigh impossible.

Yes, (2) is what I don't understand. I recently ran into this with a GUI application, where I needed to process a list of widgets that were members of the same typeclass, but I had to wrap them all because they were different types.

So so rephrase my question, why can't type classes be used as a type? Is this an implementation issues, or is there a semantic problem with this? Type classes can't be used as types because they are not types. It's just that simple. To achieve what you want you actually create a new type (with `data') and put a type class constraint on the types it accepts. We can then use that type for our collection.

...

Creating an existential type and packing all the values seems like busy work which shouldn't be necessary, or at least something that the compiler should be doing for me. Yes, it is in fact busy work and yes, it could probably be done for you by the compiler. I imagine the reason it isn't is simply because forcing heterogeneous collections where only homogeneous ones were intended is usually a sign of the fact that you are doing it wrong and usually there's a better solution. Putting in direct support for it in the compiler would just make the compiler more complex and effectively encourage bad programming. It's just not something that comes up often enough to warrant a compiler extension.

- -- Mateusz K. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.19 (GNU/Linux) iQIcBAEBAgAGBQJRpL8cAAoJEM1mucMq2pqXFiMP/jaK3i6sW+R7aoKqp3UwjgRM SSdD1zEpcPtMRwoucpW0GDk+gjtIvqTcrpo5THD6w59G1Pwvm/8G+852xHfdPVUs NmpYtz1an4mGeJZmz7One0UbX+Bh7mz83E/fLkUJ4FrBXF7q9XFVPwhkRb+5F4Yd BovYSPwmGsUslXc785UE2J3G/nPW61jtw+w0k+SRuD7wJd/0JQO54rp3PQt5udO+ GF022pOqB+IWxIAqaZ+CEPiEotrGLe6tJzvE8J0vgkcgTpGrumRyJRz/yRc0foXi FuOgRPr1dgaajanMOcaapWkf0aE1RxfIR0iDWgcQZYpPlU6nTz9XhQZ0216udUHr px5PnpFSFmVHdtWxdMEjY5zBlV51TwUZm01kQQ+mBO4cqsHJNEuSFSpcOoMddH/X P/s/dTUtWp01cjSCkxahDCltvuDNmmOGT5kfmZ22YdOGTdbsjCVY/tHM6WFDb8OB 6j2a8YovorskWx5Mpw+3GS5VOn7KgDvKXoRvCQL8KvRLBlekVGHjXRz9kQRTGQwW KV9WcNQU46mw1tyLJaD5zbKko8HvGUc4I8DdbtMLnJ3KQuiTQIp677QyoGFZcE1C USyvG3E+lsXU9fBw3GpxPfSQLM0t3waL4tMdKXt0urIidSJdpIPNJrS+SICxF62Z FpJ3V8/U7lnjo0z6/Iy0 =yKxA -----END PGP SIGNATURE-----

harry

2:47 p.m.

Mateusz Kowalczyk writes:

...

Yes, it is in fact busy work and yes, it could probably be done for you by the compiler. I imagine the reason it isn't is simply because forcing heterogeneous collections where only homogeneous ones were intended is usually a sign of the fact that you are doing it wrong and usually there's a better solution. Putting in direct support for it in the compiler would just make the compiler more complex and effectively encourage bad programming. It's just not something that comes up often enough to warrant a compiler extension.

Several people have implied that wanting to do this suggests that I'm doing something wrong. I can't find the code where I did this, but is there a general anti-pattern here?

Brandon Allbery

2:30 p.m.

On Tue, May 28, 2013 at 10:00 AM, harry wrote:

...

So so rephrase my question, why can't type classes be used as a type? Is this an implementation issues, or is there a semantic problem with this? Creating an existential type and packing all the values seems like busy work which shouldn't be necessary, or at least something that the compiler should be doing for me.

Haskell is strongly typed; if you want to throw out all the type information, you must tell if explicitly (which is what the existential does). This comes at a price, of course: once you've thrown out the type information, you can't get it back. -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

Ertugrul Söylemez

5:08 p.m.

harry wrote:

...

...
(2) A type class cannot be used as a type.

Yes, (2) is what I don't understand.

The question can be generalized: What is the difference between Haskell's type classes and OOP interfaces? The main difference is that type class instances are type-bound, while interfaces are value-bound. That's why you can't encode the Monoid pattern as a type class, but not as an interface. You /can/ think of type classes as types, but not the way you do it for OOP interfaces or base classes. A type class is a separate type that encodes values of the type it is bound to: data Monoid a = Monoid { mempty :: a, mappend :: a -> a -> a } If you would store a list of monoids [Monoid X], you would store a list of identity/addition laws for the same type X, not a list of values of type X. This is probably not what you want.

...

I recently ran into this with a GUI application, where I needed to process a list of widgets that were members of the same typeclass, but I had to wrap them all because they were different types.

Your misconception is likely that you need to /store/ widgets, because you think in terms of memory. What you really need is /definitions/ of widgets, which can very well have different types. Then you can combine them using the usual monadic or applicative interface.

...

So so rephrase my question, why can't type classes be used as a type? Is this an implementation issues, or is there a semantic problem with this? Creating an existential type and packing all the values seems like busy work which shouldn't be necessary, or at least something that the compiler should be doing for me.

It is necessary. Haskell's type system is simply not the same as C#'s type system. As pointed out a number of times we don't have subtyping. Subtyping lets you treat different types like they were the same. Haskell simply doesn't follow this philosophy and gives us enough type system power to encode proper abstractions instead of the catch-all "everything is an object" approach. This is a benefit, but it takes some time to get used to it, and usually you see the value only /after/ that time. Greets, Ertugrul -- Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad.

Giacomo Tesio

14 Aug 14 Aug

1:21 p.m.

...

...
I recently ran into this with a GUI application, where I needed to process a list of widgets that were members of the same typeclass, but I had to wrap them all because they were different types.

Your misconception is likely that you need to /store/ widgets, because you think in terms of memory. What you really need is /definitions/ of widgets, which can very well have different types. Then you can combine them using the usual monadic or applicative interface.

Ertugrul, can you please expand on this? Giacomo

Frerich Raabe

28 May 28 May

5:07 p.m.

On May 28, 2013, at 12:36 AM, harry wrote:

...

Every OO language which supports generics allows a declaration such as List<Show> alist, where Show is an interface. Any type implementing Show can be put in alist, and any Show operation can be performed on the alist's members. No casts, wrappers, or other special types and plumbing are needed.

Why isn't it possible to do this directly in Haskell?

My impression is that you often don't have this requirement, since functions are first-class values and you can treat them as closures. Consider this (silly) C++: struct Iface { // Yields the length of the printable representation of some object, plus some custom value. virtual int lengthPlus( int i ) = 0; }; struct MyString : Iface { MyString( const std::string &s ) : m_s( s ) { } virtual int lengthPlus( int i ) { return m_s.size() + i; } std::string m_s; }; struct MyBoolean : Iface { MyBoolean( bool b ) : m_b( b ) { } virtual int lengthPlus( int i ) { return m_b ? strlen( "True" ) + i : strlen( "False" ) + i; } bool m_b; }; You could now have code like: std::list l; l.push_back( new MyString( "Sample" ) ); l.push_back( new MyBoolean( true ) ); std::list::const_iterator it, end = l.end(); for ( it = l.begin(); it != end; ++it ) { std::cout << (*it)->lengthPlus( 4 ); } Now, in Haskell you wouldn't need the interface in the first place. You could use plain functions (I'm using slightly ugly naming here to show the parallels to the C++ code): MyString_lengthPlus :: String -> Int -> Int MyString_lengthPlus s i = length s + i MyBoolean_lengthPlus :: Bool -> Int -> Int MyBoolean_lengthPlus True i = 4 + i MyBoolean_lengthPlus False i = 5 + i l :: [Int -> Int] l = [MyString_lengthPlus "Sample", MyBoolean True] print $ map ($ 4) l Note how, just like in C++, the type of the actual value on which the 'map' in the last line works on is hidden at the moment the list 'l' is populated with values. -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing

Ozgur Akgun

5:28 p.m.

Hi. On 28 May 2013 18:07, Frerich Raabe wrote:

...

On May 28, 2013, at 12:36 AM, harry wrote:

...
Every OO language which supports generics allows a declaration such as List<Show> alist, where Show is an interface. Any type implementing Show can be put in alist, and any Show operation can be performed on the alist's members. No casts, wrappers, or other special types and plumbing are needed.

Why isn't it possible to do this directly in Haskell?

My impression is that you often don't have this requirement, since functions are first-class values and you can treat them as closures.

This might also be relevant: http://okmij.org/ftp/Computation/Existentials.html Hope this helps, Ozgur.

4342

Age (days ago)

4420

Last active (days ago)

List overview

Download

14 comments

10 participants

participants (10)

Brandon Allbery
Brent Yorgey
Ertugrul Söylemez
Frerich Raabe
Giacomo Tesio
harry
Magnus Therning
Mateusz Kowalczyk
Mike Ledger
Ozgur Akgun