Strange behavior of a simple function

The for loop does not terminate just because your condition was met. All you tell it to do is output a true. Scala happily outputs values even if nobody wants to use them. Unless there is an explicit return statement, the only thing that gets returned from the function is the last result. The same is true for any code block in Scala.

{ for(i <- 0 to 3) true; false } also always returns false (try it in the repl). The true values are just discarded.

Dennis

On Wed, Sep 21, 2011 at 11:04 AM, Assaf Zaritsky <assafzar@gmail.com> wrote:

Hi,
Consider the following find function that returns true iff a given
value in found in a given array. I am aware there are MUCH better ways
to perform this task, but this is not the question.

def find(a : Array[Int], x : Int) : Boolean ={
   var z : Boolean = false
   for(i <- 0 until a.length)
     if(a(i)==x)
       z=true
   z
 }

This function works as expected
now, consider the following function that should work the same way

def find(a : Array[Int], x : Int) : Boolean ={
   for(i <- 0 until a.length)
     if(a(i)==x)
       true
  false
 }

This function returns false for all inputs although I expect it to do
the same as the upper implementation

I was able to make it work by adding "return true" in the "if"
statement, but I can not understand why it doesn't work from the first
place.

Thanks,
Assaf

Hello,

On Wed, Sep 21, 2011 at 2:04 PM, Assaf Zaritsky <assafzar@gmail.com> wrote:

Hi, ...

 

def find(a : Array[Int], x : Int) : Boolean ={
   for(i <- 0 until a.length)
     if(a(i)==x)
       true
  false
 }

Well,
def find(a: Array[Int], x: Int): Boolean = {truefalse}
would always return false as well. What's returned is the value of the last expression, which is false in this case, as well as in yours.
What you need to remember is that most things in Scala are expressions. 
Your for comprehension is an expression that evaluates to () (of type Unit - similar to void in Java, but actually has a type and value, so can be used in generics, for example), so your code is functionally equivalent to:
def find(a: Array[Int], x: Int): Boolean = {()false}
Another example; the if inside your for-comprehension evaluates to an "AnyVal" and will either have the Unit value () or true, but that doesn't get passed outside of the for comprehension.
You could rewrite your function down to a single expression using a fold:
def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)

It would be much better to NOT call it a 'for loop'. It is a 'for comprehension' and it translates into a foreach(), which takes a function returning Unit, that's why the "true" is discarded...
So you basically wrote this: (0 until a.length).foreach {if(a(i)==x) true} //you can see why the true is ignored. Foreach() results in Unit. 
Anyways, it will only result in a value if you use the keyword 'yield' and in your example, it would return a List of booleans -which is not what you are looking for.

Thanks,Razvan
On 2011-09-21, at 2:24 PM, Dennis Horte <dennis.horte@gmail.com> wrote:

The for loop does not terminate just because your condition was met. All you tell it to do is output a true. Scala happily outputs values even if nobody wants to use them. Unless there is an explicit return statement, the only thing that gets returned from the function is the last result. The same is true for any code block in Scala.

{ for(i <- 0 to 3) true; false } also always returns false (try it in the repl). The true values are just discarded.

Dennis

