Functional way to express a stateful filter in Scala

Question

Imagine the following List[Int] in Scala:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

I want to apply kind of a dynamic filter to it such that towards head/tail less data is filtered compared to the middle of the list:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] _ ____ __________ ___________ ______ __ [0, 1, 3, 7, 11, 13] // result

To do this, from both ends an index is increased by the next power of 2 and from the middle onwards the powers of 2 decrease again: 0, 0 + 2**0 = 1, 1 + 2**1 = 3, 3 + 2^2 = 7, etc.

To achieve this with an imperative approach, code similar to this can be used:

var log = 0 var idx = 0 val mask: ListBuffer[Int] = mutable.ListBuffer() while (idx < buffer.size) { mask += idx if (idx + (2 ** log) < buffer.size / 2) { idx += 2 ** log log += 1 } else { idx = buffer.size - (2 ** log) + 1 log -= 1 } }

This produces a mask array that can then be used to filter the original list like mask.flatMap(list.lift)

Can somebody help me do this in a more concise, functional way? What I basically need is a way to filter the list using some changing state from the outside.

Thanks in advance.

Dima · Accepted Answer · 2022-04-22 13:19:55Z

The usual approach to iterating with state is tail recursion (or you often do the same thing with reduceLeft with simple enough cases).

This is better than the other answer, because it is linear (accessing list elements by index makes the whole thing quadratic), and tail-recursive (no extra space on stack). Also, I think, the other version reverses the order of filtered elements.

