Defining custom type families over the Nat kind

Question

How does one define new computation over types of kind GHC.TypeLits.Nat? I am hoping to be able to define a type family

type family WIDTH (n :: Nat) :: Nat

such that WIDTH 0 ~ 0 and WIDTH (n+1) ~ log2 n

Answer 1

We can pattern match on any literal Nat, then recurse using built-in operations.

{-# LANGUAGE UndecidableInstances #-}

import GHC.TypeLits

type family Div2 n where
  Div2 0 = 0
  Div2 1 = 0
  Div2 n = Div2 (n - 2) + 1

type family Log2 n where
  Log2 0 = 0  -- there has to be a case, else we get nontermination
              -- or we could return Maybe Nat
  Log2 1 = 0
  Log2 n = Log2 (Div2 n) + 1

type family WIDTH n where
  WIDTH 0 = 0
  WIDTH n = Log2 (n - 1)