On Wed, Sep 21, 2011 at 11:04 AM, Assaf Zaritsky < (assafzar [at] gmail [dot] com> wrote:

Hi,
Consider the following find function that returns true iff a given
value in found in a given array. I am aware there are MUCH better ways
to perform this task, but this is not the question.

def find(a : Array[Int], x : Int) : Boolean ={
   var z : Boolean = false
   for(i <- 0 until a.length)
     if(a(i)==x)
       z=true
   z
 }

This function works as expected
now, consider the following function that should work the same way

def find(a : Array[Int], x : Int) : Boolean ={
   for(i <- 0 until a.length)
     if(a(i)==x)
       true
  false
 }

This function returns false for all inputs although I expect it to do
the same as the upper implementation

I was able to make it work by adding "return true" in the "if"
statement, but I can not understand why it doesn't work from the first
place.

Thanks,
Assaf

uhh.

a.exists(_ == x)

Why are we bothering with this looping stuff?

On Wed, Sep 21, 2011 at 9:48 PM, Razvan Cojocaru wrote:
> It would be much better to NOT call it a 'for loop'. It is a 'for
> comprehension' and it translates into a foreach(), which takes a function
> returning Unit, that's why the "true" is discarded...
> So you basically wrote this: (0 until a.length).foreach {if(a(i)==x) true}
> //you can see why the true is ignored. Foreach() results in Unit.
> Anyways, it will only result in a value if you use the keyword 'yield' and
> in your example, it would return a List of booleans -which is not what you
> are looking for.
>
> Thanks,
> Razvan
> On 2011-09-21, at 2:24 PM, Dennis Horte wrote:
>
> The for loop does not terminate just because your condition was met. All you
> tell it to do is output a true. Scala happily outputs values even if nobody
> wants to use them. Unless there is an explicit return statement, the only
> thing that gets returned from the function is the last result. The same is
> true for any code block in Scala.
>
> { for(i <- 0 to 3) true; false } also always returns false (try it in the
> repl). The true values are just discarded.
>
> Dennis
>
> On Wed, Sep 21, 2011 at 11:04 AM, Assaf Zaritsky wrote:
>>
>> Hi,
>> Consider the following find function that returns true iff a given
>> value in found in a given array. I am aware there are MUCH better ways
>> to perform this task, but this is not the question.
>>
>> def find(a : Array[Int], x : Int) : Boolean ={
>>    var z : Boolean = false
>>    for(i <- 0 until a.length)
>>      if(a(i)==x)
>>        z=true
>>    z
>>  }
>>
>> This function works as expected
>> now, consider the following function that should work the same way
>>
>> def find(a : Array[Int], x : Int) : Boolean ={
>>    for(i <- 0 until a.length)
>>      if(a(i)==x)
>>        true
>>   false
>>  }
>>
>> This function returns false for all inputs although I expect it to do
>> the same as the upper implementation
>>
>> I was able to make it work by adding "return true" in the "if"
>> statement, but I can not understand why it doesn't work from the first
>> place.
>>
>> Thanks,
>> Assaf
>

On Wed, Sep 21, 2011 at 2:48 PM, Razvan Cojocaru wrote:
> It would be much better to NOT call it a 'for loop'. It is a 'for
> comprehension' and it translates into a foreach(), which takes a function
> returning Unit, that's why the "true" is discarded...

Just a little correction: this is actually an example of a 'for loop'.
I believe that the Scala Reference makes a distinction between a 'for
loop' (which uses 'foreach') and a 'for comprehension' (which uses
'flatMap' and 'map')

On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer wrote:
> You could rewrite your function down to a single expression using a fold:
> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)

I know he isn't looking for a working 'find' method, but it's fun to
compare algorithms anyways. Here is a tail recursive example that will
also exit the loop when a match is found:

def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))

On Wed, Sep 21, 2011 at 4:31 PM, Alec Zorab wrote:
> uhh.
>
> a.exists(_ == x)
>
> Why are we bothering with this looping stuff?

I think it is only a simplified example to help find out why he isn't
getting the value he expects.

Indeed, it makes a distinction between a 'for loop' and a 'for expression'.

I think it is misleading to name it 'loop' and to think of it as a loop, which it actually is not! It's just a strait translation to a call to foreach().

Further, I actually strongly recommend that newbies try to refrain from using 'for' and just choose the proper foreach()/map()/flatmap() (ok, maybe not flatmap() just yet), to try to get into the functional mindset. A big light bulb will eventually light up :)

cheers

-----Original Message-----
From: Derek Williams [mailto:derek@fyrie.net]
Sent: September-21-11 6:33 PM
To: Razvan Cojocaru
Cc: Dennis Horte; Assaf Zaritsky; scala-user
Subject: Re: [scala-user] Strange behavior of a simple function

On Wed, Sep 21, 2011 at 2:48 PM, Razvan Cojocaru wrote:
> It would be much better to NOT call it a 'for loop'. It is a 'for
> comprehension' and it translates into a foreach(), which takes a
> function returning Unit, that's why the "true" is discarded...

Just a little correction: this is actually an example of a 'for loop'.
I believe that the Scala Reference makes a distinction between a 'for loop' (which uses 'foreach') and a 'for comprehension' (which uses 'flatMap' and 'map')

--
Derek Williams

Makes me wonder if there is a "fail-fast" version of the fold, or some monadic way to create one. That is, once the accumulator switches to "true" in Derek's fold, the rest of the fold execution is wasted effort. I guess what I'm wondering is if there is an efficient (i.e., "fail-fast") implementation of exists() only using fold(), or flatMap().

