Is there a functional algorithm that is faster than imperative?

Question

I am looking for an algorithm (or an argument of such an algorithm) in a functional style that is faster than imperative.

I like the functional code because it is expressive and basically easier to read than real pendants. But I also know that this expressiveness can be worth the overhead. Not always due to methods like tail recursion, but often they are slower.

During programming, I don’t think about the time it takes to execute functional code, because these days PCs are very fast and development time is more expensive than runtime. In addition, for me, readability is more important than performance. However, my programs are fast enough, so I rarely have to solve the problem for real.

There are some algorithms that in practice should be implemented in an imperative style (for example, sorting algorithms), otherwise in most cases they are too slow or require a lot of memory. Unlike methods such as pattern matching, an entire program, such as a parser written in a functional language, can be much faster than written in an imperative language because of the ability of compilers to optimize code.

But are there any algorithms that are faster in a functional style or are there options for customizing the arguments of such an algorithm?

Answer 1

Simple reasoning. I do not vouch for the terminology, but it seems to make sense.

• A functional program that must be executed must be converted to a certain set of machine instructions.
• All cars (I heard) are required.
• Thus, for each functional program there is an imperative program (roughly speaking, in assembly language) equivalent to it.

So, you probably have to be content with "expressiveness" until we get "functional computers."

Answer 2

Short answer:

Everything that can be easily done parallel, because without side effects it will be faster on a multi-core processor.

QuickSort, for example, scales quite well when used with immutable collections: http://en.wikipedia.org/wiki/Quicksort#Parallelization

All the rest are equal, if you have two algorithms that can reasonably be described as equivalent, except that for pure functions immutable data are used, and in the second, mutations are in place, then the first algorithm will be scaled to several with ease.

Perhaps even your programming language can perform this optimization for you, like the scalaCL plugin, which will compile code to run on your GPU. (I'm curious now if SIMD instructions make this a "functional" processor)

Thus, when using parallel hardware, the first algorithm will work better, and the more cores you have, the greater the difference.

Answer 3

FWIW has purely functional data structures that benefit from functional programming.

There is also a good book by Chris Okasaki on purely functional data structures that presents data structures in terms of functional languages.

Another interesting article announcing Intel Concurrent Collections for Haskell 0.1 about parallel programming, they note:

Well, it happens that the notion of step in CnC is a pure function . A step does nothing but read its input and create tags and elements as output. This design was chosen to bring CnC into that elusive but wonderful place called deterministic concurrency. The decision had nothing to do with language preferences. (And indeed, the primary CnC implementations are for C ++ and Java.)

And yet, what a wonderful match Haskell and CnC will get! Haskell is the only main language where we can (1) ensure that steps are clean and (2) directly recognize (and use!) The fact that both steps and graph execution are clean.

Add to this the fact that Haskell is superbly extensible and, therefore, the CnC “library” can feel almost like a subject-oriented language.

This does not mean performance - they promise to discuss some implementation details and performance in future publications - but Haskell, with its "cleanliness", fits perfectly into parallel programming.

Answer 4

It can be argued that all programs are reduced to machine codes.

So, if I delete the machine code (of the imperative program) and configure the assembler, I might possibly get a faster program. Or I could come up with an "assembler algorithm" that uses a specific processor feature, and therefore it is really faster than the imperative language version.

Does this situation lead to the conclusion that we should use assembler everywhere? No, we decided to use imperative languages ​​because they are less bulky. We write fragments in assembler because we really need to.

Ideally, we should also use FP algorithms because they are less cumbersome for code and use imperative code when we really need to.

Answer 5

Well, I think you wanted to ask if there is an implementation of an algorithm in a functional programming language that is faster than another implementation of the same algorithm, but in an imperative language. By “faster,” I mean that it works better in terms of runtime or memory size on some inputs according to some measurements that we consider trustworthy.

I do not exclude this possibility. :)

Answer 6

To clarify Yasir Arsanukaev’s answer, purely functional data structures can be faster than mutable data structures in some situations because they separate pieces of their structure. Thus, in places where you may have to copy an entire array or list in an imperative language, where you can leave with a partial copy, because you can change (and copy) only a small part of the data structure. Lists in functional languages ​​are similar to the following: multiple lists can have the same tail, since nothing can be changed. (This can be done in imperative languages, but usually it is not, because in an imperative paradigm people are usually not used to talking about immutable data.)

In addition, lazy evaluation of functional languages ​​(in particular, Haskell, which is lazy by default) can also be very beneficial, since it can eliminate code execution when the results of the code are not actually used. (However, you can be very careful not to run this code primarily in imperative languages.)