how to produce an n-element list with an n-ary function

{-# LANGUAGE FlexibleInstances #-}

Ever wanted to write something like this?

printThem = mapM_ putStrLn $ strings 10 False (Just 'b')

And expect it to answer like so?

10
False
Just 'b'

What should be the type of strings? Obviously it should yield a list of Strings. How many arguments should it take? Ok, in this example it takes three, but the point of this post is, how to define it to have any number of arguments we supply.

If you are a Haskell Guru, then you probably know how to do such things. I didn't until recently, so if you are not, read on! Gain experience by sharing mine.

The types of strings should look as follows:

strings :: [String]
strings :: Show a => a -> [String]
strings :: (Show a, Show b) => a -> b -> [String]
strings :: (Show a, Show b, Show c) => a -> b -> c -> [String]
...

You get the idea... strings has infinitely many types, so we probably need an extension of the Hindley-Milner type system to define it. Wich one? type classes.

strings :: AccumStrings a => a
strings = accumStrings []

When you don't know how to define a function, define another one! Here we define accumStrings and use it to define strings. Of course this is only a clever thing to do, if we know how to define accumStrings otherwise we won't be getting things done finally.

So, what is accumStrings? We can see in the definition of strings that accumStrings is a function defined in the type class AccumStrings, that we can apply it to the empty list, and that it yields a function -- in fact the strings function. The parameter a of the type class should be instantiated to any type that we might expect strings to have (we have shown the first four of them above).

Here is the definition of the type class:

class AccumStrings a
where
accumStrings :: [String] -> a

accumStrings takes a list of Strings and yields an a which has some type of the function strings. The first type of strings in the above list is just [String] so let's define an instance of AccumStrings for [String]1:

instance AccumStrings [String]
where
accumStrings = reverse

In this instance accumStrings has the type [String] -> [String] and is defined as the reverse function. Why reverse? An obvious candidate woud have been id. The idea is to accumulate (hence, the name...) all strings in the list given as first parameter. It turns out that the arguments of the strings function are accumulated in reverse order, so we reverse the accumulated list in the base instance of AccumStrings.

Thanks to this instance, we have successfully defined a strings function with the first type in the list of wanted types. Can we define the infinitely many other versions of strings with finitely many instances of AccumStrings? Yes, we can! We need one more instance.

instance (Show a, AccumStrings b) => AccumStrings (a -> b)

This instance states that when we have a type a that can be converted into a String and we have a strings function of type b, then we also have a strings function of type a -> b.

Of course the instance doesn't simply state this claim. This instance proves it by defining accumStrings of type [String] -> a -> b where b is some type of the strings function.

By considering its type, we see that in this instance accumStrings takes a list of Strings and an a that can be converted into a String and that it should yield a strings function of type b. But we already know how to build a strings function of type b: we just need to apply accumStrings to a list of Strings. But which one? We have xs of type [String] and x whose type is an instance of Show.

 where
accumStrings xs x = accumStrings (show x : xs)

By using (show x : xs) as argument to accumStrings we effectively accumulate all arguments that were given to the strings function.

Exercise

Write a function withStrings with the following types:

withStrings :: String -> [String] -> String
withStrings :: (String -> String) -> [String] -> String
withStrings :: (String -> String -> String) -> [String] -> String
...

The call withStrings f l where f is an n-ary function should consume n elements of l and pass them to f in order to compute the final result. Solution2.


  1. This instance is the reason why we need to enable FlexibleInstances when compiling this module: [String] is not a type constructor applied to type variables.

  2. Definition of withStrings:

    class WithStrings a
    where
    withStrings :: a -> [String] -> String

    instance WithStrings [Char]
    where
    withStrings s _ = s

    instance WithStrings a => WithStrings (String -> a)
    where
    withStrings f (x:xs) = withStrings (f x) xs