Block-wise lazy sequences in Haskell
I want to have a data structure like Data.ByteString.Lazy, that is block-wise lazy, but polymorphic. I could use a lazy list of unboxed arrays (UArray) but the documentation says, that the element types are restricted. But I will need (strict) pairs of Double and the like as elements. It seems that I need generalized instances in order to use these arrays. I thought it must be possible to define an unboxed array type with Storable elements. I cannot find such a type in the standard libraries. Further on, I wonder why pairs are not instances of Storable.
Henning Thielemann wrote:
I thought it must be possible to define an unboxed array type with Storable elements.
Yes, this just hasn't been done. There would be a few potentially tricky corners, of course; Storable instances are not required to be fixed in size, though all the precanned instances are. Using arbitrary Storable instances would make it necessary to scan an array linearly to get to a particular element, defeating one of the advantages of e.g. ByteStrings.
Further on, I wonder why pairs are not instances of Storable.
I think it hasn't been done simply because it hasn't been done. The
upcoming fusion-based list rewrite might hold some promise for relieving
the pressure for this kind of work.
On Wed, 5 Sep 2007, Bryan O'Sullivan wrote:
Henning Thielemann wrote:
I thought it must be possible to define an unboxed array type with Storable elements.
Yes, this just hasn't been done. There would be a few potentially tricky corners, of course; Storable instances are not required to be fixed in size, though all the precanned instances are.
I see. This could be solved with a StorableFixedSize class. But it hasn't been done, too, I assume.
Using arbitrary Storable instances would make it necessary to scan an array linearly to get to a particular element, defeating one of the advantages of e.g. ByteStrings.
I doubt that someone is interested in such an array implementation.
Further on, I wonder why pairs are not instances of Storable.
I think it hasn't been done simply because it hasn't been done.
Maybe also because of the issue of varying sizes?
Bryan O'Sullivan wrote:
Henning Thielemann wrote:
I thought it must be possible to define an unboxed array type with Storable elements.
Yes, this just hasn't been done. There would be a few potentially tricky corners, of course; Storable instances are not required to be fixed in size,
They are (indirectly), see http://www.haskell.org/ghc/docs/latest/html/libraries/base/Foreign-Storable.... sizeOf :: a -> Int Computes the storage requirements (in bytes) of the argument. The value of the argument is not used. and http://www.cse.unsw.edu.au/~chak/haskell/ffi/ffi/ffise5.html#x8-320005.7 sizeOf :: Storable a => a -> Int alignment :: Storable a => a -> Int The function sizeOf computes the storage requirements (in bytes) of the argument, andalignment computes the alignment constraint of the argument. An alignment constraint x is fulfilled by any address divisible by x. Both functions do not evaluate their argument, but compute the result on the basis of the type of the argument alone. [...] Cheers Ben
Can someone explain me, why there are arrays with mutable but boxed elements? I thought that boxing is only needed for lazy evaluation. However if I access an element of an array that is the result of a sequence of in-place updates, all updates must be executed in order to get the final value. That is, the first access to an element of such an array evaluates all elements of the array - which sounds for me like eager evaluation. So what's the reason for boxes in mutable arrays? Maybe I misunderstand the Box concept, and Box means just Pointer. It would make sense to store pointers in an array if the size of the elements vary.
On Wed, 2007-09-05 at 20:37 +0200, Henning Thielemann wrote:
Can someone explain me, why there are arrays with mutable but boxed elements? I thought that boxing is only needed for lazy evaluation. However if I access an element of an array that is the result of a sequence of in-place updates, all updates must be executed in order to get the final value. That is, the first access to an element of such an array evaluates all elements of the array
No. A mutable array is mutable only in a monad (IO or ST), and updates happen within that monad. But they don't evaluate the values in the array at all, either the old value or the new one. They just move pointers to expressions in the heap around. jcc
On Wed, 5 Sep 2007, Jonathan Cast wrote:
On Wed, 2007-09-05 at 20:37 +0200, Henning Thielemann wrote:
Can someone explain me, why there are arrays with mutable but boxed elements? I thought that boxing is only needed for lazy evaluation. However if I access an element of an array that is the result of a sequence of in-place updates, all updates must be executed in order to get the final value. That is, the first access to an element of such an array evaluates all elements of the array
I was imprecise here. With 'access' I meant an access to the array outside of the ST monad, that is on the result of runSTArray.
No. A mutable array is mutable only in a monad (IO or ST), and updates happen within that monad. But they don't evaluate the values in the array at all, either the old value or the new one. They just move pointers to expressions in the heap around.
I'll see, if I understand it. do writeArray arr 0 2 x <- readArray arr 0 writeArray arr 0 (x+x) If 'arr' is an STArray, the 'arr' will contain the unevaluated expression "2+2" as zeroth element and with type STUArray it will contain the evaluated "4" ?
Henning Thielemann wrote:
I'll see, if I understand it.
do writeArray arr 0 2 x <- readArray arr 0 writeArray arr 0 (x+x)
If 'arr' is an STArray, the 'arr' will contain the unevaluated expression "2+2" as zeroth element and with type STUArray it will contain the evaluated "4" ?
Exactly. Put differently, writeArray :: STUArray -> .. is strict in the third argument whereas writeArray :: STArray -> .. is not. Regards, apfelmus
I'm not sure I understand your point : why would access to a specific element of the array make all the other elements evaluate (or even this specific element as long as you don't deconstruct it). Besides you misunderstood the "box" concept, indeed only primitive values that fits in 32 bits can be unboxed, all others need to be boxed anyway, and a box allow lazyness since it can point to a thunk as well as a WHNF. -- Jedaï
2007/9/5, Chaddaï Fouché
indeed only primitive values that fits in 32 bits can be unboxed
Note that there are some cases which could make you doubt that, like the UArray Bool (bool isn't a primitive type), but that's because UArray Bool don't really use unboxed bool, it's a specific implementation (array of bits). Also I think what I said is true for now, but I heard sum of void constructors could be unboxed in a future version of GHC, did I misunderstood ? -- Jedaï
On Wed, 2007-09-05 at 20:37 +0200, Henning Thielemann wrote:
Can someone explain me, why there are arrays with mutable but boxed elements?
I, on the other hand, have always wondered why the strict arrays are called "unboxed", rather than, well, "strict"? Strictness seems to be their observable property, while unboxing is just an (admittedly important) implementation optimization. I imagine that it'd be at least as easy to implement the strictness as the unboxedness for non-GHC compilers, and thus increase compatibility. -k
Ketil Malde wrote:
On Wed, 2007-09-05 at 20:37 +0200, Henning Thielemann wrote:
Can someone explain me, why there are arrays with mutable but boxed elements?
I, on the other hand, have always wondered why the strict arrays are called "unboxed", rather than, well, "strict"? Strictness seems to be their observable property, while unboxing is just an (admittedly important) implementation optimization. I imagine that it'd be at least as easy to implement the strictness as the unboxedness for non-GHC compilers, and thus increase compatibility.
You're quite right, that was a mistake, we should have called them strict arrays. Hugs implements the unboxed arrays without any kind of unboxing, I believe. Cheers, Simon
On 9/6/07, Simon Marlow
Ketil Malde wrote:
I, on the other hand, have always wondered why the strict arrays are called "unboxed", rather than, well, "strict"? Strictness seems to be their observable property, while unboxing is just an (admittedly important) implementation optimization. I imagine that it'd be at least as easy to implement the strictness as the unboxedness for non-GHC compilers, and thus increase compatibility.
You're quite right, that was a mistake, we should have called them strict arrays. Hugs implements the unboxed arrays without any kind of unboxing, I believe.
Any chance of a Data.Array.Strict and deprecating Data.Array.Unboxed? Cheers, /Josef
Ketil Malde wrote:
On Wed, 2007-09-05 at 20:37 +0200, Henning Thielemann wrote:
Can someone explain me, why there are arrays with mutable but boxed elements?
I, on the other hand, have always wondered why the strict arrays are called "unboxed", rather than, well, "strict"? Strictness seems to be their observable property, while unboxing is just an (admittedly important) implementation optimization.
Unboxing is, unfortunately, observable: it is not so easy to make a strict array of SomeArbitraryAlgebraicDataType, because it's not in class Storable. Isaac
Hello Isaac, Thursday, September 6, 2007, 9:41:34 PM, you wrote:
Unboxing is, unfortunately, observable: it is not so easy to make a strict array of SomeArbitraryAlgebraicDataType, because it's not in class Storable.
parallel arrays in GHC is just about it -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On Wed, Sep 05, 2007 at 07:54:34PM +0200, Henning Thielemann wrote:
I want to have a data structure like Data.ByteString.Lazy, that is block-wise lazy, but polymorphic. I could use a lazy list of unboxed arrays (UArray) but the documentation says, that the element types are restricted. But I will need (strict) pairs of Double and the like as elements. It seems that I need generalized instances in order to use these arrays. I thought it must be possible to define an unboxed array type with Storable elements. I cannot find such a type in the standard libraries. Further on, I wonder why pairs are not instances of Storable.
Your request is perfectly reasonable, it just hasn't been implemented. I started something like this a while ago; I'll see how easy it is to finish (famous last words). Stefan
participants (12)
-
apfelmus -
Benjamin Franksen -
Bryan O'Sullivan -
Bulat Ziganshin -
Chaddaï Fouché -
Henning Thielemann -
Isaac Dupree -
Jonathan Cast -
Josef Svenningsson -
Ketil Malde -
Simon Marlow -
Stefan O'Rear