Shin-Cheng Mu <scm@ipl.t.u-tokyo.ac.jp> wrote:
Occasionally I would need to define recursive datatypes using an explicit fixed-point operator, such as:
data Fix f = In (f (Fix f)) deriving (Show, Eq) data L a x = Nil | Cons a x deriving (Show, Eq)
However, Haskell was not able to derive from Fix f any instances. The following is what happens in GHCi:
*Main> In Nil == In Nil
Context reduction stack overflow; size = 21
[...]
Instance Show (f (Fix f)) => Show (Fix f) where showsPrec _ (In x) = ("In ("++) . showsPrec 1 x . (')':)
This is rather unsatisfactory, because I would not be able to inspect values of type Fix f in the interpreter. Is there a way to get around this?
You have to tie the knot yourself --- unfortunately this involves re-coding the instance functors behind ``deriving''. I did this last summer for demonstration purposes --- you need only -fglasgow-exts for the ``deep instance'': \begin{code} module Fix where data Fix f = F (f (Fix f)) data L a b = L (Maybe (a,b)) deriving Show oParen = ('(' :) cParen = (')' :) parens shows = oParen . shows . cParen mkShowsPair showsA showsB (a,b) = parens $ showsA a . (", " ++) . showsB b mkShowsMaybe showsA Nothing = ("Nothing" ++) mkShowsMaybe showsA (Just a) = parens $ ("Just " ++) . showsA a mkShowsL showsA showsB (L m) = parens $ ("L " ++) . mkShowsMaybe (mkShowsPair showsA showsB) m mkShowsFix :: ((Fix f -> ShowS) -> (f (Fix f) -> ShowS)) -> (Fix f -> ShowS) mkShowsFix mkShowsF = showsF where showsF (F x) = parens $ ("F " ++) . mkShowsF showsF x showsFL :: (Show a) => Fix (L a) -> ShowS showsFL = mkShowsFix (mkShowsL shows) instance (Show a) => Show (Fix (L a)) where showsPrec _ = showsFL flEmpty = F (L Nothing) flCons x xs = F (L (Just (x,xs))) infixr 5 `flCons` \end{code} Wolfram