type class question from MReader #8
I am reading the article from Monad Reader issue #8 called Type-Level Instant Insanity by Conrad Parker and I don't understand the part on recursive types. data Nil data Cons x xs data x ::: xs infixr 5 ::: class ListConcat a1 a2 a | a1 a2 -> a where listConcat :: a1 -> a2 -> a instance ListConcat Nil a a where listConcat = _|_ instance (ListConcat xs ys zs) => ListConcat (x ::: xs) ys (x ::: zs) where listConcat = _|_ 1. How does the last function becomes recursive? 2. Why do we need constraint '(ListConcat xs ys zs) =>' ? 3. I assume that listConcat function takes three arguments but from example provided, it takes two (see below): 4. Does the functional dependency sign (->) implies that the last argument is the return type? Main> :type listConcat (u:: R ::: G ::: B ::: Nil) (u:: W ::: Nil) listConcat (u::R:::G:::B:::Nil) (u::W:::Nil)::(:::) R ((:::) G ((:::) B ((:::) W Nil))) Thanks a lot. Malik
On Jul 13, 2009, at 23:43 , MH wrote:
class ListConcat a1 a2 a | a1 a2 -> a where listConcat :: a1 -> a2 -> a
instance ListConcat Nil a a where listConcat = _|_
instance (ListConcat xs ys zs) => ListConcat (x ::: xs) ys (x ::: zs) where listConcat = _|_
1. How does the last function becomes recursive? 2. Why do we need constraint '(ListConcat xs ys zs) =>' ?
Your second question is the answer to the first.
3. I assume that listConcat function takes three arguments but from example provided, it takes two (see below):
The last type in the (->) chain is the return type, not an argument.
4. Does the functional dependency sign (->) implies that the last argument is the return type?
No, it says type a (which is designated as the return type by the definition of listConcat) is uniquely determined by the pair of argument types a1, a2 taken together. (That is, any given unique combination of argument types produces a unique result type.) -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Could you please elaborate on how does the constraint (ListConcat xs
ys zs) makes the instance ListConcat (x ::: xs) ys (x ::: zs)
recursive.
Also, I am interested to learn more about various ways to constrain
type classes parameters, is there a paper you would recommend?
Thanks
On Tue, Jul 14, 2009 at 1:12 AM, Brandon S. Allbery
KF8NH
On Jul 13, 2009, at 23:43 , MH wrote:
class ListConcat a1 a2 a | a1 a2 -> a where listConcat :: a1 -> a2 -> a
instance ListConcat Nil a a where listConcat = _|_
instance (ListConcat xs ys zs) => ListConcat (x ::: xs) ys (x ::: zs) where listConcat = _|_
1. How does the last function becomes recursive? 2. Why do we need constraint '(ListConcat xs ys zs) =>' ?
Your second question is the answer to the first.
3. I assume that listConcat function takes three arguments but from example provided, it takes two (see below):
The last type in the (->) chain is the return type, not an argument.
4. Does the functional dependency sign (->) implies that the last argument is the return type?
No, it says type a (which is designated as the return type by the definition of listConcat) is uniquely determined by the pair of argument types a1, a2 taken together. (That is, any given unique combination of argument types produces a unique result type.)
-- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
On Tue, Jul 14, 2009 at 10:05:03AM -0400, MH wrote:
Could you please elaborate on how does the constraint (ListConcat xs ys zs) makes the instance ListConcat (x ::: xs) ys (x ::: zs) recursive.
instance (ListConcat xs ys zs) => ListConcat (x ::: xs) ys (x ::: zs) where listConcat = _|_
This says that '(x ::: xs) ys (x ::: zs)' is an instance of ListConcat *if* 'xs ys zs' is. So you can think of the 'ListConcat xs ys zs' constraint as a recursive call made by 'ListConcat (x ::: xs) ys (x ::: zs)'. As a Haskell function we might write it something like this: isListConcatInstance (x ::: xs) ys (z ::: zs) = x == z && isListConcatInstance xs ys zs Does that help? -Brent
participants (3)
-
Brandon S. Allbery KF8NH -
Brent Yorgey -
MH