Demonstration of GHC taking a long time to union two ordered type-level lists

union.hs

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE UndecidableInstances #-}
import Data.Proxy
import GHC.TypeLits

main :: IO ()
main = do
  putStrLn "Start"
  putStrLn "End"

type family IfOrd (a :: Ordering) (lt :: k) (eq :: k) (gt :: k) where 
  IfOrd LT lt eq gt = lt
  IfOrd EQ lt eq gt = eq
  IfOrd GT lt eq gt = gt

type family Union (a :: [Symbol]) (b :: [Symbol]) :: [Symbol] where
  Union '[] '[] = '[]
  Union '[] (b ': bs) = b ': Union '[] bs 
  Union (a ': as) '[] = a ': Union as '[]
  Union (a ': as) (b ': bs) = 
    IfOrd (CmpSymbol a b)
      (b ': Union (a ': as) bs)
      (a ': Union as bs)
      (a ': Union as (b ': bs))

type A =
  '[ "zzz"
   , "foo"
   , "enough"
   , "dog"
   , "daisy"
   , "bob"
   , "baz"
   , "bar"
   ]

type B =
  '[ "zzz"
   , "type"
   , "super"
   , "silent"
   , "gorge"
   , "foo"
   , "bob"
   , "baz"
   , "bar"
   , "bam"
   , "aleph"
   , "agarsh"
   ]

foo :: Proxy (Union A B)
foo = Proxy