What does this mean "shapes extended to support ragged arrays without boxing"?
K has ragged arrays without boxing, but K's concept of shape only applies to the non-ragged prefix dimensions. Meanwhile, it seems to me that the guarantee you suggest would be computationally expensive. (Not saying the ideas shouldn't be explored, but I suspect what you are really after is a more efficient boxing implementation and that will lead in an entirely different direction.) Thanks, -- Raul On Mon, Sep 8, 2014 at 11:01 AM, Michal D. <michal.dobrog...@gmail.com> wrote: > Thanks Pascal, that's a nice formulation for the 2-level deep case. It > breaks down of course for deeper nesting but could serve as a base. > > ([:|. $ ;~ $ each) ((i.2 3);(,0)) ; (i. 2 3) > +-+-------+ > |2|+-+---+| > | ||2|2 3|| > | |+-+---+| > +-+-------+ > > There's no specific problem I'm trying to solve directly in J at the > moment. It's more of a language design problem. My interest in this is a > J like language, but with shapes extended to support ragged arrays without > boxing. Failing that, we could have some optimization guarantees like 'an > array of boxes containing equal rank values are allocated contiguously'. > > Cheers, > > Mike > > > > On Sat, Sep 6, 2014 at 9:28 AM, 'Pascal Jasmin' via Programming < > programm...@jsoftware.com> wrote: > >> Hi Michal, >> >> maybe this is an interesting representation for what you want? >> >> ([:|. $ ;~ $ each) (i. 2 3) ; (,0) ; 0 1 >> ┌─┬─────────┐ >> │3│┌───┬─┬─┐│ >> │ ││2 3│1│2││ >> │ │└───┴─┴─┘│ >> └─┴─────────┘ >> >> >> >> ----- Original Message ----- >> From: Michal D. <michal.dobrog...@gmail.com> >> To: programm...@jsoftware.com >> Cc: >> Sent: Saturday, September 6, 2014 12:06 PM >> Subject: [Jprogramming] Ragged Array Shapes are Trees >> >> I just came to the realization that ragged array shapes, regardless of how >> you want to represent them, are trees. I would be interested in any >> references to prior exploration of this idea. >> >> Some example data (boxes are used to display ragged arrays, but otherwise >> have no semantic meaning): >> >> ] A =. i. 2 3 >> 0 1 2 >> 3 4 5 >> ] B =. (< @ i."0) 1+i.2 >> +-+---+ >> |0|0 1| >> +-+---+ >> ] C =. A ; B >> +-----+-+---+ >> |0 1 2|0|0 1| >> |3 4 5| | | >> +-----+-+---+ >> ] D =. A ; < B >> +-----+-------+ >> |0 1 2|+-+---+| >> |3 4 5||0|0 1|| >> | |+-+---+| >> +-----+-------+ >> >> The corresponding shape trees (monospace font required, root node is on the >> left): >> >> A: 2 - 3 >> >> 1 >> / >> B: 2 >> \ >> 2 >> >> 2 - 3 >> / >> C: 3 - 1 >> \ >> 2 >> >> 2 - 3 >> / >> D: 2 1 >> \ / >> 2 >> \ >> 2 >> >> In some sense the shape tree for A is compressed, the verbose alternative >> being: >> >> 3 >> / >> A: 2 >> \ >> 3 >> >> Compressing D in a similar manner leaves the full shape of the tree >> ambiguous - there is no way to distinguish the duplicate structure of leaf >> 3 from the structure of leaves 1, 2. >> >> 3 >> / >> D: 2 - 2 - 1 >> \ >> 2 >> >> We could resolving this ambiguity by listing the shapes of all the items >> explicitly. The problem here is that 'compression' could very easily lead >> to an increase in representation size, although it is nice and uniform for >> ragged arrays of uniform rank. >> >> 3 >> / >> | 3 >> | / >> D: 2 - 2 + >> | \ >> | 1 >> \ >> 2 >> >> Regardless of compression, I would be interested in prior work in >> representing shapes of ragged arrays as trees. >> >> Cheers, >> >> Mike >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
