 # Transpose function does not work

def transpose[T](l: List[List[T]]): List[List[Option[T]]] =

``````   case List.Nil => List.Nil

``````

}
Required: List[Option[T]]

What are the definitions of `List.Nil` and `List.Cons`? I don’t think those are part of the Scala Standard Library.

1 Like

It is my List implementation:
enum List[+A]:
case Nil
case Cons(hd: A, tl: List[A])

What’s the definition of the `.tryHead` method?

def tryHead: Option[A] = this match {

``````case Nil => None

case Cons(hd,tl)=> Some(hd)
``````

}

OK, so `.tryHead` returns an option. Therefore, when you are pattern matching on the result of a `someList.tryHead`, you have to use cases `Some` and `None`:

``````someList.tryHead match {
case Some(hd) => ???
case None => ???
}
``````

That’s why you are getting the error `Found: (head : Option[T]) Required: List[Option[T]]`.

When you do

``````l map {_.tryHead}
``````

this transform `l: List[List[T]]` to a `List[Option[T]]` because it changes every element of `l` to `Some(...)` or `None`. Every element of `l` is a `List[T]` which turns into an `Option[T]` after `tryHead`.

Thank you. Please, can you suggest me other variants to write a transpose function, if you know, because I understood that it is a wrong approach. Did I understand correctly?

I suppose you are doing this as an exercise? Because Scala has a built-in `.transpose` method already:

``````scala> val y = List(List(1,2), List(3,4))
val y: List[List[Int]] = List(List(1, 2), List(3, 4))

scala> y.transpose
val res3: List[List[Int]] = List(List(1, 3), List(2, 4))
``````

I need to implement a function:
transpose(xs: List[List[Int]]): List[List[A]]
transpose([1,2,3],[4,5,6])==[[1,4],[2,5],[3,6]]

Here is a terrible implementation (in Scala 3) assuming none of the lists are empty:

``````def transpose[A](xs: List[List[A]]): List[List[A]] =
val rows = xs.length
val columns = xs(0).length
val all =
for
j <- 0 until columns
column = (for i <- 0 until rows yield xs(i)(j))
yield column.toList
all.toList
``````

I’m sure others can suggest something better.

Thank you very much. But I have a question : Can this be written using a tail recursion?

Here is another horrible implementation:

``````def transpose[A](xs: List[List[A]]): List[List[A]] =
@tailrec
def helper[A](ys: List[List[A]], acc: List[List[A]]): List[List[A]] =
if ys.isEmpty then acc
else
val newAcc =
for
i <- 0 until first.length
yield acc(i) ::: List(first(i))
helper(ys.tail, newAcc.toList)
val acc = (for i <- 0 until xs(0).length yield List()).toList
helper(xs, acc)
``````

I won’t provide code both because I can’t write now and because since this is homework the best is if you can come up with the solution yourself.

However, I am going to give you an advice.
A simple solution requires two tail-recursions, one nested in the other.

The outer one should be pretty straightforward if you can come up with the internal one.

And the internal one has this signature.

``````def getAllHeads[A](data: List[List[A]]): Option[(List[A], List[List[A]])]
``````

It would check if all inner lists are not empty, if so it will return all heads and tails.
Otherwise a `None`

I hope that helps.

1 Like