Odd behavior with stable names and type constraints.

Test.hs

-- Odd behavior using stable names: polymorphism with type constraints causes
-- non-termination (see the tests at the bottom).

module Test where

import System.Mem.StableName (StableName, makeStableName)

---------------------------------------------------------------------------------

type Map a = [StableName (Expr a)]

analyze :: Expr a -> IO (Map a)
analyze = analyzeExpr [] 

analyzeExpr :: (Map a) -> Expr a -> IO (Map a)
analyzeExpr env e@(Op e0) = do
  sn <- makeStableName e
  if elem sn env
    then return env
    else analyzeExpr (sn : env) e0

---------------------------------------------------------------------------------
-- Language, with one constructor

class Typed a where

instance Typed Int

data Expr a = Op (Expr a) 

expr0 :: Expr a
expr0 = Op expr0

expr1 :: Typed a => Expr a
expr1 = Op expr1

expr2 :: Typed a => Expr a
expr2 = x 
  where x = Op x

---------------------------------------------------------------------------------
-- Tests

-- Returns 1
test0 :: IO ()
test0 = test (expr0 :: Expr Int)

-- Doesn't terminate!
test1 :: IO ()
test1 = test (expr1 :: Expr Int)

-- Returns 1
test2 :: IO ()
test2 = test (expr2 :: Expr Int)

test :: Expr a -> IO ()
test e = analyze e >>= putStrLn . show . length