[Haskell-cafe] Copy on read

Matthew Naylor mfn-haskell-cafe at cs.york.ac.uk
Tue May 13 04:16:23 EDT 2008

Hi Andrew,

my probably dodgy reason for mentioning deforestation is that sharing
of intermediate values is a major stumbling block; code that uses data
linearly is possibly well suited for deforesting.  See Frankau's SASL
for a language that deforests all lists simply by not letting you copy
them!  (IIRC there is another constraint that forbids accumulating
parameters too.)

> Similarly, there are recursion patterns for which fusion isn't very 
> easy.

Yep, I suspect you're right.

> That's why most array-based code is explicitly in-place.  wouldn't
> it be nice if it didn't have to be?

I agree.  As an aside, DiffArray looks quite nice:


``if a diff array is used in a single-threaded style, ..., a!i takes
O(1) time and a//d takes O(length d).''

Notice the use of "seq" in 2nd example to enforce a kind of
single-threaded behaviour.  Seems nasty!  I wonder if this could be
avoided by providing a (*!*) such that

  arr *!* i = seq x (arr, x)
    where x = arr ! i

It returns a new array which the programmer should use if they want
single-threaded behaviour.


More information about the Haskell-Cafe mailing list