[Haskell-cafe] Mutable arrays

[Luke Palmer]

On Feb 5, 2008 4:36 PM, Jeff φ <jeff1.61803 at gmail.com> wrote:
>
> I want to say thanks to everyone who responded to my mutable array post.
> I'm going to work through and experiment with all the comments people
> posted.  It might take me a while.
>
> Luke Palmer wrote:
> > Hmm, how big is the array?   If it's pretty big, that's
> > understandable.  Frankly, it's because foldl sucks: I have never seen
> > a reason to use it.  You should be using the strict variant foldl'
> > here.  (I don't think there is a foldl1').  And that will get rid of
> > your big function calc_max_2d_elem.
> >
>
> I should have mentioned that I'm working with a 2D array that is 1024 x
> 1024.  Eventually, this code will have to work with arrays that are much
> larger.  (For fun I write image processing and fractal "art" programs.)  I
> replaced the foldl1 with foldl1'.  Unfortunately, I still get a stack
> overflow.

Right, that was my mistake.  The reason is right here:

> Chaddaï Fouché wrote:
>
> >
> > Sorry but none of those propositions change the heart of the problem :
> > the list of elements is totally produced before she can be consumed
> > due to the strict monadic (IO or ST) nature of getElems. Thus you get
> > an extraordinary waste of memory as well as resources...
>
>
>
> This is interesting.  I've been programming in Concurrent Clean for a while.
> Instead of monads, Clean supports unique types for mutable arrays and IO.
> In Clean, I can write code that iterates through a mutable array by
> converting it to a lazy list.  This is convenient because I can use all the
> nice list processing functions that are available.
>
> Changing the subject slightly, I once wrote code in Concurrent Clean that
> filtered a file that was larger than the available memory on my PC.  I did
> this by creating a function that returned the contents of the original file
> as a lazy list.  Then, I created functions to process the list and write the
> processed list to a results file.  The code was not imperative at all.  The
> function that wrote the results file forced the evaluation of the lazy list.
> As the lazy list was consumed, the contents of the original file were read.
> Is this possible with Monads in Haskell?

Yes, using hGetContents, which is considered bad practice by many
people here.  The problem is that hGetContents breaks referential
transparency, and I suspect that whatever Clean does to lazily read
files also does (though I can't be sure, I haven't looked in any
detail at uniqueness types).  That is, the contents of the returned
list depend on when you read it, which is not allowed in a
referentially transparent language.

The same applies to your problem.  getElems cannot return a lazy list
of elements*, because what if the array were changed between the point
that you did the getElems and the point you required the element.  So
it seems that actually specifying the order of evaluation using an
imperative-style loop is the only pure way to do this.

* Well, it could, but it would require some cleverness like
copy-on-write logic under the hood.

Luke