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

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

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

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