What does FP do well? (was How to get functional software engineering experience?)

Hal Daume III hdaume@ISI.EDU
Wed, 15 May 2002 09:24:08 -0700 (PDT)


On Wed, 15 May 2002, Karl-Filip Faxen wrote:

> On the performance (or not) of high level code: I'm working on a 
> compiler with a strong emphasis on generating good code for 

I wish you luck!

> It is going to be interesting to see how much this will give. I suspect
> that part of the performance problems of (lazy) functional languages 
> come from their encouraging the programmer to use linked data structures
> rather than arrays and similar biases, rather than just from overhead.

I tend to agree.  I keep meaning for experimental purposes to define a
list type called AList or something which is syntactically identical to
lists (i.e., you can use the familiar (:) and [] operators/sugar), but
gets preprocessed out as actually being implemented with an array with a
pointer to the "current" element.  Especially if we use unboxed types for
such a thing, I imagine that on many applications this would give a boost
in performance.

I'm almost "mad" at the prelude for including so many functions which
basically treat lists in ways they weren't meant, for instance, lookup,
!!, etc.  lookup is more suited to FiniteMap and !! is more suited to
arrays.  However, the syntactic sugar supporting lists is *so* strong that
I find myself often using them because it's much easier to write functions
using (:) and [] and especially [a,b,c] notation than it is to write
functions using `addToFM` and emptyFM and the like.

Perhaps if I (or someone else) gets around to writing a List->Array
converter, I (or they) could apply some hueristics to see which lists
(i.e., ones with lots of !!s or backwards traversals) should be
implemented as Arrays and which (i.e., ones with lots of lookups) should
be implemented as FiniteMaps*...

Just some thoughts...

 - Hal

* I believe such things aren't unheard of -- I don't know the name of it,
but I know one of my friends up at MS Redmond was working on compilation
where the compiler would determine optimal data structures to use by
examining code...with typeclasses and all, I think this would be a very
natural thing to see in Haskell (or a Haskell derivative).