Home » forums » LtU Forum

Can one avoid monads?

From an aside in a paper on functional graph algorithms, using monads means you have given up on a functional approach. Unfortunately, the procedural approach might be ugly or confusing and we are left still pining for a functional solution. When and how could we use functional approaches and avoid monadic / procedural? What are the limits of our abilities with functional programming?

By raould at 2005-11-08 23:32 | LtU Forum | previous forum topic | next forum topic | other blogs | 7528 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Minimal data dependencies?

In this particular context, maybe the "functionalness" of an algorithm is a measurement of how minimal the data dependencies are. Code written in the imperative style takes data dependencies to the extreme -- there is an implicit "state-of-the-world" parameter threaded through every statement -- while functional code tries to minimise those dependencies.

Monads aren't necessarily non-functional; they just make it easy to handle repetetive data dependence paths. In a simple interactive shell, for example, the I/O operations obviously need to be strictly sequenced and so I don't think it's unfunctional to thread them through the I/O monad. But for graph traversal algorithms, it's seems relatively clear that the commonly-known imperative algorithms impose more than the minimal set of data dependencies.

So I guess I'm now left with the problem of figuring out the minimal set of data dependencies for a given problem, which doesn't sound any easier :)

By Kannan Goundan at Wed, 2005-11-09 05:43 | login or register to post comments

Perhaps I'm missing something

Perhaps I'm missing something, but I have a hard time with the idea that monads are not functional. That seems to me like saying function composition isn't functional. Are you objecting to the use of monads to sequence operations?

I'm by no means the wisest person here; in fact, I'm a mostly clueless lurker. Can I buy a vowel?

By jimdesu at Wed, 2005-11-09 17:35 | login or register to post comments

-O-A-

Monads let you thread state through a program in the same sort of way as in imperative languages, without having to explicitly pass the state around as you would normally have to do in a pure functional situation. So, especially with Haskell's syntactic sugar (do), you end up with code that at least looks imperative. Even without the sugar, if you squint you can see that imperative look, with the bind operator being seen as equivalent to a statement separator (e.g. semicolon) in imperative languages, but doing the work of transmitting the non-local state from one statement to the next.

All I've described so far is something that tends to look like imperative style, it doesn't necessarily involve anything that's not purely functional. However, of course, the same features of monads can be used to encapsulate real side effects, like I/O and destructive update, and interact functionally with them. Once you do that, a kind of line has been crossed, and you're using the monad to help draw the line clearly, and keep the impure stuff clearly separated, so the rest of the program still obeys functional laws.

In the case of the example in the paper, it's common in graph algorithms to cross that line, and use something like the ST (state transformation) monad to e.g. encapsulate destructive update of an array of marks to track the nodes you've dealt with. This doesn't have to be done destructively, but there are obvious space & time complexity issues in copying an array of marks every time you want to update one of the marks. So, to compete with the complexity of an imperative equivalent, a functional graph algorithm ends up not only using imperative style via a monad, but also using the monad to encapsulate an impure, destructive update.

The paper addresses the question of whether this can be done in a more elegant way, which is answered by representing graphs as an inductive data type, avoiding the need to track nodes with an array of marks.

A paper which discusses some of the underlying issues is Monads and Effects, e.g. in section 5.2, "Imperative Algorithms". [Edit: although I think I may have the older, non-revised version, so exact details may vary.]

By Anton van Straaten at Wed, 2005-11-09 18:31 | login or register to post comments

Zipper Candidate?

Once you have a graph represented by an inductive data type, I wonder if it doesn't become amenable to manipulation by a Zipper, with the attendant maximal sharing properties.

By Paul Snively at Wed, 2005-11-09 19:47 | login or register to post comments

Funny you should mention that...

Dominic Fox and I have been discussing just such a thing, for a variety of uses.

By shapr at Wed, 2005-11-09 19:59 | login or register to post comments

Metamorphic Programming

Mildly interesting, you may want to look at metamorphic programming (google should work, otherwise look for "How to hide your state monad"). I think it's also by Erwig so you shouldn't need to look far.

As another note, even when using monads, even to do very imperative things, it is often possible to provide a rather high-level interface that still feels functional. Metamorphic programming provides one example/approach, but there are others.

By Derek Elkins at Thu, 2005-11-10 18:59 | login or register to post comments