[zby]

The problem with verbs is that they are black boxes. With objects you can subclass and override methods - do stuff like the Universal Design Pattern - basing something on prototypes that you tweak here and there. Functions you can only apply, objects have parts that have names.

[tikhonj]

This is why the fundamental operation in the land of the verbs is composition: do this then do that. It turns out that composition is such a useful idea that we want more of it, which is where categories, monads and arrows come in.

The most obvious type of composition for functions is, well, function composition. In math we define the composition of functions f and g as f(g(x)), usually written as f ∘ g. We can write this directly in Haskell pretty trivially:

    f ∘ g = λ x → f (g x)

And, in fact, you will see this operator everywhere in Haskell, except most people are too boring for ∘ and use the ASCII . instead. (Weak.)

Also, a cool aside. I just realized that Haskell syntax is even more regular than I had assumed. In general, in Haskell, you can rewrite expressions like

    f x = λ y → ...

as

    f x y = ...

Turns out this even works for operators! So you could actually write the above composition as:

    (f ∘ g) x = f (g x)

I think that's pretty cool, but maybe I'm just easily impressed.

The idea of a category just takes the ∘ operator and generalizes it to other types, letting you use it for things that aren't normal functions. As I mentioned above, these things could be arrows or functions involving monads, but they can really be anything at all. This is, coincidentally, one of the main reasons we care about category theory: at its very heart, category theory is the study of composition. (Okay, I'm probably really misrepresenting the mathematics here, but that's how it works out for programmers :).)

There are also other things you can do with functions. In particular, you can map functions to other functions. And this is, indeed, what the well-known map function does. Normally, you think of the map function as taking a function and a list and then mapping that function over the list. In Haskell, this has the following type:

    map :: (α → β) → [α] → [β]

However, I posit that map actually does something rather different and more subtle--it takes normal functions and produces list functions. In fact, the type signature is better thought of this way:

    map :: (α → β) → ([α] → [β])

(This is why currying is so great--both interpretations are equally valid!) So, in fact, we can think of the list type as a way of mapping existing types (like a) to new types (like [a]) and mapping existing functions (like (α → β)) to new functions (like ([α] → [β])).

This operation also turns out to be exceptionally useful. So useful, in fact, that it's the basis for one of the most fundamental concepts--the functor. In fact, a functor (in Haskell) is simply any type with a function analogous to the list type's map. For historical reasons, we call this function fmap and it has the following type:

    fmap :: Functor f => (α → β) → (f α → f β)

All this says is that, given a functor type, we can map normal functions to functions over the functor. Another way of thinking about this is that a functor is roughly like a function at the type level.

Of course, we have other ways to transform functions as well; fmap is just the simplest. Similarly, we have other ways to compose functions, function composition is just the simplest.

So the most important idea is that we actually have a fairly wide variety of operations over functions. We can sling them around as easily as any other data type, really.

We move forward by combining functions rather than trying to modify them. Instead of starting with a composite piece and working inwards, we start with the basic building blocks (functions and types) and work outwards, combining them in different ways to get a composite program.

It's a difference in philosophy, and I think a rather important one.

[zby]

I am happy with you with all that mathy stuff and I agree that it is cool - but it does not address my point which was that functions are black boxes. Once you have 'f' you can compose it whatever you want - but you cannot change its parts - ala universal design pattern (yet another too long Yegge rant: http://steve-yegge.blogspot.com/2008/10/universal-design-pat...).

Sure composing can somehow work for these case, just like a Turing Machine would work, after all it is all equivalent - but we really tend to think about reality in terms of prototypes - a pony is like a horse only small, a goose is like a duck only bigger and white, etc. - this is what makes this inheritance and overriding so convenient. And if you argue that it is not as clean as pure function composition, that it can quickly get into a tangled mass where pure functions are pure and easy to reason about (but it is all equivalent - so you can actually write the same tangled mess code in a pure functional language - by carrying the state around like the burlaks on Volga) - then yeah I agree - engineering is always about trade-offs. I am only trying to explain one of the sides of that trade off.

[sixbrx]

Why would you need to change its parts, it can be parameterized over the parts that change, by passing in other functions as arguments. It's also cheap conceptually and syntactically to create new ones, if an existing one doesn't fit the bill.

[zby]

I don't really know - I've never extensively programmed in functional way (beside studies) - but the point about overriding is that you do it post-hoc you get a library class and you change it. The original author does not need to imagine all the ways you'd like to modify it - and yet by doing some basic structural design and putting stuff into methods he gives you the opportunity to override. Also I imagine that this level of parametrizing - that is if every function in a package is a parameter to another function in that package then it gets messy, but with subclassing/overriding you can change any method and it changes for all other methods.

[realitygrill]

Your explanations of Haskell concepts have been impressing me lately. Do you write elsewhere?

[metaphorm]

of course he does. every Haskell programmer has a blog. some have several.

[tikhonj]

I keep on meaning to start a blog, but haven't gotten around to it yet :/. I even have some half-finished articles lying around.

One of these days...

[fmstephe]

I am enjoying watching this comment grow. I hit refresh every five minutes to get the next installment :)

[andolanra]

There is a standard technique in functional programming called 'defunctionalization'[1] which replaces functions with a data structure that can be poked or prodded or examined. It's usually implemented as a compilation technique, but can be done manually, as in Olivier Danvy's system for transforming an interpreter for a language into an abstract machine for the same language. What you are doing is, in effect, 'nominalizing' your verbs, to use Yegge's terminology. ([1] also acknowledges that it is inverse to the Church encoding of data structures, which 'verbifies' your nouns.)

[1]: http://www.kennknowles.com/blog/2008/05/24/what-is-defunctio...

[crntaylor]

That's why functional aficionados love to work with higher-order functions!

[Roboprog]

You can fake objects and subclassing with closures, in addition to making it trivial to implement the "one method interface" (aka "functor").

http://roboprogs.com/devel/2010.06.html (example using a subset of JavaScript, rather than a language likely to be unfamiliar to most)

TODO: edit example someday to get rid of "useless use of local variables" (in place of original formal parameters), fix where I call the outer functions "closures" instead of the inner functions.

Of course, it's easier to work with both real objects AND real functions/closures/lambdas -- I can use a hammer and a screwdriver :-)

[daxelrod]

I always thought this koan summed up this concept best: http://stackoverflow.com/a/501053/580947

[seanmcdirmid]

> Of course, it's easier to work with both real objects AND real functions/closures/lambdas -- I can use a hammer and a screwdriver :-)

But do you hit your screwdriver with the hammer, or do you twist your hammer with the screwdriver? This can be a real problem if one programs in Scala.

[Roboprog]

Not too often, but I find myself using the screwdriver for a chisel, and the hammer for a plumb bob.

I probably need to buy more tools :-)

[ajuc]

You can pass functions as arguments to functions, so verbs, too, can have parts.

[zby]

That is interesting proposal (together with the higher order functions etc) - the problem I see with that is that normally you have many more methods and fields then you normally pass arguments to functions. Maybe with some aggregating.

[ajuc]

And I think it's one of the problems with OOP - it's too easy to create class that have 20 methods and 10 parameters, and too hard to refactor it into smaller classes once you have it in such state. You start with simple - domain related classes that have a few methods and related state. Then real life happens and you end up with such monstrocities.

It's much less convenient to work with function that takes 30 arguments, so nobody write such functions - you just divide it into smaller parts. And it's much easier to refactor when most of the code don't need to deal with internal state, and when you can use closures.