Function to determine membership in a list

Question

I need to write a program which contains the function doesExist: [A](p:A => Boolean) (xs: List[A]) Boolean.

e.g. doesExist ((x:Int) => x==2) (List(5,1,2,3)) => true

It should just return true or false depending on whether the element is found in the list.

Please add information on what you've tried so far, what problems you encountered. [ask]. — morxa, Mar 16 '16 at 18:14
def doesExist[A](p: A => Boolean)(xs: List[A]): Boolean = { xs.foldLeft(false)((acc, elem) => acc || p(elem)) } Got this compiled, now I try to test on some data, trying that form: doesExist(2)(List(1,2,3)) No proper reply. — H4rdy, Mar 16 '16 at 18:19
Solved it, form like that: doesExist((x:Int) => x==2)(List(1,2,3)) Returns that: doesExist((x:Int) => x==0)(List(1,2,3)) res11: Boolean = false So I think it is clear now. — H4rdy, Mar 16 '16 at 18:29

score 1 · Accepted Answer · answered Mar 16 '16 at 18:10

1

I guess that the gist of it is to not use the built in function of lists... So here's an alternative using foldLeft:

def doesExist[A](p: A => Boolean)(xs: List[A]): Boolean = {
    xs.foldLeft(false)((acc, elem) => acc || p(elem))
}

answered Mar 16 '16 at 18:10

hasumedic

2,139
12
17

This goes through the whole list even after it's found a true element. – Ben Kovitz Mar 17 '16 at 07:40

score 1 · Answer 2 · answered Mar 16 '16 at 18:40

1

It could be a good exercise to practice pattern-matching:

def doesExist[A](p:A => Boolean)(xs: List[A]): Boolean = xs match {
    case Nil => false
    case head :: tail => p(head) || doesExist(p)(tail)
}

answered Mar 16 '16 at 18:40

Alexis C.

91,686
21
171
177

Jean Logeart · Answer 3 · 2016-03-16T18:15:13.153

0

Simply:

def doesExist[A](p:A => Boolean)(xs: List[A]) = xs.exists(p)

If you cannot use exists:

def doesExist[A](p:A => Boolean)(xs: List[A]) =
  xs.fold(false)((alreadyFound, a) => alreadyFound || p(a))

edited Mar 16 '16 at 18:15

answered Mar 16 '16 at 18:06

Jean Logeart

52,687
11
83
118

The second version searches the whole list even after finding a true element. The first version does not. – Ben Kovitz Mar 17 '16 at 08:08

score 0 · Answer 4 · edited May 23 '17 at 11:45

Here's how the Scala 2.11.8 standard library does it.

From LinearSeqOptimized.scala:

  override /*IterableLike*/
  def exists(p: A => Boolean): Boolean = {
    var these = this                      // <--- Look, a var!
    while (!these.isEmpty) {
      if (p(these.head)) return true      // <--- Look, a return!
      these = these.tail
    }
    false
  }

In other words, Scala uses a while loop, which mutates a var that points to the next object, and breaks out of the loop when it reaches the desired object.

I found out, when comparing answers to a similar question, that while with some sort of mutating iteration variable is the most efficient way to write this in Scala. Pure-functional approaches like recursion, Streams, etc. are slower—as much as 8 times slower (and still without scanning beyond the first 'true' element). I gather that the best approach is to use some kind of mutable iterator when you need to do a linear search and hide it inside a function that presents a pure-functional interface to the rest of the program. The Scala standard library does that in many places for you, so you get the best possible performance with a pure-functional interface.

Function to determine membership in a list

4 Answers4