Transpose function does not work

Question
1

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

l map {_.tryHead} match {

   case List.Nil => List.Nil

   case List.Cons(head,tail) => List.Cons(head, transpose(l.tail))

}
Found: (head : Option[T])
Required: List[Option[T]]

2

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

1 Like
3

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

4

What’s the definition of the .tryHead method?

5

def tryHead: Option[A] = this match {

case Nil => None

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

}

6

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.

7

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?

8

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))
9

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]]

10

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.

11

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

12

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 first = ys.head
      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)
13

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