resizeDefault allowing a 'fill' element if the dimensions are short

[kozross]

Is there a way to do something like

resizeDefault :: (Index ix', Size r ix e) => e -> ix' -> Array r ix e -> Array r ix' e

This will use the supplied e to 'fill in' any elements needed to resize that don't exist in the argument array. For example:

resizeDefault 0 (4 :. 3) (makeArrayR U Par 10 ((+ 1) :: Int -> Int))

should produce

Array U Par (4 :. 3)
  [  [ 1,2,3 ]
  ,  [ 4,5,6 ]
  ,  [ 7,8,9 ]
  ,  [ 10,0,0 ]
  ]

[lehins]

If there is a will, there is a way :D You bring up an interesting question. A solution with exact type signature you presented is not possible without some major change to underlying structure of the library, but that would be a wrong way to go about it anyways.

I am not sure if I will add any of the solutions to the library, but free to use either one of them

Here is a naive and less optimal solution to the problem:

defaultResizeNaive :: (Construct r ix' e, Source r ix e) => e -> ix' -> Array r ix e -> Array D ix' e
defaultResizeNaive e newsz arr =
  makeArray (getComp arr) newsz $
  handleBorderIndex (Fill e) oldsz (unsafeIndex arr) . fromLinearIndex oldsz . toLinearIndex newsz
  where oldsz = size arr

It is sub-optimal because it has to check if index doesn't go out of bounds for every element of new array. But the good thing is that resulting array is D so no intermediate array has been created and further computation can be fused. Which is also known as "pull" array.

A more involved solution is to actually iterate over the old array while loading it's elements into the new array, and if there is any unfilled space leftover fill it with default value:

defaultResize :: (Source r ix e, Mutable r' ix' e) => e -> ix' -> Array r ix e -> Array r' ix' e
defaultResize e newsz' arr =
  unsafePerformIO $ do
    let newsz = liftIndex (max 0) newsz'
        oldsz = size arr
        knew = totalElem newsz
        kold = min (totalElem oldsz) knew
        comp = getComp arr
    marr <- unsafeNew newsz
    case comp of
      Seq -> do
        loopM_ 0 (< kold) (+ 1) $ \i -> unsafeLinearWrite marr i (unsafeLinearIndex arr i)
        loopM_ kold (< knew) (+ 1) $ \i -> unsafeLinearWrite marr i e
      ParOn wIds ->
        withScheduler_ wIds $ \scheduler -> do
          splitLinearlyWith_
            (numWorkers scheduler)
            (scheduleWork scheduler)
            kold
            (unsafeLinearIndex arr)
            (unsafeLinearWrite marr)
          let slack = knew - kold
          splitLinearlyWith_
            (numWorkers scheduler)
            (scheduleWork scheduler)
            slack
            (const e)
            (unsafeLinearWrite marr . (+ kold))
    unsafeFreeze comp marr

The interesting part about the problem and this last solution is that it would be possible to create a delayed array as well, but of a different kind, namely a "push" array. I've been pondering on this idea for couple of weeks now and considering implementing this new kind of delayed array, we'll see. This would allow nicer solutions for a new class of problems, including this one.

cc @ocramz Thanks for pointing out the topic of Pull/Push arrays to me at Haskell Exchange, it already comes in handy ;)

[kozross]

Wow, I didn't realize it was this tricky! Ultimately, I'd be after a D array for my current use case, so I'll try both options and see which one works better.

Also, do you have any links about push/pull arrays I could read?

[lehins]

Here is a paper that gives a nice introduction to push pull arrays, but then goes into more stuff: https://svenssonjoel.github.io/writing/defuncEmb.pdf

[lehins]

Now that push arrays are available in massiv we can easily implement this function.