Skip to content

Instantly share code, notes, and snippets.

@Talndir
Last active January 12, 2024 16:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Talndir/6567abfa2cf9671e808766243b8c94e2 to your computer and use it in GitHub Desktop.
Save Talndir/6567abfa2cf9671e808766243b8c94e2 to your computer and use it in GitHub Desktop.
FizzBuzz in Haskell at the type level. Use `:t fizzbuzz` in GHCi to get the output.
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE UndecidableInstances #-}
module FizzBuzz where
import Data.Kind (Type)
import GHC.TypeLits (Symbol, AppendSymbol)
data Nat :: Type where
Z :: Nat
S :: Nat -> Nat
type N0 = Z
type N1 = S N0
type N2 = S N1
type N3 = S N2
type N4 = S N3
type N5 = S N4
type N6 = S N5
type N7 = S N6
type N8 = S N7
type N9 = S N8
type N10 = S N9
type family Add (n :: Nat) (m :: Nat) :: Nat where
Add Z n = n
Add (S n) m = Add n (S m)
type family Mul (n :: Nat) (m :: Nat) :: Nat where
Mul Z n = Z
Mul (S n) m = Add m (Mul n m)
type family ShowDigit (n :: Nat) :: Symbol where
ShowDigit N0 = "0"
ShowDigit N1 = "1"
ShowDigit N2 = "2"
ShowDigit N3 = "3"
ShowDigit N4 = "4"
ShowDigit N5 = "5"
ShowDigit N6 = "6"
ShowDigit N7 = "7"
ShowDigit N8 = "8"
ShowDigit N9 = "9"
type family Div' (n :: Nat) (k :: Nat) (a :: Nat) :: Nat where
Div' n Z a = S (Div' n a a)
Div' Z _ _ = Z
Div' (S n) (S k) a = Div' n k a
type Div n k = Div' n k k
type family Mod' (n :: Nat) (k :: Nat) (a :: Nat) :: Nat where
Mod' n a a = Mod' n Z a
Mod' Z k _ = k
Mod' (S n) k a = Mod' n (S k) a
type Mod n k = Mod' n Z k
type family ShowNat' (n :: Nat) (d :: Nat) (m :: Nat) :: Symbol where
ShowNat' Z _ _ = ""
ShowNat' n d m = AppendSymbol (ShowNat' d (Div d N10) (Mod d N10)) (ShowDigit m)
type family ShowNat (n :: Nat) :: Symbol where
ShowNat Z = "0"
ShowNat n = ShowNat' n (Div n N10) (Mod n N10)
type family FB' (c :: Nat) (n3 :: Nat) (n5 :: Nat) (k :: Nat) :: [Symbol] where
FB' Z _ _ _ = '[]
FB' (S n) N3 N5 k = "FizzBuzz" ': FB' n N1 N1 (S k)
FB' (S n) N3 n5 k = "Fizz" ': FB' n N1 (S n5) (S k)
FB' (S n) n3 N5 k = "Buzz" ': FB' n (S n3) N1 (S k)
FB' (S n) n3 n5 k = ShowNat k ': FB' n (S n3) (S n5) (S k)
type FB n = FB' n N1 N1 N1
data FizzBuzz (xs :: [Symbol]) :: Type where
FizzBuzz :: FizzBuzz (FB n)
-- Stackoverflow at anything above 96
type N50 = Mul N10 N5
-- Get the final result by opening GHCi and running `:t fizzbuzz`
-- Also shows up visually if you're using HLS
fizzbuzz = FizzBuzz @N50
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment