3

I have troubles with the following simple code in Haskell:

import Prelude hiding (cycle).

class ICycle a where
    cycle :: a -> a

instance ICycle [a] where
    cycle [] = []
    cycle (x:xs) = xs ++ [x]

instance ICycle Bool where
    cycle True = False
    cycle False = True

instance Num a => ICycle a where
    cycle n = n+1

main = do
    print $ cycle $ [1,2,3]
    print $ cycle $ True
    print $ cycle $ 42

Here the first two instance declarations work as expected, but the third one triggers various sorts of errors depending on flag combinations.

I know that Num a is no shorter than ICycle a and hence the compiler can not finish type checking. In the examples, I have seen this is circumvented by either making the right-hand side a bigger term or by declaring a class of interest a subclass of other classes in the first place. Here, to the contrary, I essentially want to declare an existing class to be a subclass of a new one.

I wonder if there are objections against this kind of use of type classes. Or else, if there is a natural solution.

Sergey
  • 31
  • 2
  • 1
    What do you mean by "`Num a` is no shorter than `ICycle a` and hence the compiler can not finish type checking"? *Shorter* in what sense? – G Philip Apr 28 '15 at 23:30
  • 1
    The fact that the last instance may cause constraint checking to be undecidable is not a real issue. But the last instance is overlapping with the previous ones -- and this _is_ an issue. Consider what should happen if one adds `instance Num Bool` or `instance Num [a]`: the code would be ambiguous. – chi Apr 28 '15 at 23:43
  • I mean, shorter as a term tree. This has been discussed here: http://stackoverflow.com/questions/7198907/haskell-constraint-is-no-smaller-than-the-instance-head – Sergey Apr 28 '15 at 23:45
  • There is a simple solution: use DefaultSignatures to write a default implementation of `cycle n = n + 1` and then add instances for all of the `Num` types. – user2407038 Apr 29 '15 at 01:01

2 Answers2

3

For this particular example, I think you're best off using a newtype to wrap the instance:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Prelude hiding (cycle)

class ICycle a where
    cycle :: a -> a

newtype Succ a = Succ { runSucc :: a }
  deriving (Num, Eq, Ord, Bounded, Enum, Show, Read)

newtype Pred a = Pred { runPred :: a }
  deriving (Num, Eq, Ord, Bounded, Enum, Show, Read)

instance Enum a => ICycle (Succ a) where
    cycle = Succ . succ . runSucc

instance Enum a => ICycle (Pred a) where
    cycle = Pred . pred . runPred

main = do
    print $ cycle $ (42 :: Succ Int)
    print $ cycle $ (42 :: Pred Int)

There are multiple ways one could cycle through numbers - by succ, by pred, by doubling, by halving. The advantage of using a newtype for the instance (making the RHS "bigger", as you noted in your question) is that it lets us have ALL of them.

The standard library does the same trick with Product and Sum for Monoid.

Looking at it another way, if it were possible to define a new superclass for Num, adding a default implementation for all instances of Num, then you'd be taking that choice away from all those implementations. In possibly a way that doesn't make sense.

rampion
  • 87,131
  • 49
  • 199
  • 315
  • So, the message is: if you need something specific, you first need to go and implement something generic (even if you do not believe in it). And it is especially welcome to rationalize the fact that the byproducts of this work are to be useful. That seems to be one of those philosophical points behind Haskell I am not very good at. – Sergey Apr 29 '15 at 19:27
2

According to the Haskell report 2010, chapter 4, Declarations and Bindings, the thing that is to be defined as an instance needs to be a type constructor. Thus,

instance Num a => ICycle a where
    ...

is invalid, because a is a type variable, not a type constructor.

Therefore the valid way to do it is, unfortunately, type by type. One has to say:

instance ICycle Int where
    ...

instance ICycle Double where
    ...

and so on.

Abhay
  • 768
  • 4
  • 13
  • @CarstenKönig Did you delete your comments? Without those, mine look like I am talking to a wall! :) – Abhay Apr 29 '15 at 05:05
  • yeah I did - they made no sense (sorry again) - I was under the impression that the OP was using `FlexibleInstance` and some other extensions but never mentioned it really - so shame on me – Random Dev Apr 29 '15 at 05:07
  • No! They made perfect sense, and I had to look up the manual once more to see what all can come under type constructor, just to be sure. Thanks for making me look at the manual! – Abhay Apr 29 '15 at 05:09