Skip to content

Instantly share code, notes, and snippets.

@andrewthad
Created December 27, 2015 22:27
Show Gist options
  • Save andrewthad/b6a815c0ea91800edc1d to your computer and use it in GitHub Desktop.
Save andrewthad/b6a815c0ea91800edc1d to your computer and use it in GitHub Desktop.
Demonstration of GHC taking a long time to union two ordered type-level lists
{-# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment