A better printf

printf is the canonical example of a variadic function. Many people believe that kind of function is impossible to write in a type-safe fashion, so it’s often brought into conversation with an obnoxious «Static typing, huh? I’d like to see how you write printf in Haskell».

Thanks to Haskell’s type system capabilites, not only is it possible to write variadic functions, but also a type-safe, polymorphic, extensible, and composable printf, that is way better than your «regular» printf.

’Tis but a neat trick.

Variadic Functions

Variadic Functions are those that take a variable number of arguments, and even no arguments at all. Note that this is not the same as receiving a possibly empty list of arguments, because that would be a single argument with variable content.

If you’ve worked with C, you’re surely familiar with a variadic function: printf. It takes one or more arguments, and prints them according to the given format

printf("Hello world\n");
printf("Answer = %d\n",42);
printf("Answer = %d, Question = %s\n",ans,msg);

Many a novice programmer going through the manual page (man 3 printf) has been baffled by its definition

int printf(const char *format,...);

because it’s obvious that the format must be an immutable string, but what’s with those periods?

The C language subroutine calling convention was designed so that any function can receive at least one argument, followed by as many additional ones. Those periods indicate to the compiler not to worry if calls to printf have a variable number of arguments, and to just push them into the stack. But, that’s it; the compiler will not perform any type checking on them. Thus, the actual number of additional arguments, their types, and whether or not they match their positions within the format string, are checked by printf’s implementation during runtime. If they’re not correct, you’ll get a runtime error.

Languages with slightly better type systems than C’s also have printf implemented with more or less the same restrictions and pitfalls.

Keep calm and curry on

Currying is one of those simple concepts that take you very far, once you learn to look for it everywhere. The first thing that understanding currying does to you, is realizing that all functions in Haskell are actually one argument functions.

The curry-aficionado, when presented with

f :: a -> b -> c

that looks like a two-argument (types a and b, respectively) function, returning a value (type c), rather thinks of it as

f :: a -> (b -> c)

a function of a single argument (type a), returning a function (from b to c).

Since function application is right associative, when we have

f x y

the implicit grouping makes it actually mean

((f x) y)

Currying combined with function application’s right associativity are already useful in the form of function sections and partial applications. Both mechanisms are core to a truly functional language, and we’ll be taking advantage of that in yet another clever way.

Currying and variadic functions

Combining currying and application right associativity we see that a variadic function is something like

f :: a -> (a -> (a -> ... (a -> b) ... ))

where the length of chained applications is determined by the number of arguments at the calling place. We should look at f as receiving a single argument (type a), and somehow producing a function that will capture the next argument at the calling place, until we’ve captured them all. At that point, the «last» function, computes the actual result (type b).

Let’s start with a simple, concrete, naïve-looking, variadic function that takes a variable list of numbers, and adds them up: a variable argument sum.

Consider the type class declaration

typeclass SumArguments a where
  sumArgs :: [Integer] -> a

It specifies that any type a can be SumArguments as long as it’s able to take a list of numbers and produce a single result value of type a.

The first part of our trick is making the result type polymorphic, instead of a monomorphic Integer. We are trying to add numbers, but keeping the result type polymorphic will allow us to decide if it’s time to add a number to our list, or to actually perform the addition, depending on the call site context.

The simplest instance we can write is when a ~ Integer. That is, we must implement sumArgs such that receiving a [Integer] returns an Integer.

instance SumArguments Integer where
  sumArgs = sum

It’s that easy. However, it doesn’t seem to help much, because sum expects a [Integer] that we still don’t know how to build.

Now, consider a call to sumArgs where there are many values in sequence, all of them Integer. What’s the type of sumArgs at this particular call site?

sumArgs 1 2 3...

If we look at it as right-associative curried function applications, it’s actually

(...(((sumArgs 1) 2) 3)...)

and now sumArgs type, in context, seems to be

sumArgs :: Integer -> (Integer -> (Integer -> ...))

Applying sumArgs to the first argument is akin to “dropping” the first Integer from it’s type, so the result type ends up being

Integer -> (Integer -> ...)

But that is pretty much the same type sumArgs looked like before consuming its first argument! That means consuming the second argument has the same context as consuming the first argument, so on and so forth for the remaining ones.

Let’s introduce a new type variable

    r ~ Integer -> (Integer -> ...)

and think of sumArgs as returning a value of type

    sumArgs :: Integer -> r

Now, we can write this SumArguments instance

instance SumArguments r => SumArguments (Integer -> r) where
  sumArgs is = \i -> sumArgs (i:is)

There’s a lot going on here. We are saying that as long as type r has a way to sum integers, then there’s a way to add one integer to the tally. We have sumArgs receiving a list of integers is and returning a function that takes an integer i, adds it to current list, and defers the problem of adding the list to whatever SumArguments is in context now.

Closing the loop

We have two SumArguments instances. Every sumArgs call site is analyzed by the compiler such that:

• If there are arguments remaining to be «collected» the call site has context Integer -> r so it compiles to the second instance.

• If there are no arguments left to be «collected» the call site has context Integer so it compiles to the first instance.

The second instance adds to the collection, while the first instance adds-up the collection. The final piece of the puzzle is a helper function – the actual one to use directly.

sumOf :: SumArguments a => a
sumOf = sumArgs []

Now sumOf doesn’t look like a function because there’s only one type in its signature. However, the SumArguments restriction allows the compiler to select the appropriate instance to use. Here we use calculational reasoning, another tool of the functional programming trade:

• When sumOf is called in a context whose type demands an integer immediately

      sumOf :: Integer
        { sumOf definition }
      sumArgs [] :: Integer
        { a ~ Integer => use SumArguments Integer }
      sum []
        { Good old sum }
      0

• When sumOf is called in a context whose type demands consuming an integer

      sumOf 1 :: Integer
        { sumOf definition }
      sumArgs [] 1 :: Integer
        { currying and right-associativity }
      ((sumArgs []) 1) :: Integer
        { sumArgs context is (Integer -> r) }
      ((\i -> sumArgs (i:[])) 1) :: Integer
        { apply lambda }
      sumArgs [1] :: Integer
        { see previous bullet }
      1

It works out fine.

ghci> sumOf :: Integer
0
ghci> :type sumOf 1 2
sumOf 1 2 :: (SumArguments (t1 -> t2 -> t3), Num t1, Num t2) => t3
ghci> sumOf 1 2 :: Integer
3
ghci> sumOf 1 2 3 :: Integer
6

But wait, there’s more!

This trick relies on looking at the type implied by each call site: if out of arguments, the context is the Integer type for the result value, so it sums; if there’s at least one argument, the context is «need a function to consume an argument and curry on» (pun intended). What if the argument were a [Integer]? Well, no sweat

instance SumArguments r => SumArguments ([Integer] -> r) where
  sumArgs is = \ns -> sumArgs $ ns ++ is

And now we have the incredibly puzzling, yet useful

ghci> sumOf 1 [2,3] 4 [5,6] 7 :: Integer
28

This pretty much sums up the trick. ¹

Let’s kick it up a notch

The previous example illustrates the fundamental trick: look at each curried call site for context, and give the compiler specific instances to use when resolving each one. That’s why we need the result type to be polymorphic in order to be applicable to any call site. The value collection remained monomorphic ([Integer]) because it wasn’t central to the collecting trick.

But we want to get more flexibility out of this, and the natural next step is to make the collection’s content’s type also polymorphic. That is to say, consider

class Collector a r | r -> a where
  collect' :: [a] -> a -> r

Notice how we simply replaced Integer with a type variable a. It becomes a multi-parameter typeclass, with the ability to collect things of any type in a list. The r -> a in the class signature is called a functional dependency (or fundep) and it’s needed to keep type inference working. It reads as «type r dictates which type a is valid in context», and will make sure there’s only one instance for each type pair. ²

But first, let’s make this new typeclass work.

Collecting polymorphic values

We need to provide two Collector instances: one to return the whole collection once we’re done collecting, and one to add one element to an existing collection. Therefore

instance Collector a [a] where
    collect' l x = reverse (x:l)

instance Collector a r => Collector a (a -> r) where
    collect' l x = \y -> collect' (x:l) y

And we’re going to need the helper function to «seed» the empty collection

collect :: Collector a r => a -> r
collect x = collect' [] x

A few things worth mentioning here:

• It follows from collect’s type signature, that it requires at least one thing to add to the collection. This mimics printf «at least one argument» behavior.

• Items are collected by adding to the front of the accumulating list for efficiency reasons. They will be in reverse order once we collect them all but the last. That’s why the list is reverse’d just after collecting the last element, to return them in the original order.

The abstraction becomes more useful

ghci> :type collect 1 2 3
collect 1 2 3 :: (Collector a t, Num a) => t
ghci> collect 1 2 3 4 5 :: [Int]
[1,2,3,4,5]
ghci> collect True False False :: [Bool]
[True,False,False]
ghci> collect 'w' 'a' 't' '?' :: String
"wat?"

What’s the fundep for?

Consider a call site such as

    collect 42 :: [Int]
      { collect definition }
    collect' [] 42 :: [Int]

Looking at the call site context, the return type is fixed as [Int]. Let’s look at the typeclass signature for collect' and reason

    collect' :: [a] -> a -> [a]
      { take (result) [a] ~ [Int], implying a ~ Int, matches }
    collect' :: [Int] -> Int -> [Int]

Great, the call site matches the signature, and we have concrete types for each. Now, which instance shall we use?

We have to match

    collect' :: [Int] -> Int -> [Int]

with the first instance

class Collector a r | r -> a where
  collect' :: [a] -> a -> r

instance Collector a [a] where

And it matches, because

    collect' :: [a] -> a -> r
      { Take a ~ Int / satisfy both arguments }
    collect' :: [Int] -> Int -> r
      { take r ~ [Int] / satisfy return type }
    collect' :: [Int] -> Int -> [Int]

and we end up with the type at the call site. It means we should use this instance.

But wait! We could also match

    collect' :: [Int] -> Int -> [Int]

with the second instance

class Collector a r | r -> a where
  collect' :: [a] -> a -> r

instance Collector a r => Collector a (a -> r) where

Because

    collect' :: [a] -> a -> r
      { Take a ~ Int / satisfy FIRST argument }
    collect' :: [Int] -> Int -> r
      { take r ~ [Int] / satisfy CURRIED type Int -> [Int] }
    collect' :: [Int] -> Int -> [Int]

and we end up with the type at the call site. It means we should use this instance, too?

Wait, what? If you’re confused, imagine the compiler.

That’s why we need the fundep!

Having multi-parameter typeclasses with polymorphic arguments and return types may lead to ambiguities like this one. This ambiguity weakens type inference, and we rather have sound type inference.

The functional dependency helps, by narrowing the actual instance based on the unique type at the call site:

• If the call site demands [a] use the first instance. This helps when the compiler is type-checking the «end» of the variable length argument list, after all arguments but the last have been consumed, and both instances would be applicable.

• If the call site demands (a -> r), where r happens to be a list because that’s our «trick», use the second instance. This applies when the compiler is type-checking the call site at any given argument but the last.

Finally we have everything we need to provide…

A better printf

The previous examples have shown how to build a type-safe, polymorphic, variadic function, that takes one or more arguments. We would like to use the same technique to provide a printf implementation such that:

• It receives at least one argument – «the format».

• It receives zero or more additional arguments – «the things to print using the format»

• The «shape» of the format helps type-check the things to print. It should establish the type at each position, and it must account for all things to print.

• «Be more flexible» – Read in the tone of a dynamic-programming language fan whose notion of flexibility is somewhat inflexible.

A better format specification

«String is the poor man’s datatype» is something that I say a lot, with the dismissive tone of a static-typing language, with an actual type system, fan. The reason behind your typical printf shortcomings has to do with the format being a String that needs to be parsed at runtime in order to figure out what should be in the stack. And that’s why it sucks.

Let’s improve printf by having a better format definition that can be parsed by the compiler, and helps the compiler check everything is correct. This new format must:

• Preserve order from left to right.

• Carry type information, possibly with additional payload, at each position of the collection.

• Be efficient – can’t get away with reversing.

• Help create a value with a type that forces the compiler to check all values to print are present and have matching types.

• Allow the programmer to extend it.

• «Be more flexible» – wait and see for yourself.

This hefty list of requirements is easily satisfied if we have one type for each possible format, and each type links to the next item in the format. It will behave as an «heterogenous linked list of position descriptions», built from left to right, each node having a specific type, and pointing to the next one.

Let’s use the following types

data End = End             -- End of format
data L f = L String f      -- Literal string
data S f = S f             -- Like %s
data I f = I f             -- Like %d

Each type, except End, is polymorphic. It allows values of each type to hold a value of any other, thus creating a «linked list» where the innermost one signals the End of the format. Each type designates an expected argument, and can carry additional payload. This design allows for easy extension to define more formats

data F f = F f             -- Format a Float
data B f = B f             -- Format a Bool
data G f = G Int Int f     -- Mantissa/exponent space

A format value built by nesting these types, is going to be the mandatory first argument for our printf implementation.

Plot twist to the old trick

We used the same trick for summing and collecting: have a typeclass that treats arguments as function application, and accumulate them in a list. Of course, they were always the same type.

Since printf is going to print, this is one of the few instances where String is the right type to use. Instead of accumulating values in a list, this new typeclass will have a single method that, for each instanced type, is going to Show its argument, add it to a String, and give the full String when done. ³

Let’s start with

class Printf f x | f -> x where
  printf' :: f -> String -> x

Where f stands for any format type. Each application of printf' will consume one «format» value and the current accumulator String. The result type is left polymorphic, as part of our trick of call site context instantiation.

Providing an instance for each format type is straightforward. The End format type only requires returning the accumulated String with everything already «printed». For the remaining format types, the instance must build a function that takes a value from the format-specified matching type, makes it into a String, appends to the accumulator, and proceeds with the next format item. ⁴

instance Printf End String where
  printf' End out = out

instance Printf fmt x => Printf (L fmt) x where
  printf' (L s fmt) out = printf' fmt (out ++ s)

instance Printf fmt x => Printf (S fmt) (String -> x) where
  printf' (S fmt) out = \s -> printf' fmt (out ++ s)

instance Printf fmt x => Printf (I fmt) (Int -> x) where
  printf' (I fmt) out = \i -> printf' fmt (out ++ show i)

instance Printf fmt x => Printf (B fmt) (Bool -> x) where
  printf' (B fmt) out = \b -> printf' fmt (out ++ if b then "t" else "f")

Finally, a few helper functions to make things pretty appealing

lit  = L
str  = S
int  = I
bool = B

This set of helper functions help writing cleaner and clearer formats. Instead of writing

    "%s = %d"

we can write

    str . lit " = " . int

Note that they are nothing more than function composition. Moreover, every format defined this way is just a function needing an argument (the next format!); this means you can have type-safe reusable formats, i.e.

msg = lit "the value is "
someNumber = lit " numeric = " . int
someString = lit " a string = " . str
someBool = lit " a boolean = " . bool

and then write things like

printf (msg . someNumber) 42
printf (msg . someString) "forty-two"
printf (msg . someBool) True

That is what we functional programmers call «flexibility».

Finally, helper function

printf :: (Printf format x) => (End -> format) -> x
printf f = printf' (f End) ""

is the one actually doing the printing. It applies the given format to End, thus completing the format function application, and uses printf' on the full format value, seeding an empty String accumulator. Look again at the signature: it will compile only if you pass a format that’s missing the End.

This works out as desired

ghci> :type printf ( list "hello world" )
String
ghci> :type printf ( int . lit " is " . str )
Int -> String -> String
ghci> :type printf ( lit "odd( " . int . lit ") = " . bool )
Int -> Bool -> String
ghci> printf ( lit "odd( " . int . lit " ) = " . bool ) 42 (odd 42)
"odd( 42 ) = f"

Using calculational reasoning, it’s easy to see how each step of printf' across the format value will build a function with nested function applications having their types directed, in order and number, by the actual format. A simple example

    printf (str . lit " = " . int) "ans" 42
      { printf definition }
    printf' ((str . lit " = " . int) End) "" "ans" 42
      { desugaring str, lit and int, and applying }
    printf' (S (L " = " (I End))) "" "ans" 42
      { substitute Printf instance for S }
    (\s -> printf' (L " = " (I End)) ("" ++ s)) "ans" 42
      { apply lambda }
    printf' (L " = " (I End)) ("" ++ "ans")) 42
      { substitute Printf instance for L }
    printf' (I End) ("" ++ "ans" ++ " = ") 42
      { substitute Printf instance for I }
    (\i -> printf' End ("" ++ "ans" ++ " = " ++ show i)) 42
      { apply lambda }
    printf' End ("" ++ "ans" ++ " = " ++ show 42)
      { substitute Printf instance for End }
    "" ++ "ans" ++ " = " ++ show 42
      { evaluate (++) three times }
    "ans = 42"

The compiler will perform a similar calculation, but using only types. For the arguments ("ans" and 42 in this example) it will have concrete types to work on. For the format, it will have a list of nested types that in can traverse outermost to innermost. At each step, call site context and each format element will give enough information to build the types for the corresponding nested functions, leading to a fully curried type for the types in the format. That type must match those of the arguments given.

Best of all, it’s Not At All Magical®

Tell me more about flexibility

There are several points to be made about how this printf is way more flexible, while being type-safe, than the primitive String-based counterparts provided by other programming languages.

I’ve already mentioned that formats are actually partially applied functions that can be reused. It doesn’t get more flexible than that.

If a programmer needs a new format for a simple type, all it takes is a new datatype and its Printf instance. Thus, having %c or the weird %n are very straightforward, as well as custom formatting for complex datatypes.

Having format display modifiers, as in how many spaces to use, left or right alignment, truncation or padding and whatnot, can be added by having additional Maybe values as a payload for each format type and their corresponding instances using them appropriately.

Ironically, Haskell’s default Text.Printf implementation has signature

    printf :: PrintfType r => String -> r

The restriction on typeclass PrintfType allows programmers to create custom formatting rules for their types, in a way similar to the one proposed above. However, the printing format is a (sad) String ⁵ that gets parsed at runtime and throws (sadder) exceptions on mismatches. The attentive reader should not be surprised by the polymorphic return type r, because it’s part of the variadic trick.

If you’ve read so far, you can get the (uncommented) code right here.