haskell - Why won't GHC reduce my type family? -

here's untyped lambda calculus terms indexed free variables. i'm using singletons library singleton values of type-level strings.

{-# language datakinds #-} {-# language gadts #-} {-# language polykinds #-} {-# language typefamilies #-} {-# language typeoperators #-} {-# language undecidableinstances #-}  import data.singletons import data.singletons.typelits  data expr (free :: [symbol])     var :: sing -> expr '[a]     lam :: sing -> expr -> expr (remove as)     app :: expr free1 -> expr free2 -> expr (union free1 free2) 

a var introduces free variable. lambda abstraction binds variable appears free in body (if there's 1 matches). applications join free variables of 2 parts of expression, removing duplicates (so free variables of x y x , y, while free variables of x x x). wrote out type families:

type family remove x xs     remove x '[] = '[]     remove x (x ': xs) = remove x xs     remove x (y ': xs) = y ': remove x xs  type family union xs ys     union xs ys = nub (xs :++ ys)  type family xs :++ ys     '[] :++ ys = ys     (x ': xs) :++ ys = x ': (xs :++ ys)  type family nub xs     nub xs = nub' '[] xs  type family nub' seen xs     nub' seen '[] = '[]     nub' seen (x ': xs) = if (elem x seen) (nub' seen xs) (nub' (x ': seen) (x ': xs))  type family if c t f     if true t f = t     if false t f = f  type family elem x xs     elem x '[] = false     elem x (x ': xs) = true     elem x (y ': xs) = elem x xs 

i tested out @ interactive prompt:

ghci> :t var (sing :: sing "x") var (sing :: sing "x") :: expr '["x"]  -- ghci> :t (lam (sing :: sing "x") (var (sing :: sing "x"))) (lam (sing :: sing "x") (var (sing :: sing "x")))   :: expr (remove "x" '["x"])  -- not 

i surprised learn type of identity function \x. x expr (remove "x" '["x"]), not expr '[]. ghc seems unwilling evaluate type family remove. experimented little more , learned it's not problem type family per se - ghc happy reduce in case:

ghci> :t (proxy :: proxy (remove "x" '["x"])) (proxy :: proxy (remove "x" '["x"])) :: proxy '[] 

so: why won't ghc reduce remove "x" '["x"] '[] when query type of gadt? in general, when will-or-won't type checker evaluate type family? there heuristics can use avoid being surprised behaviour?

it works. ghc seems lazy.

λ *main > :t (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) (lam (proxy :: proxy "x") (var (proxy :: proxy "x")))   :: expr (remove "x" '["x"])  λ *main > :t (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) :: expr '[] (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) :: expr '[]   :: expr '[]  λ *main > :t (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) :: expr '["x"]  <interactive>:1:2:     couldn't match type ‘'[]’ ‘'["x"]’     expected type: expr '["x"]       actual type: expr (remove "x" '["x"])     in expression:         (lam (proxy :: proxy "x") (var (proxy :: proxy "x"))) ::           expr '["x"] 

---

i changed definitions there isn't dependency on singletons library (easier test in ad-hoc):

{-# language typeoperators, datakinds, typefamilies, gadts #-}  import data.proxy import ghc.typelits  type family remove (x :: symbol) (xs :: [symbol])     remove x '[] = '[]     remove x (x ': xs) = remove x xs     remove x (y ': xs) = y ': remove x xs  data expr (free :: [symbol])     var :: knownsymbol => proxy -> expr '[a]     lam :: knownsymbol => proxy -> expr -> expr (remove as) --    app :: expr free1 -> expr free2 -> expr (union free1 free2)