Add transpose to NonEmptyArray

[newlandsvalley]

I've had a look at modifying both implementations we have for the normal Array case detailed in #225 for use with a NonEmptyArray. I came up with this one based on my implementation:

import Data.Array.NonEmpty
import Data.Array.NonEmpty.Internal (NonEmptyArray(..))
import Data.Maybe (Maybe(..))
import Prelude (map)

transpose :: forall a. NonEmptyArray (NonEmptyArray a) -> NonEmptyArray (NonEmptyArray a)
transpose x = 
  case (mapMaybe tail' x) of 
    [] -> 
      singleton (map head x)
    end -> 
      cons (map head x) (transpose (unsafeFromArray end))

  where
  tail' :: NonEmptyArray a -> Maybe (NonEmptyArray a)
  tail' x = 
    case tail x of 
      [] -> Nothing 
      end -> Just (unsafeFromArray end)

unsafeFromArray :: forall a. Array a -> NonEmptyArray a
unsafeFromArray = NonEmptyArray

and this one based on the implementation from @JordanMartinez :

import Prelude
import Data.Array as A
import Data.Array.NonEmpty
import Data.Array.NonEmpty.Internal (NonEmptyArray(..))
import Data.Maybe (Maybe(..), maybe)
import Data.Foldable (foldl) 

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

unsafeFromArray :: forall a. Array a -> NonEmptyArray a
unsafeFromArray = NonEmptyArray

All the tests pass for whichever version, but performance comparisons show the same pattern as for Array - Jordan's is again about three times faster than mine and is only a little slower than for Array. I'm slightly concerned about the use of unsafeFromArray at the top level, but I think it's legitimate and many other functions in the module rely on it.

If you're agreeable, I'll raise a PR using this.

[JordanMartinez]

Oh, I was thinking something much simpler using unsafeAdapt:

transpose :: forall a. NonEmptyArray (Array a) -> NonEmptyArray (Array a)
transpose = unsafeAdapt Array.transpose

[newlandsvalley]

OK - I'll add this to my tests and see how it compares.

[newlandsvalley]

Oh, I hadn't spotted that our signatures are different. Mine handles NonEmptyArray (NonEmptyArray a) and yours handles NonEmptyArray (Array a). I had assumed that we wanted the former.

[newlandsvalley]

And your implementation does suggest another implementation for my signature:

import Prelude
import Data.Array.NonEmpty (toArray)
import Data.Array.NonEmpty.Internal (NonEmptyArray(..))
import Data.Array (transpose) as A

transpose :: forall a. NonEmptyArray (NonEmptyArray a) -> NonEmptyArray (NonEmptyArray a)
transpose = unsafeFromArray2D <<< A.transpose <<< toArray2D

toArray2D :: forall a. NonEmptyArray (NonEmptyArray a) -> Array (Array a)
toArray2D =
  (map toArray) <<< toArray

unsafeFromArray2D :: forall a. Array (Array a) -> NonEmptyArray (NonEmptyArray a) 
unsafeFromArray2D =  
  (map unsafeFromArray) <<< unsafeFromArray
 
unsafeFromArray :: forall a. Array a -> NonEmptyArray a
unsafeFromArray = NonEmptyArray 

This has identical performance behaviour to the better of my two implementations above and I think has the virtue of simplcity.

[garyb]

Oh, I hadn't spotted that our signatures are different. Mine handles NonEmptyArray (NonEmptyArray a) and yours handles NonEmptyArray (Array a). I had assumed that we wanted the former.

Having both varieties would probably be good actually!

[newlandsvalley]

Oh, I hadn't spotted that our signatures are different. Mine handles NonEmptyArray (NonEmptyArray a) and yours handles NonEmptyArray (Array a). I had assumed that we wanted the former.

Having both varieties would probably be good actually!

OK. What about naming? transpose for NonEmptyArray (NonEmptyArray a) and transpose' for NonEmptyArray (Array a) ?

[garyb]

That works for me, we tend to prime the other NonEmptyArray operations that also involve Array 🙂

[JordanMartinez]

Fixed by #228