Brian Maso

On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams <derek@fyrie.net> wrote:

On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer <thomas.switzer@gmail.com> wrote:
> You could rewrite your function down to a single expression using a fold:
> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)

I know he isn't looking for a working 'find' method, but it's fun to
compare algorithms anyways. Here is a tail recursive example that will
also exit the loop when a match is found:

def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
 if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))

--
Derek Williams

On Wed, Sep 21, 2011 at 19:33, Derek Williams wrote:
> On Wed, Sep 21, 2011 at 2:48 PM, Razvan Cojocaru wrote:
>> It would be much better to NOT call it a 'for loop'. It is a 'for
>> comprehension' and it translates into a foreach(), which takes a function
>> returning Unit, that's why the "true" is discarded...
>
> Just a little correction: this is actually an example of a 'for loop'.
> I believe that the Scala Reference makes a distinction between a 'for
> loop' (which uses 'foreach') and a 'for comprehension' (which uses
> 'flatMap' and 'map')

It does indeed, not that it means much:

scala> class WeirdLoop {
| def foreach[T](f: Int => T) = 1 to 10 map f
| }
defined class WeirdLoop

scala> val y = for (x <- new WeirdLoop) x % 2 == 0
y: scala.collection.immutable.IndexedSeq[Boolean] = Vector(false,
true, false, true, false, true, false, true, false, true)

One could easily give foreach the type signature of a monad, in which
case one could use a "for-loop" as a true monad comprehension (ie,
without the "map" at the end).

On Wed, Sep 21, 2011 at 20:45, Brian Maso wrote:
> Makes me wonder if there is a "fail-fast" version of the fold, or some
> monadic way to create one. That is, once the accumulator switches to "true"
> in Derek's fold, the rest of the fold execution is wasted effort. I guess
> what I'm wondering is if there is an efficient (i.e., "fail-fast")
> implementation of exists() only using fold(), or flatMap().

You can just return at that point. Of course, that will skip any other
code that might be left in the method, but you shouldn't be making
methods that big anyway. ;-)

What actually happens is that an exception is thrown and caught, so
one could simulate it with a try-catch. Just make sure to use a
"cheap" exception.

On 09/22/2011 11:08 AM, Daniel Sobral wrote:
> On Wed, Sep 21, 2011 at 19:33, Derek Williams wrote:
>> On Wed, Sep 21, 2011 at 2:48 PM, Razvan Cojocaru wrote:
>>> It would be much better to NOT call it a 'for loop'. It is a 'for
>>> comprehension' and it translates into a foreach(), which takes a function
>>> returning Unit, that's why the "true" is discarded...
>> Just a little correction: this is actually an example of a 'for loop'.
>> I believe that the Scala Reference makes a distinction between a 'for
>> loop' (which uses 'foreach') and a 'for comprehension' (which uses
>> 'flatMap' and 'map')
> It does indeed, not that it means much:
>
> scala> class WeirdLoop {
> | def foreach[T](f: Int => T) = 1 to 10 map f
> | }
> defined class WeirdLoop
>
> scala> val y = for (x <- new WeirdLoop) x % 2 == 0
> y: scala.collection.immutable.IndexedSeq[Boolean] = Vector(false,
> true, false, true, false, true, false, true, false, true)
>
> One could easily give foreach the type signature of a monad, in which
> case one could use a "for-loop" as a true monad comprehension (ie,
> without the "map" at the end).
>
def mapM[A, B, F[_]: Monad](k: A => F[B], as: List[A]): F[List[B]]

Note:
1) This has the same signature as a regular map except that every type
in return position is wrapped in F.
2) This has the same signature (and indeed, is the same as), the
function traverse mentioned in The Essence of the Iterator Pattern
(which Eric Torreborre has written an excellent article about in a Scala
context).

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 22.09.2011 01:45, schrieb Brian Maso:
> Makes me wonder if there is a "fail-fast" version of the fold, ...

def isTwo (n: Int) : Boolean = {
println (n)
n == 2
}

(false /: (0 to 10)) (_ || isTwo _)

0
1
2
res2: Boolean = true

foldLeft terminates fast. (not: 'fails')

(0 to 10).exists (isTwo)
0
1
2
res3: Boolean = true

exists terminates fast.

On Wed, Sep 21, 2011 at 9:49 PM, Stefan Wagner wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 22.09.2011 01:45, schrieb Brian Maso:
>> Makes me wonder if there is a "fail-fast" version of the fold, ...
>
> def isTwo (n: Int) : Boolean = {
>  println (n)
>  n == 2
> }
>
> (false /: (0 to 10)) (_ || isTwo _)
>
> 0
> 1
> 2
> res2: Boolean = true
>
> foldLeft terminates fast. (not: 'fails')
>

It still loops over all of the elements, just isTwo isn't called
because the function you passed short circuited? That is, if you did
instead:

(false /: (0 to 10))((a,b) => {println(b); a || isTwo(b)})

You'd see it doesn't call isTwo with all of the other elements, but it
does still evaluate the function _ || isTwo _ for each element.
Right?

Not true, as demonstrated by Josh. In fact, I'd be *very* wary of
foldLeft with anything that's supposed to be lazy. See, for instance,
https://issues.scala-lang.org/browse/SI-4582.

On Wed, Sep 21, 2011 at 22:49, Stefan Wagner wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 22.09.2011 01:45, schrieb Brian Maso:
>> Makes me wonder if there is a "fail-fast" version of the fold, ...
>
> def isTwo (n: Int) : Boolean = {
>  println (n)
>  n == 2
> }
>
> (false /: (0 to 10)) (_ || isTwo _)
>
> 0
> 1
> 2
> res2: Boolean = true
>
> foldLeft terminates fast. (not: 'fails')
>
> (0 to 10).exists (isTwo)
> 0
> 1
> 2
> res3: Boolean = true
>
> exists terminates fast.
>
> - --
>
> Tschööö--->...Stefan
> - ---------------------------
> Don't visit my homepage at:
> http://home.arcor-online.net/hirnstrom
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk56lBcACgkQQeATqGpDnRoCmACbBb9wtQO7s4y7i7RBPdxaWtSe
> 7AgAn0o88ZeZWj5cZUk8Ujmnmfjen81i
> =Nqi+
> -----END PGP SIGNATURE-----
>

Nope – but there is this:

 

ts collectFirst { case (test, action) if test(e) => action(e) } - the condition will stop the loop

 

note that collectFirst will take a PartialFunction which you can implement to do whatever before it is applicable J.

 

This is not a monadic operation that I know though. I don’t believe monads include ordering concepts so there’s no point in interrupting a random sequence in an “ordinary” monad.

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of Brian Maso
Sent: September-21-11 7:45 PM
To: Derek Williams
Cc: Tom Switzer; Assaf Zaritsky; scala-user
Subject: Re: [scala-user] Strange behavior of a simple function

 

Makes me wonder if there is a "fail-fast" version of the fold, or some monadic way to create one. That is, once the accumulator switches to "true" in Derek's fold, the rest of the fold execution is wasted effort. I guess what I'm wondering is if there is an efficient (i.e., "fail-fast") implementation of exists() only using fold(), or flatMap().

Brian Maso

On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams <derek@fyrie.net> wrote:

On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer <thomas.switzer@gmail.com> wrote:
> You could rewrite your function down to a single expression using a fold:
> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)

I know he isn't looking for a working 'find' method, but it's fun to
compare algorithms anyways. Here is a tail recursive example that will
also exit the loop when a match is found:

def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
 if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))

--
Derek Williams

 

On Wed, Sep 21, 2011 at 5:45 PM, Brian Maso wrote:
> Makes me wonder if there is a "fail-fast" version of the fold, or some
> monadic way to create one. That is, once the accumulator switches to "true"
> in Derek's fold, the rest of the fold execution is wasted effort. I guess
> what I'm wondering is if there is an efficient (i.e., "fail-fast")
> implementation of exists() only using fold(), or flatMap().

It's possible with Haskell:

Prelude> let find n = foldr (\a b -> a == n || b) False
Prelude> find 3 [1..10]
True
Prelude> find 30 [1..10]
False
Prelude> find 3 [1..]
True

or with Scalaz if using Stream:

scala> def find(s: Stream[Int], n: Int) = s.foldr(false)((a, b) => a == n || b)
find: (s: Stream[Int], n: Int)Boolean

scala> find(Stream.from(0), 3)
res5: Boolean = true

With both I tested with an infinite list (or stream) to make sure that
it terminates when a match is found.

I still prefer my tail recursive solution though.

