Last active
January 12, 2024 16:53
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-# 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