CODEWITHSUNDEEP
scalafunctional-programming
Aslan986
Aslan986

Reputation: 10314

How to filter a list with a condition that depends on more than one element

Given a list L I want to keep an element L(i) if it exists at least one value j > i such that L(j) is a multiple of L(i), otherwise L(i) should be discarded.

It is quite simple to do that by means of imperative programming paradigms, but I would like to do that using functional programming.

Is that possible to use the filter method? If so, how to write the condition (i.e. the parameter of the filter function) ? Otherwise, what can I do?

Upvotes: 2

Views: 206

Answers (2)

idonnie
idonnie

Reputation: 1703

A more "explicit" one - you accumulate elements in a case if tail has a multiple of head:

(1 to 10).tails.foldLeft(List[Int]())((acc, tl) => tl match {
  case h +: t if (t.exists(_ % h == 0)) => h :: acc
  case _ => acc
}).reverse

Upvotes: 2

0__
0__

Reputation: 67280

For example:

val l = (1 to 100)
l.tails.collect { case (head +: tail) if tail.exists(_ % head == 0) => head } .toList

tail produces an iterator that returns in each step the input minus one element, e.g.

(1 to 10).tails.foreach(println)

gives

Vector(1, 2, 3, 4)
Vector(2, 3, 4)
Vector(3, 4)
Vector(4)
Vector()

You can view these 'tails' as a head element to which you want to apply a filter and a tail in itself that is used to find out whether to keep the head.

The collect method is useful here, because it takes a partial function, so you only need to specify the cases where you actually retain a value—like filter—, while at the same time it acts like a map by letting you specify how the filtered value is to be collected.

So we can match on tails that have at least one head element and a tail of any size, and then see if in that tail there exists an element that is a multiple of the head. I use a guard here for the match case, so the match is a double filter. First, the tail must be non-empty, second there must be multiple. A multiple means that the modulus is zero. If the case matches, just return the verified head element.

Finally, since without specific type annotations the collect will just return another iterator, we turn the result into a list with toList.

Upvotes: 4

Related Questions