Skip to content

Instantly share code, notes, and snippets.

@erose
Created December 9, 2019 18:20
Show Gist options
  • Save erose/72497ad698119d4a969d2067fd0a7067 to your computer and use it in GitHub Desktop.
Save erose/72497ad698119d4a969d2067fd0a7067 to your computer and use it in GitHub Desktop.
The simplest way I know of to crash/hang the Haskell typechecker using UndecidableInstances.
-- Inspired by https://aphyr.com/posts/342-typing-the-technical-interview and
-- https://wiki.haskell.org/wikiupload/d/dd/TMR-Issue8.pdf. See the latter for a well-paced
-- introduction to what's going on in general.
-- Allows one type parameter to a class to be fully determined by the type of another.
{-# LANGUAGE FunctionalDependencies #-}
-- The head of an instance declaration may mention arbitrary nested types.
{-# LANGUAGE FlexibleInstances #-}
-- Lifts rules that would ensure the typechecker always terminates when checking instance
-- declarations. <devilface.jpg>
{-# LANGUAGE UndecidableInstances #-}
-- The following class is conceptually similar, on the type level, to the following term-level function.
-- loop :: a -> b
-- loop x = let y = loop [x] in loop y
class Loop a b | a -> b where -- using FunctionalDependencies
runLoop :: a -> b
instance (Loop [x] y) => Loop x y -- using FlexibleInstances
main :: IO ()
main = runLoop undefined
-- Run with GHC >= 8.8.1, like
-- `ghc -freduction-depth=0 -fno-warn-missing-methods crash-the-haskell-typechecker.hs`
-- or with Stack like
-- `stack ghc -- -freduction-depth=0 -fno-warn-missing-methods crash-the-haskell-typechecker.hs``
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment