By Leonardo Giordani Published on

# Problem 16¶

## The problem¶

P16 (**) Drop every Nth element from a list.

Example:

```scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)
```

## Mapping¶

A first simple approach is to divide the list in small groups of up to N elements and drop the last element from each of them. This is easily achieved with the `grouped()` method of `List` types and the application of a flat mapping.

```def drop[A](n: Int, l: List[A]):List[A] = {
l.grouped(n).flatMap { _.take(n - 1) }.toList
}
```

The `grouped()` method returns an iterator, which is, as in other languages, something that can visit the elements contained in a collection and yield them. When an iterator is required to be consumed all at once you can call the `toList()` method to convert it into a `List`.

```scala> val l = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)
l: List[Symbol] = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)

scala> l.grouped(3)
res0: Iterator[List[Symbol]] = non-empty iterator

scala> l.grouped(3).toList
res1: List[List[Symbol]] = List(List('a, 'b, 'c), List('d, 'e, 'f), List('g, 'h, 'i), List('j, 'k))
```

`Iterator` type has a lot of methods in common with `List` type, most notably `flatMap()`. This last method is fed with a simple anonymous function that, using `take()`, keeps the first `n - 1` elements.

A different approach may be followed using the `zipWithIndex()` method that packs each element of the list with its index (starting from 0)

```scala> l zipWithIndex
res5: List[(Symbol, Int)] = List(('a,0), ('b,1), ('c,2), ('d,3), ('e,4), ('f,5), ('g,6), ('h,7), ('i,8), ('j,9), ('k,10))
```

After this transformation, we may apply the `filter()` method to get the right elements with a selection based on the modulo operation.

The list is now made of `Tuple2` elements, as tuples in Scala aren't a collection just like lists (or like Python tuples). For performance reasons, they are implemented with a different type according to the length, like in this case. To index a `Tuple2` element we may use its `_1` and `_2` attributes (pay attention that tuples are indexed starting from 1).

The filter anonymous function just checks if the index (the second element of the tuple) is a multiple of `n`. Then, with `map()` we keep the first element only (the original element); the anonymous function `{ _._1 }` is a shortcut form for `{ e => e._1 }`

```def dropZip[A](n: Int, l: List[A]):List[A] = {
l.zipWithIndex filter { e => (e._2 + 1) % n != 0 } map { _._1 }
}
```

## The recursive solution¶

A recursive solution can be written based on this simple algorithm: the number N is used as a countdown, keeping elements until it reaches the value 1. Then the current element is discarded and the process continues with a countdown reset.

```def dropRec[A](n: Int, l: List[A]):List[A] = {
def _dropRec[A](c: Int, res: List[A], rem: List[A]):List[A] = (c, rem) match {
case (_, Nil) => res
case (1, _::tail) => _dropRec(n, res, tail)
case (_, h::tail) => _dropRec(c -1, res:::List(h), tail)
}
_dropRec(n, List(), l)
}
```

As you can see the case `(1, _::tail)` restarts the process ignoring the current head of the list, while the more generic `(_, h::tail)` case stores the element in the result list.

# Problem 17¶

## The problem¶

P17 (*) Split a list into two parts.

Example:

```scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
```

## Solution¶

`List` objects provide a bunch of methods to interact with them, thus splitting may make use of several different ones. Very simple and straightforward solutions come from the `splitAt()` method

```def split[A](n: Int, l: List[A]): (List[A], List[A]) = l.splitAt(n)
```

using the two `take()` and `drop()` methods

```def split[A](n: Int, l: List[A]): (List[A], List[A]) = {
(l.take(n), l.drop(n))
}
```

or using `take()` and `takeRight()`

```def split[A](n: Int, l: List[A]):(List[A], List[A]) = {
(l.take(n), l.takeRight(l.length - n))
}
```

A list can be splitted also using recursion, however, using the given split position as a counter

```def split[A](n: Int, l: List[A]):(List[A], List[A]) = {
def _split[A](c: Int, res: List[A], rem: List[A]):(List[A],List[A]) = (c, rem) match {
case (_, Nil) => (res, Nil)
case (0, rem) => (res, rem)
case (c, h::tail) => _split(c - 1, res:::(List(h)), tail)
}
_split(n, List(), l)
}
```

where I basically keep extracting the head from `rem` appending it to `res` until the counter is 0.

# Problem 18¶

## The problem¶

Pxx (**) Extract a slice from a list. Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.

Example:

```scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)
```

## Solution¶

As for the previous problem we may make use of the `List` type methods. The aptly named `slice()`

