Transpose in Elm without Maybe

Question

I have a list of lists of ints [[1,2,3,4],[1,2,3,4]]

I want to transpose that to [[1,1],[2,2],[3,3]...]

I have:

transpose : List (List a) -> List (List a)
transpose ll = case ll of
    ((x::xs)::xss) -> (x :: (List.map List.head xss)) :: transpose (xs :: (List.map List.tail xss))
    otherwise -> []

but the issue is that the compiler doesn't like the head and tail operations and wants to return a Maybe type.

How do I transpose a list properly in elm?

Answer 1

You can sometimes use List.take 1/List.drop 1 in place of List.head/List.tail in cases where it can make more sense to get an empty List instead of Nothing.

In the example of transpose, if you want to write it such that it will drop any extra values when the lists are not of equal length (i.e. only transpose "as much as it can" depending on the shortest list), you can use:

transpose : List (List a) -> List (List a)
transpose ll =
  let heads = List.map (List.take 1) ll |> List.concat
      tails = List.map (List.drop 1) ll 
  in
      if | List.length heads == List.length ll ->
             heads::(transpose tails)
         | otherwise ->
             []

transpose [[1,2,3,4],[1,2,3,4]]        --> [[1,1],[2,2],[3,3],[4,4]]
transpose [[10,11],[20],[],[30,31,32]] --> []

If you want it to keep taking from the lists until they are all gone (i.e. transpose "as much as it can" depending on the longest list), you can use:

transpose : List (List a) -> List (List a)
transpose ll =
  let heads = List.map (List.take 1) ll |> List.concat
      tails = List.map (List.drop 1) ll 
  in
      if | List.isEmpty heads ->
             []
         | otherwise ->
             heads::(transpose tails)

transpose [[1,2,3,4],[1,2,3,4]]        --> [[1,1],[2,2],[3,3],[4,4]]
transpose [[10,11],[20],[],[30,31,32]] --> [[10,20,30],[11,31],[32]]

Both will work equally well in the case that the matrix is well formed, so if you wanted to check for edge cases and do something else you could do that first. They just handle the edge cases a little differently.

Answer 2

It depends...
Do you want to do this thoroughly, considering all the edgecases? Or do it the quick and dirty way? What I'm calling an edge-case is a list of lists where the sublists have a different length.

Very dirty way

In edge-cases you get a program crash

unsafeHead l =
  case l of
    (h :: t) -> h
    _ -> Debug.crash "unsafeHead called with empty list"

unsafeTail l =
  case l of
    (h :: t) -> t
    _ -> Debug.crash "unsafeTail called with empty list"

transpose ll =
  case ll of
    ((x::xs)::xss) ->
      let
        heads = 
          List.map unsafeHead xss

        tails =
          List.map unsafeTail xss
      in
        (x :: heads) :: transpose (xs :: tails)

    _ ->
      []

Good luck with those random program crashes, don't say I didn't warn you!

Don't care about edge-cases (or: shorter rows are ok)

In edge-cases you get: transpose [[10,11],[20],[],[30,31,32]] == [[10,20,30],[11,31],[32]]

transpose ll =
  case ll of
    [] ->
      []

    ([] :: xss) ->
      transpose xss

    ((x::xs) :: xss) ->
      let
        heads =
          List.filterMap List.head xss

        tails =
          List.filterMap List.tail xss
      in
        (x :: heads) :: transpose (xs :: tails)

Embrace the Maybe

In edge-cases you get a Nothing

If you only want to transpose when you have a list of lists where all sublists are the same size, you can just hoist up the Maybes that you get from mapping with List.head/List.tail:

transpose : List (List a) -> Maybe (List (List a))
transpose ll =
  case ll of
    ((x::xs)::xss) ->
      let
        heads =
          xss
          |> List.map List.head
          |> insideout

        tails =
          xss
          |> List.map List.tail
          |> insideout
      in
        (x #^ heads) ^#^ ((xs #^ tails) `Maybe.andThen` transpose)

    _ ->
      if ll == List.filter List.isEmpty ll then
        Just []
      else
        Nothing

----- Some helper functions: -----


mCons : a -> Maybe (List a) -> Maybe (List a)
mCons v ml = Maybe.map ((::) v) ml

v #^ ml = mCons v ml

-- this is really a Maybe.map2 (::) mv ml
-- but the standard library doesn't provide map2 :(
m2Cons : Maybe a -> Maybe (List a) -> Maybe (List a)
m2Cons mv ml =
  case (mv,ml) of
    (Just v, Just l) -> Just (v :: l)
    _ -> Nothing

mv ^#^ ml = m2Cons mv ml

-- list of justs to just of list
insideout : List (Maybe a) -> Maybe (List a)
insideout l =
  case l of
    [] -> Just []
    ((Just v) :: tail) -> v #^ insideout tail
    (Nothing :: _) -> Nothing