> I'm relatively new to Haskell, but have spent a fair amount of time programming
> in SML and Scheme. Up to this point, I've been thrilled by the extras Haskell
> offers and fun one can have with lazy evaluation, but now I'm stuck.
>
> How would a seasoned Haskell programmer create and EFFICIENTLY incrementally
> modify large highly interlinked data-structures such as you find commonly in
> most graphics programs.
> ...
Hi,
You've already gotten two responses concerning this message, and I agree with
both of them, but they neglected to mention the most obvious solution to your
problem which is to use a state monad --- this will give you the same abilities
in Haskell as refs and updates do in SML. If you don't know how to use monads,
reply again and I will give you some references with simple explanations
(mostly papers by Phil Wadler and/or Simon Peyton Jones).
There are certain problems which cannot only be solved "efficiently" in a
functional language (and I'm not sure if your example is one of them); when you
encounter one, you need to think a little bit harder about what it is you want
to do. If you use monads, you can get destructive update, etc., but it comes
at a price because the code must now be single-threaded. This means that, for
instance, you will have more problems integrating it into a concurrent program
and reusing parts of it for other purposes. Also, in the case of monads,
the types of the functions in your interface will change and you'll need
to thread it through the IO monad which involves some contortions in medium-size
programs.
On the other hand, you might be planning to use the buffer in a persistent way,
so that different parts of the program will need to access different versions
of it simultaneously. In that case, you should take a look at Okasaki's work,
as someone suggested. I don't think he has published anything concerning
ring buffers, but I know he has a paper on double-ended queues.
The bottom line, though, is that, because Haskell is statically typed and
purely functional, it will force you to make things explicit more often than
an imperative language or a semi-imperative language like SML. Another way
to say it is that, in Haskell, you have to "add more static information to
a program" than in most other languages. This has advantages in the long run,
but sometimes you just want to say "do it this way and trust me" --- technically
speaking, you want to be able to make a claim (construct a type) without
justifying it by a proof (a well typed program). Unfortunately, that isn't
really an option in Haskell.
So, you need to rethink what you want to use the DbLink module for. It might
be the case that you can decompose it into smaller, more general parts. Or,
conversely, you might be able to specialize it in some way. In my opinion,
this is a better solution than using monads --- when possible --- and it may
be more efficient than using a persistent data structure. Frankly, my first
impression is that a doubly-linked _anything_ is not a very functional data
structure because its "semantics" depends on the order in which you traverse
it. In an imperative language, this sort of structure is common, because
one needs to encode a lot of information in the form of dependencies, but in
a functional language it will create problems for obvious reasons.
Ah, BTW, I just noticed that you said your main goal was to modify a large
interlinked data structure like in a graphics application. OK, then you
will mostly want to ignore what I have said and program that part in C
and link it in as foreign code. :) That will require using monads anyways.
To be perfectly honest, Haskell is not good in this sort of application area
(large quantities of low-level data). It's partly a failing of Haskell, but
it is more because of the operating system which is completely biased towards
imperative languages and hence forces client programs to do practically
everything even though it could reasonably provide generic algorithms to
perform the dirty work. If it's really graphics that you are doing and you
are dead set on doing it in Haskell, I suggest you look at the existing graphics
packages like Haggis or Fudgets or maybe even TkGofer. I think the first two
are linked from haskell.org.
-- FC
