transpose?

[newlandsvalley]

Is there any interest in adding transpose to arrays? Not sure what would be a good implementation but possibly something along the lines of:

transpose :: forall a. Array (Array a) -> Array (Array a)
transpose x = 
  case head x of 
    Just [_] -> 
      x
    _ -> 
      (mapMaybe head x) : transpose (mapMaybe tail x)

[JordanMartinez]

transpose is likely something worth adding. However, is the above implementation the fastest it can be?

[newlandsvalley]

I've no idea. I thought perhaps someone else could take a look at it. You could certainly cache the result of head x to avoid calling it twice.

[JordanMartinez]

Not sure if this is faster due to the allocations of arrays, but here's what I got:

transpose :: forall a. Array (Array a) -> Array (Array a)
transpose xs = go 0 []
 where
 go :: Int -> Array (Array a) -> Array (Array a)
 go idx allArrays = case buildNext idx of
  Nothing -> allArrays
  Just next -> go (idx + 1) (A.snoc allArrays next)
  
   
 buildNext :: Int -> Maybe (Array a)
 buildNext idx = do
  xs # flip F.foldl (Just []) \acc nextArr -> do
   el <- A.index nextArr idx
   nextArray <- acc
   pure $ A.snoc nextArray el

Which accounts for array elements that are unequal in size:

transpose [[1], [2], [3]] == [[1, 2, 3]]
transpose [[1], [2], [3, 4]] == [[1, 2, 3]]
transpose [[1, 2], [3, 4], [5, 6, 7]] == [[1, 3, 5], [2, 4, 6]]

[newlandsvalley]

Thanks for looking at this, @JordanMartinez . When I get back home next week I'll try to investigate with some tests and performance measurements of these (and any other implementations that we might pick up in the meantime)

[newlandsvalley]

I've been making a start at looking at correctness. One thing I'm not sure about is your last two examples. By analogy to Data.List.transpose:

transpose ( (1 : Nil) : (2 : Nil) : (3 : (4 : Nil)) : Nil) == ((1 : 2 : 3 : Nil) : (4 : Nil) : Nil)
transpose ( (1 : (2 : Nil)) :  (3 : (4 : Nil)) : (5:  (6 : (7 : Nil))) : Nil) == ((1 : 3 : 5 : Nil) : (2 : 4 : 6 : Nil) : (7 : Nil) : Nil)

[JordanMartinez]

Huh... I guess the question here is which is the correct way. I support the List version is right because it was supported first.

[newlandsvalley]

Yeah - I suppose we could see what Haskell does which might confirm things.

[newlandsvalley]

Haskell's Data.List.transpose behaves exactly as purescript's version. Can I suggest that you amend your implementation accordingly? Also, there is an edge case to look at - the empty array [] - which hangs. The one element array where that element is empty [[]] gives [] which I'm slightly surprised to see is exactly what the haskell version gives - I would have expected [[]] but maybe this is consistent with the overall pattern of filtering away all empty arrays.

My initial attempts at profiling indicate that your implementation is probably going to be considerably faster than mine!

[JordanMartinez]

How about this one? https://try.purescript.org/?gist=d367a2668942b31d9a77c53050053db4

[newlandsvalley]

That passes all my tests (which are not very different from yours anyway). Many thanks!

[newlandsvalley]

And you win the performance test. Transposing a 750 * 750 Int array takes about 890 ms as opposed to my 2800. And for a 1000 * 1000 Int array, mine crashes out of memory whereas yours takes about 1920 ms.

If it's of interest, my final implementation was this:

transpose :: forall a. Array (Array a) -> Array (Array a)
transpose [] = []
transpose x = 
  case (mapMaybe head x) of 
    [] -> 
      transpose (mapMaybe tail x)
    start ->       
      start : transpose (mapMaybe tail x)      

[JordanMartinez]

I'm wondering if my version would be any faster if runST was used. I don't know if ST gets properly inlined right now, so I think it might be slower?

[JordanMartinez]

Anyhow, feel free to submit a PR!

[newlandsvalley]

Would you accept a PR based on your implementation?

[JordanMartinez]

Yeah