Discoverability of Functional Languages' Functions

Question

I'm currently learning Clojure and it's been very intellectually stimulating, but I've run into many situations where I can program a solution to a problem (on 4Clojure for example), but find the other solutions to use a large breadth of other functions that I am totally unaware of.

Besides reading through all of the documentation, or at least all of the name spaces, is there a solution to discoverability in functional programming? The corollary to this question would be if there is a solution to not duplicating effort between people in a software engineering team. Is there a way that I can discover if I need a new function, or if my team mate has already implemented it? Is there a way for her to discover my functions? That is, without some sort of overarching functional decomposition of the entire system we are building.

Is there an ontology or mapping of functions that can help me discover new functions based on use. For example, a way to classify foldl and foldr so that I can easily discover that foldl' exists (or could exist) and foldr' doesn't need to exist? Some way I can see a "dark area" of the map and know that there could be a function there and what it would do.

Is there a database somewhere of problems or data types and functions addressing them?

Answer 1

Types! :D

A good start according to many 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 Int 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 -> String) -> String -> String

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.

Types :(

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 Text values 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.

Conclusion

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 String -> b -> String 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.