Skip to content

Loop with undecidable instances in GHC 9.4.3

Summary

Certain undecidable instances are compiled into infinite loops in GHC 9.4.3.

Steps to reproduce

This problem showed up in the logict-sequence test suite. Li-yao Xia somehow managed to figure out that the problem was the way certain instances were compiled. Here's a greatly reduced version:

-- Everything works fine with -O0 and -O. Only -O2 fails.
{-# OPTIONS_GHC -O2 #-}

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE MonoLocalBinds #-}
import Data.Function (on)
import Data.Functor.Identity

data ViewT m a
  = Empty
  | a :< SeqT m a
newtype SeqT m a = SeqT [m (ViewT m a)]

toViewT :: Monad m => SeqT m a -> m (ViewT m a)
toViewT (SeqT []) = pure Empty
toViewT (SeqT (h : t)) = h >>= \case
  Empty -> toViewT (SeqT t)
  hi :< SeqT ti -> pure (hi :< SeqT (ti ++ t))

instance (Eq (m (ViewT m a)), Monad m) => Eq (SeqT m a) where
  (==) = (==) `on` toViewT

deriving instance (Eq a, Eq (SeqT m a)) => Eq (ViewT m a)

example :: SeqT Identity Int
example = SeqT []

main :: IO ()
main = print (example == example)

When compiled with GHC 9.4.3, this prints

Buggle: <<loop>>

When compiled with versions 7.10.3, 8.0.2, 8.2.2, 8.4.4, 8.6.5, 8.8.4, 8.10.4, 9.0.2, or 9.2.5, it prints

True

For version 7.8, it works once the source is adjusted appropriately.

Expected behavior

I expect it to print True.

Environment

  • GHC version used: 9.4.3

Optional:

  • Operating System:
  • System Architecture:
Edited by David Feuer
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information