```def slice[A](start: Int, end: Int, l: List[A]): List[A] =
l.slice(start, end)
```

or a combination of `drop()` and `take()`

```def slice[A](i: Int, k: Int, l: List[A]):List[A] = {
l take k drop i
}
```

The recursive solution first drops the required number of elements from the head of the list. When the first index is exhausted the function starts dropping elements from the tail (using `init()`). The number of elements to be dropped is computed as `k - i` when the internal function is called.

```def slice[A](i: Int, k: Int, l: List[A]):List[A] = {
def _slice[A](cl: Int, cr: Int, rem: List[A]):List[A] = (cl, cr, rem) match {
case (0, 0, rem) => rem
case (0, cr, rem) => _slice(0, cr - 1, rem.init)
case (cl, cr, h::rem) => _slice(cl - 1, cr, rem)
}
_slice(i, k - i, l)
}
```

# Problem 19¶

## The problem¶

P19 (**) Rotate a list N places to the left.

Example:

```scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)

scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)
```

## Solution¶

Rotating a list has some caveats. First one must consider wrapping, so the first thing I did is to calculate the actual shift with the modulo operation. The second thing is that rotation can happen in both directions, and the case of negative shift can be converted to a positive one just adding the shift to the length of the list (being the shift negative this is actually a subtraction). Eventually we can perform the rotation which requires a composition of the output of `drop()` and `take()`

```def rotate[A](n: Int, l: List[A]):List[A] = {
val wrapn = if (l.isEmpty) 0 else n % l.length
if (wrapn < 0) rotate(l.length + n, l)
else l.drop(wrapn):::l.take(wrapn)
}
```

# Problem 20¶

## The problem¶

P20 (*) Remove the Kth element from a list. Return the list and the removed element in a Tuple. Elements are numbered from 0.

```scala> removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)
```

## Solution¶

There are two edge conditions in this problem. The first is when the list is empty, and the second is when we are asking for an index outside the list. Since an empty list has length 0 both conditions can be summarized checking if the requested index is greater or equal than the length of the list (the "or equal" part comes from the fact that lists are indexed starting from 0).

The simplest solution uses `take()` and `drop()`

```def removeAt[A](n: Int, l: List[A]):(List[A], A) = {
if (l.length <= n ) throw new NoSuchElementException
(l.take(n):::l.drop(n).tail, l(n))
}
```

The problem with boundaries comes from the use of `tail()`, that cannot be applied to an empty list, while `take()` and `drop()` seamlessly work on empty lists and negative indexes. So using the `take()` counterpart `takeRight()` we could write

```def removeAt[A](n: Int, l: List[A]):(List[A], A) = {
(l.take(n):::l.takeRight(l.length - n), l(n))
}
```

which automatically raises an `IndexOutOfBoundsException` when the requested index is outside the list. If we want a `NoSuchElementException`, however, we have to wrap the code with a `try` statement.

We can also use mapping, even if in this case its use is probably overkill

```def removeAt[A](n: Int, l: List[A]):(List[A], A) = {
(l.zipWithIndex filter { e => e._2 != n } map { _._1 }, l(n))
}
```

this solution raises an `IndexOutOfBoundsException` when the index is outside the list, just like the previous one.

A recursive solution may use the index as a countdown value to get elements until the requested one pops up, then skipping it and getting the rest of the list.

```def removeAtR[A](n: Int, l: List[A]):(List[A], A) = {
def _removeAtR[A](k: Int, res: List[A], rem: List[A]):(List[A], A) = (k, rem) match {
case (0, h::tail) => return (res:::tail, h)
case (k, Nil) => throw new NoSuchElementException
case (k, h::tail) => return _removeAtR(k - 1, res:::List(h), tail)
}
return _removeAtR(n, List(), l)
}
```

## Final considerations¶

Problem 16 introduced me to new list methods `filter()` and `zipWithIndex()`. I met iterators and tuples for the first time and learned how to deal with them on a basic level. Problem 17 introduced the new `splitAt()` method and let me review `take()`, `takeRight()` and `drop()`. The recursive solution makes use of everything has been already discovered solving the previous problems. With problem 18 I learned a new method of the `List` type, `slice()`. The recursive solution is pretty straightforward but matching a tuple of three values requires some attention. I appreciate the syntactic sugar that allows to drop parenthesis when calling a function with a single argument, it makes the call resemble natural language. Problems 19 and 20 are just applications of the same methods.

## Feedback¶

Feel free to use the blog Google+ page to comment the post. The GitHub issues page is the best place to submit corrections.