4

I have a List that contains, 1s and -1s. The goal I'm after is to find the position in the List when the total is -1. 

List[Int] = List(1, -1, 1, -1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 
-1, 1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1)

But my code is not working.

Here are my attempts(I spaced the code out for better reading) Note: floor is the val that holds the List of Ints.

floor.foldLeft(0) { ( (x,y) => x+y == -1 ) }.indexOf(-1)

floor.foldLeft(0) ( (x,y) => {  (x + y == -1) {x.indexOf(-1)} }  )

floor.foldLeft(0) { (x,y) => { if (x + y == -1) { indexOf(-1) } } }

I'd like to know what I'm doing wrong here. I'm really after the why more than the answer in and of itself.

Maytham Fahmi
  • 31,138
  • 14
  • 118
  • 137
Native
  • 73
  • 1
  • 5
  • All your solutions miss an important point about foldLeft. The value `x` takes is the type of the initial value, in this case, `0` and the type returned by the function should have this type. In the first example, it's boolean. The other two just don't make sense. – pedrofurla Aug 11 '16 at 04:32

2 Answers2

3

The anonymous function (the 2nd argument to foldLeft) needs to return the same type as the 1st argument.

The fold and reduce families are designed to take a collection and reduce it to a single value. It's not going to work for you here.

This will get you what you want.

floor.scanLeft(0)(_+_).indexOf(-1) - 1  // scan collection is 1 element longer

In this case scan produces a new collection with different properties/values that can be queried for elements of interest.

So if you really need to use foldLeft, try this.

floor.zipWithIndex.foldLeft((0,-1)) {
  case ((s,x),(e,i)) => if (s+e == -1 && x < 0) (0,i) else (s+e, x)
}._2

Pretty ugly because you have to carry around the current sum, s, and the index of where you are, i, and the current element being evaluated, e, and after you find your goal, x, you have to keep it around and unpack it at the end, ._2.

Compare the result with the scanLeft version. I think you'll find that the final - 1 adjustment is needed.

Here's one other approach that has the benefit of bailing out early if/when the desired target is reached.

val floorSums:Stream[Int] = Stream.tabulate(floor.length){ idx =>
     floor(idx) + (if (idx>0) floorSums(idx-1) else 0)
}

floorSums.indexOf(-1)  // 38
jwvh
  • 50,871
  • 7
  • 38
  • 64
  • are you sure indexOf(-1) works for every occurance? The element -1 appears many times in the collection. – 0x6C38 Aug 11 '16 at 01:34
  • @MrD, the value `-1` appears twice in the resulting scan collection. `indexOf(-1)` returns `39` which is the first occurrence. – jwvh Aug 11 '16 at 01:39
  • This is from Advent of Code day 1 part 2. scanLeft(0)(_+_).indexOf(-1) produced the right solution link: http://mo.github.io/2016/01/09/advent-of-code.html. No need for -1. Here for a tuple: https://github.com/jrohland/adventofcode-scala/blob/master/src/Day01Part2.scala Question is, how can it be achieved with foldLeft and why am I not able to achieve the desired result with foldLeft ? – Native Aug 11 '16 at 02:30
  • As I understand it. With foldLeft, it is a curried function. And it goes foo.foldLeft(initial value)(total, next). So: foo.foldLeft(initial value)(total, next) { What can I do in this area to get my result, or am I in the wrong place, do I have curly braces in the wrong place ? Because all the first parameter is good for is setting up a inital value, all the action happens in the second parameter. – Native Aug 11 '16 at 02:38
  • It's less complicated when you use the correct tools (`scanLeft`). When you try to clear a drain pipe with a hammer it gets more complicated. – jwvh Aug 11 '16 at 07:35
2

There are two styles of solution to a problem like this where you may need to bail out partway through an operation (in this case a fold).

One style is to use a non-local return inside a def you write just for this purpose (note that .zipWithIndex turns every element into a pair of elements: the original plus the index):

def exceedsTen(xs: List[Int]): Int = {
  xs.zipWithIndex.foldLeft(0){ (sum, x) =>
    val now = sum + x._1
    if (now > 10) return x._2
    else now
  }
  -1
}

The other style is to have some value that you can pass along to indicate that you're done--so you really do traverse all the rest of the list, but you don't do any work because you know you don't have to.

def overTen(xs: List[Int]): Int = {
  val pair = 
    xs.foldLeft((0, 0)){ (si, x) =>
      if (si._1 > 10) si
      else (si._1 + x, si._2 + 1)
    }
  if (pair._1 > 10) si._2 else -1
}

In this case, keeping a running total and the index where you found what you were looking for takes a little more space but is arguably a little clearer once you're familiar with both forms.

In general, finding indices of things is a kind of a niche application; you want to do something not just find something and hang on to the position for later.

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407