You can do it with recursively in one go (this is better than the other answer, because it is tail-recursive, and linear (accessing list elements by index makes the implementation quadratic).

I didn't check the logic, which the other answer suggested was incorrect, just used it as is from your snippet, but here is the idea:

@tailrec def filter( in: List[Int], midpoint: Int, out: List[Int]=Nil, idx: Int = 0, next: Int = 0, log: Int = 0 ): List[Int] = in match { case Nil => out.reverse case head::tail if (idx == next) => filter(tail, midpoint, head::out, idx+1, idx + pow(2, log).toInt, if (idx < midpoint) log + 1 else log-1) case head::tail => filter(tail, midpoint, out, idx+1, next, log) }

Note, that this may seem less efficient than your "mask" idea because it looks at every element in the list, rather than jumping over indices being filtered out, but in fact, as long as you are working with List, it is actually more efficient: first, yours is (at least) O(N) anyway, because you have to traverse the whole list to figure out the size, and secondly, list.lift(idx) is O(idx), so towards the end of the list, this will be require multiple traversals of almost entire list.

Now, if you had an indexed container instead of a list, the whole "masking" idea would indeed improve things:

def filter(list: IndexedSeq[Int]) = { val size = list.size Iterator.iterate((0, 0)) { case (idx, log) => (idx + math.pow(2, log).toInt, if idx < size/2 log+1 else log-1) }.map(_._1).takeWhile(_ < size).map(list) }

The last code snippet looks like something I was looking for, thank you very much. I currently use a ListBuffer as an input collection, but I could turn this into an ArrayBuffer easily. This should provide constant random access as well as a constant buffer.size call.
Don't use Buffers, you should avoid using mutable containers and variables. 99% of the time you do not need them. Also avoid arrays, they are evil. Just use IndexedSeq
I am in a streaming setting in Akka, implementing a custom flow shape. There is a steady stream of elements arriving, filling up the buffer. Based on some condition, the buffer is evicted and then the logic of this post is called on the result buffer. So, as "buffering" is required in a quite literal sense, I chose to go with ArrayBuffer to have both efficient appends and random access at the same time.

leleogere · Accepted Answer · 2022-04-22 12:27:14Z

You code snippet does not work very well, I had to tweak it a bit to make it output the result you want:

var log = 0 var idx = 0 val resultList: mutable.ListBuffer[Int] = mutable.ListBuffer() // Fill the result until the middle, increasing the jump size while (idx < list.size / 2) { resultList += list(idx) idx += math.pow(2, log).toInt log += 1 } // Fill the result from the middle until the end, decreasing the jump size again while (idx < list.size && log >= 0) { resultList += list(idx) log -= 1 idx += math.pow(2, log).toInt }

With your example it works:

val list = (0 to 13).toList -> ListBuffer(0, 1, 3, 7, 11, 13)

However with another example I got that:

val list = (0 to 22).toList -> ListBuffer(0, 1, 3, 7, 15)

I don't think this is really what you want, do you?

Anyway here is a more functionnal version of it:

def filter(list: List[Int]) = { // recursive function to traverse the list def recursive(l: List[Int], log: Int, idx: Int, size: Int, halfSize: Int): List[Int] = { if (idx >= l.size || log < 0) // terminal case: end of the list Nil else if (idx < l.size / 2) // first half of the list: increase the jump size l(idx) :: recursive(l, log + 1, idx + math.pow(2, log).toInt, size, halfSize) else // second half of the list: decrease the jump size l(idx) :: recursive(l, log - 1, idx + math.pow(2, log-1).toInt, size, halfSize) } // call the recursive function with initial parameters recursive(list, 0, 0, list.size, list.size / 2) }

However, jumping by powers if 2 is too aggressive. If you are near the middle of the list, the next jump will ends at the very end, and you will not be able to get a progressive jump decay.

Another solution could be to increase the jump size by one each time instead of working with powers of 2. You can also keep a constant jump size when you are near the middle of the list to avoid skipping too much values in the second half before starting to reduce the jump size:

def filter2(list: List[Int]) = { def recursive(l: List[Int], jumpsize: Int, idx: Int, size: Int, halfSize: Int): List[Int] = { if (idx >= l.size) // terminal case: end of the list Nil else if (idx + jumpsize < l.size/2) // first half of the list: increase the jump size l(idx) :: recursive(l, jumpsize+1, idx + jumpsize, size, halfSize) else if (idx < l.size/2) // around the middle of the list: keep the jump size l(idx) :: recursive(l, jumpsize, idx + jumpsize, size, halfSize) else { // second half of the list: decrease the jump size val nextJumpSize = jumpsize - 1 l(idx) :: recursive(l, nextJumpSize, idx + nextJumpSize, size, halfSize) } } // call the recursive function with initial parameters recursive(list, 1, 0, list.size, list.size / 2) }

In my opinion, the results with this version are a bit better:

val list = (0 to 22).toList -> List(0, 1, 3, 6, 10, 15, 19, 22)

Thanks a lot for the improvements. I edited my original snipped to one that works better. The idea is to kind of start from both ends of the list, increasing by the next power of 2 until they meet each other. Example (0 to 100): 0, 1, 3, 7, 15, 31. And from the other side: 100, 98, 94, 86, 70. The specifics of the "aggressive" filtering make sense in the context this is used.

esse · Accepted Answer · 2022-04-22 15:39:38Z

Your question is not so clear for some corner case, here is my solution:

scala> def filter[A](seq: Seq[A], n: Int = 1): Seq[A] = seq match { | case Nil => Nil | case Seq(x) => Seq(x) | case _ => seq.head +: filter(seq.drop(n).dropRight(2*n), 2*n) :+ seq.last | } def filter[A](seq: Seq[A], n: Int): Seq[A] scala> filter(0 to 13) val res0: Seq[Int] = List(0, 1, 3, 7, 11, 13) scala> filter(0 to 100) val res1: Seq[Int] = List(0, 1, 3, 7, 15, 31, 38, 70, 86, 94, 98, 100) // I am not sure if 38 should in the result

Thanks for the interesting approach! I agree that the exact "algorithm" is not presented good enough in the question. Maybe this helps: Either 38 or 63 can be in the solution, because 15 as well as 70 kind of "represent" 2^4=16 elements. The next index is 31 and it represents 2^5=32 elements. So depending on whether we start at the beginning or at the end, 63 or 38 can be included.

Collectives™ on Stack Overflow

Functional way to express a stateful filter in Scala

3 Answers 3

3 Comments

1 Comment

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

2 Comments

Related