There's "find", which I personally think is preferable to collectFirst
unless you need to return the same collection or do a mapping after
finding.

On Thu, Sep 22, 2011 at 00:03, Razvan Cojocaru wrote:
> Nope – but there is this:
>
>
>
> ts collectFirst { case (test, action) if test(e) => action(e) } - the
> condition will stop the loop
>
>
>
> note that collectFirst will take a PartialFunction which you can implement
> to do whatever before it is applicable J.
>
>
>
> This is not a monadic operation that I know though. I don’t believe monads
> include ordering concepts so there’s no point in interrupting a random
> sequence in an “ordinary” monad.
>
>
>
> From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On
> Behalf Of Brian Maso
> Sent: September-21-11 7:45 PM
> To: Derek Williams
> Cc: Tom Switzer; Assaf Zaritsky; scala-user
>
> Subject: Re: [scala-user] Strange behavior of a simple function
>
>
>
> Makes me wonder if there is a "fail-fast" version of the fold, or some
> monadic way to create one. That is, once the accumulator switches to "true"
> in Derek's fold, the rest of the fold execution is wasted effort. I guess
> what I'm wondering is if there is an efficient (i.e., "fail-fast")
> implementation of exists() only using fold(), or flatMap().
>
> Brian Maso
>
> On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams wrote:
>
> On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer
> wrote:
>> You could rewrite your function down to a single expression using a fold:
>> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)
>
> I know he isn't looking for a working 'find' method, but it's fun to
> compare algorithms anyways. Here is a tail recursive example that will
> also exit the loop when a match is found:
>
> def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
>  if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))
>
> --
> Derek Williams
>
>

This is a pretty cool question, is there a monadic solution for fast fold, like your example with _ || _ == x.
Say, if x were (somehow) lazy, we would not do the x evaluation after finding truth, but still would be scanning the stream. We need what is called a "monoid with zero" to be sure we can stop.

Thanks,
-Vlad


On Wed, Sep 21, 2011 at 8:03 PM, Razvan Cojocaru <pub@razie.com> wrote:

Nope – but there is this:

 

ts collectFirst { case (test, action) if test(e) => action(e) } - the condition will stop the loop

 

note that collectFirst will take a PartialFunction which you can implement to do whatever before it is applicable J.

 

This is not a monadic operation that I know though. I don’t believe monads include ordering concepts so there’s no point in interrupting a random sequence in an “ordinary” monad.

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of Brian Maso
Sent: September-21-11 7:45 PM
To: Derek Williams
Cc: Tom Switzer; Assaf Zaritsky; scala-user

Subject: Re: [scala-user] Strange behavior of a simple function

 

Makes me wonder if there is a "fail-fast" version of the fold, or some monadic way to create one. That is, once the accumulator switches to "true" in Derek's fold, the rest of the fold execution is wasted effort. I guess what I'm wondering is if there is an efficient (i.e., "fail-fast") implementation of exists() only using fold(), or flatMap().

Brian Maso

On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams <derek@fyrie.net> wrote:

On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer <thomas.switzer@gmail.com> wrote:
> You could rewrite your function down to a single expression using a fold:
> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)

I know he isn't looking for a working 'find' method, but it's fun to
compare algorithms anyways. Here is a tail recursive example that will
also exit the loop when a match is found:

def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
 if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))

--
Derek Williams

 

A fold implies order. The notion of stopping it at some point implies that the elements traversed before that point are different than the elements following. Traversing implies internal structure of the monad – which they don’t like you to see, feel or otherwise be in control of J

 

From: Vlad Patryshev [mailto:vpatryshev@gmail.com]
Sent: September-21-11 11:11 PM
To: Razvan Cojocaru
Cc: Brian Maso; scala-user
Subject: Re: [scala-user] Strange behavior of a simple function

 

This is a pretty cool question, is there a monadic solution for fast fold, like your example with _ || _ == x.

 

Say, if x were (somehow) lazy, we would not do the x evaluation after finding truth, but still would be scanning the stream. We need what is called a "monoid with zero" to be sure we can stop.

 

Thanks,
-Vlad

On Wed, Sep 21, 2011 at 8:03 PM, Razvan Cojocaru <pub@razie.com> wrote:

Nope – but there is this:

 

ts collectFirst { case (test, action) if test(e) => action(e) } - the condition will stop the loop

 

