CODEWITHSUNDEEP
scalatuples
user_123945839432
user_123945839432

Reputation: 189

How to write a zip function from scratch

How to write the zip function, which tuples corresponding elements in a list. I understand that zip is a built in function but I am trying to write it from scratch.

def zip[A,B](lst1: List[A], lst2: List[B]): List[(A, B)]

Test example would be:

test("zip test 1") {
assert(zip(List(1, 2, 3), List(4, 5, 6)) == List((1,4), (2, 5), (3, 6)))
}

or strings as parameters:

test("zip test 2") {
assert(zip(List("hey", "code"), List("world", "scala")) ==
List(("hey", "world"), ("code", "scala")))
}

I tried this so far:

 def zip[A,B](lst1:List[A], lst2:List[B]):List[(A,B)] = (lst1,lst2) match{
    case Nil=> Nil
    case (h1::t1 :: h2 :: t2) =>zip(t1, t2)
 }

But I get a type mismatch error, and a immutability error.

Upvotes: 0

Views: 1260

Answers (1)

user1804599
user1804599

Reputation:

If either list is empty, return the empty list. Otherwise, prepend the pair of heads to the zip of tails:

def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)] =
  (xs, ys) match {
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    case (x :: xs, y :: ys) => (x, y) :: zip(xs, ys)
  }

Augmenting to exploit tail recursion optimisation is left as an exercise for the reader.

Upvotes: 6

Related Questions