Functors: an intuition

Today, I want to give an example of a kind of abstraction sorely missing from “conventional” programming languages.  This post is only a tiny bit “what is a functor?” It’s more about “when are functors useful?”

Suppose we’re writing a parser. So we write the simple, obvious unit of abstraction: a function that parses a file and produces an output that’s either an error message or the corresponding syntax tree.  We have a type like so:

parse :: {-File-} Handle -> IO (Either String AST)

But this isn’t actually good abstraction, is it? Let’s break it up a bit…

parseFile :: Handle -> IO (Either String AST)
parse :: String -> Either String AST

(This is one of the hard things to hammer into intro to programming students’ heads. It always seems to take a while to get them to understand why writing a function that just computes something might be more useful than one coupled to a particular interaction. And it really pains me when I see this kind of crap baked into standard APIs…)

But, now suppose we have TWO different, convertible forms of AST.  AST1 and AST2. The user might be interested in either one, and will potentially want to convert back and forth. For those questioning the sanity of this, imagine that AST1 is a faithful implementation of the horrifying XML DOM API, while AST2 is a nicer version to work with, but doesn’t have native XPath queries.

So things we definitely have:

parse1 :: String -> Either String AST1
convert1to2 :: AST1 -> AST2
convert2to1 :: AST2 -> AST1

And something we’d like to have, for the user’s convenience:

parse2 :: String -> Either String AST2

How can we implement parse2?  Ideally, we’d like to reuse as much code as possible, without rewriting, copy/pasting, or otherwise writing unnecessary code.

The problem we run into is there is no simple application or composition of functions that allows us to write parse2 in terms of parse1 and convert1to2. Without functors, that is. The problem is that the data to which we want to apply the convert function is wrapped up in an ‘Either’ because we might have had a parse error instead. With functors, though:

parse2 str = fmap convert1to2 $ parse1 str

Easy as pie!  Intuitively, functors allow us to apply a function to the data wrapped up by another appropriate data structure.

And Control.Applicative (despite the source of this operator, do not confuse what I’m talking about with applicative functors; that is something more!) in Haskell even gives us an operator to do this more directly:

parse2 str = convert1to2 <$> parse1 str

And, while I’m not especially a fan of “point-free style,” (variable names are fantastic documentation, okay?) I should note here the relationship to function composition, in addition to function application already shown.  Here is another perfectly equivalent implementation of parse2:

parse2 = fmap convert1to2 . parse1

Oddly enough there doesn’t seem to be a <.> operator that’s analogous to what we did above with $. That sort of strikes me as strange. (Perhaps a commenter who knows more of Haskell will set me straight.) But,  another implementation analogous to what we changed before:

(<.>) :: (Functor f) => (a -> b) -> (c -> f a) -> (c -> f b)
(<.>) a b = fmap a . b

parse2 = convert1to2 <.> parse1

And here the type of the operator <.> directly states the intuition we were describing earlier: we’re trying to do function application “under” the wrapper type of the result of another function.

My motivation for writing this post? I’m writing this code in Java. No functors.

Fiddlesticks!

Advertisements
This entry was posted in Typing Tidbits and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s