[Haskell-cafe] Mutable arrays

[Jeff φ]

On Feb 6, 2008 1:18 AM, Jonathan Cast <jonathanccast at fastmail.fm> wrote:

>   On 5 Feb 2008, at 10:14 PM, Jeff φ wrote:
>
>
>
> On Feb 5, 2008 4:58 PM, Chaddaï Fouché <chaddai.fouche at gmail.com> wrote:
>
> > 2008/2/5, Jeff φ <jeff1.61803 at gmail.com>:
> > > 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.
> > >
> >
> > You could absolutely write something like that in Haskell, but as some
> > have pointed out, this is probably _not a Good Idea_, even though it
> > works in your particular case, the array could be modified between the
> > time you get the lazy list and the time you actually read it... And
> > there's no way to insure it's not happening in Haskell, and I strongly
> > doubt there is in Concurrent Clean, could you confirm ?
> >
>  Concurrent Clean can handle this in a safe way.  Here's a code snippet
> for normalize_2D_ary from ArrayTest.icl:
>
> uToList_2D :: *(a u:(b c)) -> (.[c],*(a u:(b c))) | Array a (b c) & Array
> b c
> map_in_place_2d_arr :: (a -> a) *(b *(c a)) -> *(b *(c a)) | Array b (c a)
> & Array c a
> normalize_2D_ary :: *(a *(b c)) -> *(a *(b c)) | Array a (b c) & Array b c
> & / c & Ord c
> normalize_2D_ary ary =
>     let (lst,ary2) = uToList_2D ary
>         max_elem = foldl1 max lst
>     in  map_in_place_2d_arr (\ x -> x / max_elem) ary2
> uToList_2D takes a unique array, ary, and returns a tuple containing a
> list of the array elements and a "new" array, ary2.  uToList_2D does not
> modify ary, but Clean's type system forces any function that accesses a
> unique array to thread the array through and return a "new" array.  Under
> the hood the "new" array actually uses the same memory storage as the
> original array.  So, it is effecient.  Threading the array serializes access
> insuring the array won't be modified until the list is complete.
>
>
> I'm confused --- does uToList_2D return the head of the list before or
> after it finishes reading the array?  If before, then I don't see how the
> type system prevents me from modifying the array before I finish examining
> the list, as you claim.  If after, then the list isn't truly lazy.
>

uToList_2D can return the head of the list before it finishes reading the
array.  I could modify the code so that it is ambiguous whether the array is
modified before the list processing is finished.

normalize_2D_ary ary =
    let (lst,ary2) = uToList_2D ary
        max_elem = foldl1 max lst
     in  map_in_place_2d_arr (\ x -> x / max_elem) ary  // I changed ary2 to
ary

However, the type system will generate an error with this code because
ary is no longer unique because it is referenced in two expressions.  Clean
produces this error message:

Uniqueness error [ArrayTest.icl,55,normalize_2D_ary]: "ary" demanded
attribute cannot be offered by shared object

I should mention that a problem with the code I've shown is that it is very
sensitive to the order in which the expression graph is evaluated.  Simple
changes can cause lst to become strict and the program to run out of heap.
By the way, Clean has it's share of rough edges.  The reason I'm hanging out
on Haskell-Cafe is because I'm trying to get away from those rough edges.
But, I am missing Clean's uniqueness types.  I'm starting to see Haskell's
unsafe functions as a blunt work around that could be fixed elegantly and
safely by implementing uniqueness types.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080206/e66ca3eb/attachment.htm