note that collectFirst will take a PartialFunction which you can implement to do whatever before it is applicable J.

 

This is not a monadic operation that I know though. I don’t believe monads include ordering concepts so there’s no point in interrupting a random sequence in an “ordinary” monad.

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of Brian Maso
Sent: September-21-11 7:45 PM
To: Derek Williams
Cc: Tom Switzer; Assaf Zaritsky; scala-user

Subject: Re: [scala-user] Strange behavior of a simple function

 

Makes me wonder if there is a "fail-fast" version of the fold, or some monadic way to create one. That is, once the accumulator switches to "true" in Derek's fold, the rest of the fold execution is wasted effort. I guess what I'm wondering is if there is an efficient (i.e., "fail-fast") implementation of exists() only using fold(), or flatMap().

Brian Maso

On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams <derek@fyrie.net> wrote:

On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer <thomas.switzer@gmail.com> wrote:
> You could rewrite your function down to a single expression using a fold:
> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)

I know he isn't looking for a working 'find' method, but it's fun to
compare algorithms anyways. Here is a tail recursive example that will
also exit the loop when a match is found:

def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
 if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))

--
Derek Williams

 

 

On 21/09/2011 20:04, Assaf Zaritsky wrote:
> Consider the following find function that returns true iff a given
> value in found in a given array. I am aware there are MUCH better ways
> to perform this task, but this is not the question.
>
> def find(a : Array[Int], x : Int) : Boolean ={
> var z : Boolean = false
> for(i<- 0 until a.length)
> if(a(i)==x)
> z=true
> z
> }

I thought: "This calls for having a break after z=true!"...

> This function works as expected
> now, consider the following function that should work the same way
>
> def find(a : Array[Int], x : Int) : Boolean ={
> for(i<- 0 until a.length)
> if(a(i)==x)
> true
> false
> }
>
> This function returns false for all inputs although I expect it to do
> the same as the upper implementation

That's funny, because sometimes I want to do something similar. We assimilated (when
coming from Java world) that 'return' isn't necessary, and even should be avoided, but the
mind (mine, at least) conflates that with "just remove the return where you would put it",
forgetting such statement won't break a loop... :-)

> I was able to make it work by adding "return true" in the "if"
> statement, but I can not understand why it doesn't work from the first
> place.

See above... ^_^'
The 'true' value just does nothing and is probably dropped by the compiler, perhaps making
an empty loop, perhaps even optimizing it away (not sure...).

Use the source, Luke.

http://www.scala-lang.org/api/current/index.html#scala.collection.Traver...

312 def exists(p: A => Boolean): Boolean = {
313 var result = false
314 breakable {
315 for (x <- this)
316 if (p(x)) { result = true; break }
317 }
318 result
319 }

It's very true that subclasses might override and introduce a non fail-
fast exists(). Easy enough to determine that for your data structure
in question.

-ljr

On Sep 21, 6:45 pm, Brian Maso wrote:
> Makes me wonder if there is a "fail-fast" version of the fold, or some
> monadic way to create one. That is, once the accumulator switches to "true"
> in Derek's fold, the rest of the fold execution is wasted effort. I guess
> what I'm wondering is if there is an efficient (i.e., "fail-fast")
> implementation of exists() only using fold(), or flatMap().
>
> Brian Maso
>
>
>
>
>
>
>
> On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams wrote:
> > On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer
> > wrote:
> > > You could rewrite your function down to a single expression using a fold:
> > > def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)
>
> > I know he isn't looking for a working 'find' method, but it's fun to
> > compare algorithms anyways. Here is a tail recursive example that will
> > also exit the loop when a match is found:
>
> > def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
> >  if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))
>
> > --
> > Derek Williams

I meant is it possible to implement in a "pure FP" way, in the Tony Morris sense: no exceptions, no nulls, no casts, no funny business. The fact that the Scala implementors used exception-based controls to do it with efficiency I take it means that it can't be done a "pure FP" way efficiently.

Brian Maso

On Thu, Sep 22, 2011 at 3:12 PM, Lanny Ripple <lanny@spotinfluence.com> wrote:

Use the source, Luke.

http://www.scala-lang.org/api/current/index.html#scala.collection.TraversableLike

312    def exists(p: A => Boolean): Boolean = {
313         var result = false
314         breakable {
315           for (x <- this)
316             if (p(x)) { result = true; break }
317         }
318         result
319       }

