Extreme branchless: primitives

Previously, we have tackled Maybe/Stream branchless.

But we still have many Algebraic data-types under the hood, such as... Strings, which are defined as:

type String = [Char]

A plain old list of Char, let's define it.

A List is a Stream with a end (one more constructor):

newtype List a = List (forall b. b -> (a -> List a -> b) -> b)

We could define few utils:

toList :: [a] -> List a
toList =
  \case
    [] -> List $ \h _ -> h
    (x : xs) -> List $ \_ t -> t x (toList xs)

fromList :: List a -> [a]
fromList (List f) = f [] (\h t -> h : fromList t)

Note: take some time to admire the simplicity of fromList.

Then we need the Semigroup instance is needed to merge "Fizz" and "Buzz":

instance Semigroup (List a) where
  List f <> List g = List $ \h t -> f (g h t) (\h' t' -> t h' (t' <> List g))

We could redefine String:

type String' = List Char

Additionally, we need Eq and Show

instance Show String' where
  show = show . fromList

instance Eq a => Eq (List a) where
  List f == List g =
    f
      (g True (\_ _ -> False))
      (\h t -> g False (\h' t' -> h == h' && t == t'))

Finally, GHC allows defining types instantiated from string symbols.

To do so, we need an instance of IsString, which has one function, taking a String, so it's easy as:

instance IsString String' where
  fromString = toList

So far so good, we have a framework to convert Algebraic Data Types to lambda calculus representation:

• One parameter per constructors
• All parameters are functions ending by the transformed existential type
• The resulting function ends by the transformed existential type

Sadly, we still have one place with pattern-matching:

atStream :: Int -> Stream a  -> a
atStream n s
  | n <= 0 = headStream s
  | otherwise = n - 1 `atStream` tailStream s

Yes, you read it correctly: Numbers.

Hopefully, there is a famous way to represent them: Church Encoding.

The basic idea is: we have a function, which applies n times a given function:

newtype Natural = Natural (forall x. (x -> x) -> x -> x)

So we have:

zero = Natural $ \_ x -> x
one = Natural $ \f x -> f x
two = Natural $ \f x -> f (f x)

So we can rewrite atStream:

infixr 4 `atStream'`

atStream' :: Natural -> Stream a  -> a
atStream' (Natural n) s = headStream $ n tailStream s

It's way simpler: tailStream is applied n times, then we fetch headStream.

Sadly, we won't implement subtraction for the moment, let's adjust fizzbuzz:

fizzbuzz' :: Natural -> String'
fizzbuzz' n = n `atStream'` error "FizzBuzz isn't defined at 0" .: fizzbuzzStream

Finally, as for String', we can implement Show (display) and Num (basic numbers operation and converting from symbols, like IsString):

instance Num Natural where
  Natural m + Natural n = Natural $ \f x -> m f (n f x)
  Natural m * Natural n = Natural $ \f x -> m (n f) x
  abs = id
  signum (Natural n) = Natural $ \f x -> n (const $ f x) x
  fromInteger =
    \case
      0 -> Natural $ \_ x -> x
      n | n < 0 -> error "Church Natural can't be negative"
        | otherwise -> let Natural m = fromInteger (n - 1) in Natural $ \f x -> f (m f x)
  (-) = error "Church Natural can't be subtracted"

instance Show Natural where
  show (Natural f) = show $ f (1 +) 0

Note: we have left some parts not implemented, partly due to a more complex implementation, partly because Num is too big and deserves to be split.

And that's it, a pure, end-to-end fizzbuzz branchless.

Done correctly, adding the right constraint, how extreme is it, can improve a design, even this style improved ergonomics.

Back to top