One day I was playing around with types and I came across this type:
data S m a = Nil | Cons a (m (S m a))
The idea being one could use generic functions with whatever monad m (of course m doesn't need to be a monad but my original idea was to be able to make mutable lists with some sort of monad m.) Anyway in attempting to define a generic show instance for the above datatype I finally came upon:
instance (Show a, Show (m (S m a))) => Show (S m a) where show Nil = "Nil" show (Cons x y) = "Cons " ++ show x ++ " " ++ show y
which boggles my mind. But hugs +98 and ghci -fallow-undecidable-instances both allow it to compile but when i try
show s
on
s = Cons 3 [Cons 4 [], Cons 5 [Cons 2 [],Cons 3 []]]
(btw yes we are "nesting" an arbitrary lists here! however structurally it really isnt much different from any tree datatype) we get ERROR - *** The type checker has reached the cutoff limit while trying to *** determine whether: *** Show (S [] Integer) *** can be deduced from: *** () *** This may indicate that the problem is undecidable. However, *** you may still try to increase the cutoff limit using the -c *** option and then try again. (The current setting is -c998) funny thing is apparently if you set -c to an odd number (on hugs) it gives *** The type checker has reached the cutoff limit while trying to *** determine whether: *** Show Integer *** can be deduced from: *** () why would it try to deduce Show integer? Anyway, is my instance declaration still a bit mucked up? Also, could there be a way to give a definition of show for S [] a? Heres my sample definition just in case anybody is curious.
myshow Nil = "Nil" myshow (Cons x y) = "Cons "++ show x ++ " [" ++ blowup y ++ "]" where blowup (x:y:ls) = myshow x ++ "," ++ blowup (y:ls) blowup (x:[]) = myshow x blowup [] = ""
Thanks, Jay Cox yet another non-academic person on this list.
On Sun, May 27, 2001 at 10:46:37PM -0500, Jay Cox wrote:
data S m a = Nil | Cons a (m (S m a)) ... instance (Show a, Show (m (S m a))) => Show (S m a) where show Nil = "Nil" show (Cons x y) = "Cons " ++ show x ++ " " ++ show y ... show s s = Cons 3 [Cons 4 [], Cons 5 [Cons 2 [],Cons 3 []]]
Anyway, is my instance declaration still a bit mucked up?
Hmm. To try to deduce Show (S [] Integer), the type checker reduces it by your instance declaration to Show [S [] Integer], which reduces to Show (S [] Integer), which reduces to... ghci or hugs could, in theory, be slightly smarter and handle this case.
Also, could there be a way to give a definition of show for S [] a?
Yes. You could drop the generality: instance (Show a) => Show (S [] a) where show Nil = "Nil" show (Cons x y) = "Cons " ++ show x ++ " " ++ show y Really, the context you want is something like instance (Show a, forall b. Show b => Show (m b)) => Show (S m b) ... if that were legal. --Dylan
Jay Cox writes: | One day I was playing around with types and I came across this type: | | >data S m a = Nil | Cons a (m (S m a)) : | >instance (Show a, Show (m (S m a))) => Show (S m a) where | > show Nil = "Nil" | > show (Cons x y) = "Cons " ++ show x ++ " " ++ show y | | which boggles my mind. But hugs +98 and ghci | -fallow-undecidable-instances both allow it to compile but when i try | | >show s | | on | | >s = Cons 3 [Cons 4 [], Cons 5 [Cons 2 [],Cons 3 []]] | | (btw yes we are "nesting" an arbitrary lists here! however structurally | it really isnt much different from any tree datatype) | | we get | | | ERROR - | *** The type checker has reached the cutoff limit while trying to | *** determine whether: | *** Show (S [] Integer) | *** can be deduced from: | *** () | *** This may indicate that the problem is undecidable. However, | *** you may still try to increase the cutoff limit using the -c | *** option and then try again. (The current setting is -c998) | | | funny thing is apparently if you set -c to an odd number (on hugs) | it gives | | | *** The type checker has reached the cutoff limit while trying to | *** determine whether: | *** Show Integer | *** can be deduced from: | *** () | | why would it try to deduce Show integer? It's the first subgoal of Show (S [] Integer). If the cutoff were greater by 1, presumably it's achieved, and then that last memory cell is reused for the second subgoal Show [S [] Integer], which in turn has a subgoal Show (S [] Integer), which overflows... as Dylan's just pointed out, so I'll stop now. - Tom
On 2001-05-27T22:46:37-0500, Jay Cox wrote:
data S m a = Nil | Cons a (m (S m a))
instance (Show a, Show (m (S m a))) => Show (S m a) where show Nil = "Nil" show (Cons x y) = "Cons " ++ show x ++ " " ++ show y
Here's how I've been handling such situations: data S m a = Nil | Cons a (m (S m a)) -- "ShowF f" means that the functor f "preserves Show" class ShowF f where showsPrecF :: (Int -> a -> ShowS) -> (Int -> f a -> ShowS) -- "instance ShowF []" is based on showList instance ShowF [] where showsPrecF sh p [] = showString "[]" showsPrecF sh p (x:xs) = showChar '[' . sh 0 x . showl xs where showl [] = showChar ']' showl (x:xs) = showChar ',' . sh 0 x . showl xs -- S preserves ShowF instance (ShowF m) => ShowF (S m) where showsPrecF sh p Nil = showString "Nil" showsPrecF sh p (Cons x y) = showString "Cons " . sh 0 x . showChar ' ' . showsPrecF (showsPrecF sh) 0 y -- Now we can define "instance Show (S m a)" as desired instance (Show a, ShowF m) => Show (S m a) where showsPrec = showsPrecF showsPrec You could call it the poor man's generic programming... -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
My SUV is bigger than your bike. Stay out of the damn road! Kiss my reflector, SUV-boy I'm too busy sucking on my tailpipe, bike dude.
I'm having a little of a problem with a project of mine. Just check out this, which is the minimum piece of code that will show this problem: ---- type MyType a = a (+++) :: MyType a -> MyType a -> MyType a a +++ b = a class MyClass a where baseVal :: a val1 :: MyClass a => MyType a val1 = baseVal val2 :: MyClass a => MyType a val2 = baseVal -- combVal :: MyClass a => MyType a combVal = val1 +++ val2 -- line 18 is here... ---- Trying this in Hugs returns the following error: ---- ERROR E:\JCAB\Haskell\testcv.hs:18 - Unresolved top-level overloading *** Binding : combVal *** Outstanding context : MyClass b ---- Now, how can it possibly say that the context "MyClass b" is outstanding? What does this mean? Uncommenting the type expression above clears the error. But, why can't the compiler deduce it by itself? I mean, if a function has type shaped like in (a -> a -> a) and it is used with parameters (cv => a) where the constrains are identical, then the result MUST be (cv => a) too, right? Or am I missing something here? Don't get me wrong, I can just put type declarations everywhere in my code. It's a good thing, too. But this problem is really nagging at me because I don't get where the problem is. Any ideas or pointers? Salutaciones, JCAB --------------------------------------------------------------------- Juan Carlos "JCAB" Arevalo Baeza | http://www.roningames.com Senior Technology programmer | mailto:jcab@roningames.com Ronin Entertainment | ICQ: 10913692 (my opinions are only mine) JCAB's Rumblings: http://www.metro.net/jcab/Rumblings/html/index.html
Jay Cox complained that the following is not possible: | data S m a = Nil | Cons a (m (S m a)) | | instance (Show a, Show (m (S m a))) => Show (S m a) where | show Nil = "Nil" | show (Cons x y) = "Cons " ++ show x ++ " " ++ show y Ken Shan answered: | Here's how I've been handling such situations: | | data S m a = Nil | Cons a (m (S m a)) | | -- "ShowF f" means that the functor f "preserves Show" | class ShowF f where | showsPrecF :: (Int -> a -> ShowS) -> (Int -> f a -> ShowS) Actually, this class definition can be simplified to: class ShowF f where showsPrecF :: Show a => Int -> f a -> ShowS And the rest of Ken's code accordingly. /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden
participants (6)
-
Dylan Thurston -
Jay Cox -
Juan Carlos Arevalo Baeza -
Ken Shan -
Koen Claessen -
Tom Pledger