It's very true that subclasses might override and introduce a non fail-
fast exists().  Easy enough to determine that for your data structure
in question.

 -ljr

On Sep 21, 6:45 pm, Brian Maso <brian.d.m...@gmail.com> wrote:
> Makes me wonder if there is a "fail-fast" version of the fold, or some
> monadic way to create one. That is, once the accumulator switches to "true"
> in Derek's fold, the rest of the fold execution is wasted effort. I guess
> what I'm wondering is if there is an efficient (i.e., "fail-fast")
> implementation of exists() only using fold(), or flatMap().
>
> Brian Maso
>
>
>
>
>
>
>
> On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams <de...@fyrie.net> wrote:
> > On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer <thomas.swit...@gmail.com>
> > wrote:
> > > You could rewrite your function down to a single expression using a fold:
> > > def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)
>
> > I know he isn't looking for a working 'find' method, but it's fun to
> > compare algorithms anyways. Here is a tail recursive example that will
> > also exit the loop when a match is found:
>
> > def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
> >  if (a.length <= i) false else (a(i) == x || find(a, x, i + 1))
>
> > --
> > Derek Williams

On Thu, Sep 22, 2011 at 11:38 PM, Brian Maso <brian.d.maso@gmail.com> wrote:

I meant is it possible to implement in a "pure FP" way, in the Tony Morris sense: no exceptions, no nulls, no casts, no funny business. The fact that the Scala implementors used exception-based controls to do it with efficiency I take it means that it can't be done a "pure FP" way efficiently.

Yes. Convert it to a scalaz Stream (there is two way to do that, I suggest you don't use the one using fold, but rather using unfold),  then fold over the Stream.
(This is dependant on the earlier mail than foldr is lazy on scalaz stream. )
Best,
Nicolas. 

Ah. I didn't read the question close enough and mistook a post on the
scala-user's list as a discussion of scala and wondered why folks just
didn't look. :)

-ljr

On 09/22/2011 05:38 PM, Brian Maso wrote:
> I meant is it possible to implement in a "pure FP" way, in the Tony Morris
> sense: no exceptions, no nulls, no casts, no funny business. The fact that
> the Scala implementors used exception-based controls to do it with
> efficiency I take it means that it can't be done a "pure FP" way
> efficiently.
>
> Brian Maso
>
> On Thu, Sep 22, 2011 at 3:12 PM, Lanny Ripplewrote:
>
>> Use the source, Luke.
>>
>>
>> http://www.scala-lang.org/api/current/index.html#scala.collection.Traver...
>>
>> 312 def exists(p: A => Boolean): Boolean = {
>> 313 var result = false
>> 314 breakable {
>> 315 for (x<- this)
>> 316 if (p(x)) { result = true; break }
>> 317 }
>> 318 result
>> 319 }
>>
>> It's very true that subclasses might override and introduce a non fail-
>> fast exists(). Easy enough to determine that for your data structure
>> in question.
>>
>> -ljr
>>
>> On Sep 21, 6:45 pm, Brian Maso wrote:
>>> Makes me wonder if there is a "fail-fast" version of the fold, or some
>>> monadic way to create one. That is, once the accumulator switches to
>> "true"
>>> in Derek's fold, the rest of the fold execution is wasted effort. I guess
>>> what I'm wondering is if there is an efficient (i.e., "fail-fast")
>>> implementation of exists() only using fold(), or flatMap().
>>>
>>> Brian Maso
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Wed, Sep 21, 2011 at 3:39 PM, Derek Williams wrote:
>>>> On Wed, Sep 21, 2011 at 12:34 PM, Tom Switzer<
>> thomas.swit...@gmail.com>
>>>> wrote:
>>>>> You could rewrite your function down to a single expression using a
>> fold:
>>>>> def find(a: Array[Int], x: Int): Boolean = (false /: a)(_ || _ == x)
>>>
>>>> I know he isn't looking for a working 'find' method, but it's fun to
>>>> compare algorithms anyways. Here is a tail recursive example that will
>>>> also exit the loop when a match is found:
>>>
>>>> def find(a: Array[Int], x: Int, i: Int = 0): Boolean =
>>>> if (a.length<= i) false else (a(i) == x || find(a, x, i + 1))
>>>
>>>> --
>>>> Derek Williams
>>
>