Two Wrongs

(don't make a right)

Discoverability of Functions in Functional Languages

by ~kqr

A problem in programming in general, and functional programming in particular, is that of finding the functions that do what you want. Amidst 20 modules with 50 functions each, how do you know if the function you want exists or not? It's like the metaphorical needle in a haystack, except you don't even know if the needle exists!

Being able to find the function you need, however, is important. If you fail to find the existing function, not only do you have to waste time re-writing it – you also have to waste time when you want to change it, because you will have to change both functions.

The problem is one of intentions. The question you want to ask is, "Has a programmer previously had the same intentions as I have now?" We know how to search for implementations (just grep the source code!) but how do we find intentions in a code base?


A good start is being able to talk about types. In the Haskell world, they even have a type-based search engine. Say, for example, you have a value of type Maybe Integer and you want to convert it to a string if there is a value there, otherwise supply the empty string. In type terms, that is a function

f' :: Maybe Integer -> (Integer -> Text) -> Text -> Text

It takes three arguments – a Maybe value, a conversion function, a default value, and it will return a string. If we make this more general, we might arrive at something like

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

By using this as a query for the type-based search engine, we will find that there is indeed a function

maybe :: b -> (a -> b) -> Maybe a -> b

in the Data.Maybe library which does what we want.


Granted, this isn't perfect. One problem is that you can express the same operation at varying levels of abstraction. Imagine instead, for example, that we have a list of integers, which we want to convert to strings and then concatenate. A first attempt at the type signature results in something along the lines of

g' :: [Int] -> (Int -> Text) -> Text

If we search for this, we don't find a clear result. It might not be immediately clear how to make this more abstract. Maybe it should be something like this?

g :: [a] -> (a -> b) -> ([b] -> b) -> b

(in other words, given a list of a, a conversion function, and a function that tells you how to concatenate bs, return a single b.) Searching for this yields a variety of results, all of which are completely irrelevant to our application.

The key insight here, which doesn't come with reasoning but with experience and knowledge, is that we really want something that already knows how to concatenate itself. We want a Monoid operating function. Based on that knowledge, we are much more likely to find

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

– exactly what we were looking for.


So types are not a perfect system, but they really do help. The reason they work is because they attempt to encode the intention of the programmer. What you are really asking for is a sort of database of intentions, instead of implementations (as source code is.)

Better type systems can only make this process smoother by allowing the programmer to encode their intentions better. But they will always require discipline, such as using the most general type available.

The case for more general types is that more general types restrict the number of intentions that fall under the same type. A function with type a -> b -> a can, in absence of context, only do one thing – ignore its second argument and return the first one. On the other hand, a function of type Text -> Integer -> Text can do pretty much whatever it wants, because it knows how to construct a value of its own return type. If a function does not know its return type, it can only construct it by using the arguments it gets.

If you enjoyed this article, you might like others tagged with