Help with Type Class
Although the discussion about Array refactoring died down quickly on the Haskell' mailing list, I've been noodling on refactoring the various Collections in Haskell. In doing so, I've bumped into a problem with type classes that I can't resolve. The issue is as follows: I'm designing a Collections class heirarchy that is a blend between that of Java and of Haskell. The problem is that, whereas in OOP it is easy to do so, Haskell class mechanism seems to make it difficult to add *new* member variable to subclasses. Simple goal: create a top-level Collection with an *indexed* Array subclass (and various other subclasses). The problem I'm running into is Collection has no need of an "index" variable and I can't seem to figure out how to add an "index" to Array when subclassing from Collection Mock up: -- class CollectionClass c e where -- every Collection supports toList... toList :: c e -> [e] class (CollectionClass a e)=> ArrayClass a e where ... data Array i e = Array i i instance CollectionClass Array e where -- Since Array is a Collection -- toList :: c e -> [e] -- but with an Array the type would be -- toList :: a i e -> [e] toList = ... -- I think that the problem goes away if: class CollectionClass c x e where ... with "x" used an index for Array or a key for Map or () for Set, but it doesn't seem clean to scatter member variables in the parent class in case the subclass requires them... Another possible solution that I couldn't get to work would be to use (Array i) as the type for "c" in "Collection c": instance CollectionClass (Array i) e where toList = ... -- (Array i) e -> [e] ? This seems clean because it says the Collection holds "e"s and is organized by an (Array i). Similarly, Set would be a Collection of "e"s organized by Set and Map would be a Collection of "e"s organized by (Map k). Undoubtedly, I've missspoken some crucial aspect of the type/kind/class/instance magical incantation. Help! - Alson
Hello Alson, Wednesday, March 1, 2006, 3:26:44 AM, you wrote: AK> class CollectionClass c e where this works with -fglasgow-exts : class CollectionClass c e where toList :: c e -> [e] data Array i e = Array i i instance CollectionClass (Array i) e where toList a = [] btw, see chapter 7.1.1 in the http://cvs.haskell.org/Hugs/pages/hugsman/exts.html -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Am Mittwoch, 1. März 2006 01:26 schrieb Alson Kemp:
Although the discussion about Array refactoring died down quickly on the Haskell' mailing list, I've been noodling on refactoring the various Collections in Haskell. In doing so, I've bumped into a problem with type classes that I can't resolve. The issue is as follows:
I'm designing a Collections class heirarchy that is a blend between that of Java and of Haskell. The problem is that, whereas in OOP it is easy to do so, Haskell class mechanism seems to make it difficult to add *new* member variable to subclasses.
Simple goal: create a top-level Collection with an *indexed* Array subclass (and various other subclasses). The problem I'm running into is Collection has no need of an "index" variable and I can't seem to figure out how to add an "index" to Array when subclassing from Collection Mock up:
-- class CollectionClass c e where -- every Collection supports toList... toList :: c e -> [e]
class (CollectionClass a e)=> ArrayClass a e where ...
data Array i e = Array i i ^^^^^^^^^^ shouldn't the element type appear here?
instance CollectionClass Array e where -- Since Array is a Collection -- toList :: c e -> [e] -- but with an Array the type would be -- toList :: a i e -> [e] toList = ...
Well, the parameter c of CollectionClass has kind (* -> *), Array has kind (* -> * -> *), so it must be instance CollectionClass (Array i) e where ... But the element type doesn't really belong in the class, wouldn't class Collection c where toList :: c e -> [e] instance Collection [] where toList = id instance Collection (Array i) where -- or rather instance Ix i => Collection (Array i), -- if we use Data.Array toList = elems -- or whatever we'd use for another implementation class Collection (a i) => ArrayC a i where item :: i -> a i e -> Maybe e -- or perhaps, better class Collection c => ArrayLike c i | c -> i where look :: Monad m => i -> c e -> m e be preferable?
--
I think that the problem goes away if: class CollectionClass c x e where ... with "x" used an index for Array or a key for Map or () for Set, but it doesn't seem clean to scatter member variables in the parent class in case the subclass requires them...
Another possible solution that I couldn't get to work would be to use (Array i) as the type for "c" in
I can't imagine why that wouldn't work (apart from the typo above). It compiles, and if we have a more appropriate Array type, we'd get a decent toList-function.
"Collection c": instance CollectionClass (Array i) e where toList = ... -- (Array i) e -> [e] ?
This seems clean because it says the Collection holds "e"s and is organized by an (Array i). Similarly, Set would be a Collection of "e"s organized by Set and Map would be a Collection of "e"s organized by (Map k).
Undoubtedly, I've missspoken some crucial aspect of the type/kind/class/instance magical incantation. Help!
- Alson
HTH, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton
data Array i e = Array i i shouldn't the element type appear here? Typo: data Array i e = Array i i [e] --mockup with
Bulat, BZ>AK> class CollectionClass c e where BZ>this works with -fglasgow-exts : Yup. Figured that out shortly after I e-mailed... Thank you for providing the extra detail, though. -fglasgow-exts fixed the problem, but I didn't have a good idea why the problem went away. Daniel, list
Well, the parameter c of CollectionClass has kind (* -> *), Array has kind (* -> * -> *), so it must be instance CollectionClass (Array i) e where ... ... which (I think) was breaking until -fglasgow-exts. Once that was fixed, this seems to be the preferred way to implement this function.
But the element type doesn't really belong in the class, wouldn't class Collection c where toList :: c e -> [e] Hmmm... For example, implementing Array and UArray as subclasses of Collection: class Collection c where toList :: c e -> [e] instance Collection (Array i) where toList a = ... instance Collection (UArray i) where toList a = ...
If Collection is not parameterized on "e", then there is no way to make sure that the "e" in Collection (UArray i):toList is actually "unboxable". As with the current IArray implementation, the following works and isn't particularly limiting in flexibility: class Collection c e where toList :: c e -> [e] instance Collection (Array i) e where toList a = ... instance Collection (UArray i) Int where --note the Int toList a = ... I understand trying to make Collection as general as possible by removing "e", but it look as if doing so makes useful subclasses difficult to implement?
-- or perhaps, better class Collection c => ArrayLike c i | c -> i where look :: Monad m => i -> c e -> m e be preferable? ermm... Need to read up on Functional Dependencies... brb...
Thanks for the help. - Alson
Am Mittwoch, 1. März 2006 20:20 schrieben Sie:
Daniel,
data Array i e = Array i i
shouldn't the element type appear here?
Typo: data Array i e = Array i i [e] --mockup with list
Well, the parameter c of CollectionClass has kind (* -> *), Array has kind (* -> * -> *), so it must be instance CollectionClass (Array i) e where ...
... which (I think) was breaking until -fglasgow-exts.
Well, Haskell98 doesn't allow multiparameter type classes, so extensions are required.
Once that was fixed, this seems to be the preferred way to implement this function.
But the element type doesn't really belong in the class, wouldn't class Collection c where toList :: c e -> [e]
Hmmm... For example, implementing Array and UArray as subclasses of Collection: class Collection c where toList :: c e -> [e] instance Collection (Array i) where toList a = ... instance Collection (UArray i) where toList a = ...
If Collection is not parameterized on "e", then there is no way to make sure that the "e" in Collection (UArray i):toList is actually "unboxable". As with
Ah, I see. I didn't think of that.
the current IArray implementation, the following works and isn't particularly limiting in flexibility: class Collection c e where toList :: c e -> [e] instance Collection (Array i) e where toList a = ... instance Collection (UArray i) Int where --note the Int toList a = ...
I understand trying to make Collection as general as possible by removing "e", but it look as if doing so makes useful subclasses difficult to implement?
Making Collection a single parameter class doesn't increase generality, I believe, but I thought that creating a collection was a property of the type constructor c alone, so the element type didn't really belong to the class. However, the UArray example gives a good reason to include it.
-- or perhaps, better class Collection c => ArrayLike c i | c -> i where look :: Monad m => i -> c e -> m e be preferable?
ermm... Need to read up on Functional Dependencies... brb...
Thus we can declare instance ArrayLike [] Int where look 0 (x:_) = return x ...
Thanks for the help.
- Alson
Cheers, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton
participants (3)
-
Alson Kemp -
Bulat Ziganshin -
Daniel Fischer