[vector] #15: Add "generalised scan"

vector vector at projects.haskell.org
Tue Aug 24 07:28:34 EDT 2010


#15: Add "generalised scan"
------------------------+---------------------------------------------------
Reporter:  rl           |        Owner:     
    Type:  enhancement  |       Status:  new
Priority:  critical     |    Milestone:  0.7
 Version:  0.6          |   Resolution:     
Keywords:               |  
------------------------+---------------------------------------------------
Comment (by anonymous):

 More of a note for me...

 Lets say I have
 {{{
 do
   (tx,txM) <- mkTable 0 n
   (ty,tyM) <- mkTable 0 n
   forM_ [n,n-1..0] $ \i -> do
     write txM i $ opA tx ty i n
     write tyM i $ opB tx    i n
   return (tx,ty)
 }}}
 mkTable creates space for some elements in 'snd' and unsafefreezes
 everything in 'fst'. With the generalized scan, I would not have 2 tables
 of 1-tuples but 1 table of a 2-tuple per cell.

 This badly breaks some algorithms. Consider that I want to extend stuff to
 include a third table. Now the functions opA and opB would receice a table
 of 3-tuples and would have to do indexing in another way.

 This is no problem, if we can unzip the tuples in O(1). It is O(n) but if
 fusion fires correctly, everything should come down to loops that
 correctly index the tuple elements.



 Otherwise, I have to take a closer look at all this anyway, as sometimes
 fusion does not happen. I have, for example, two function doing exactly
 the same (one does enumFromN, the other enumFromStepN) and one produces a
 nice loop, the other generates an intermediate array. But that will be a
 report, once I know more...

-- 
Ticket URL: <http://trac.haskell.org/vector/ticket/15#comment:6>
vector <http://trac.haskell.org/vector>
Package vector


More information about the vector mailing list