Functional programming, Scala map and fold left [closed]

Solution 1:

Now that you've edited to ask an almost completely different question, I'll give a different answer. Rather than point to a tutorial on maps and folds, I'll just give one.

In Scala, you first need to know how to create an anonymous function. It goes like so, from most general to more specific:

(var1: Type1, var2: Type2, ..., varN: TypeN) => /* output */
(var1, var2, ..., varN) => /* output, if types can be inferred */
var1 => /* output, if type can be inferred and N=1 */

Here are some examples:

(x: Double, y: Double, z: Double) => Math.sqrt(x*x + y*y + z*z)
val f:(Double,Double)=>Double = (x,y) => x*y + Math.exp(-x*y)
val neg:Double=>Double = x => -x

Now, the map method of lists and such will apply a function (anonymous or otherwise) to every element of the map. That is, if you have

List(a1,a2,...,aN)
f:A => B

then

List(a1,a2,...,aN) map (f)

produces

List( f(a1) , f(a2) , ..., f(aN) )

There are all sorts of reasons why this might be useful. Maybe you have a bunch of strings and you want to know how long each is, or you want to make them all upper case, or you want them backwards. If you have a function that does what you want to one element, map will do it to all elements:

scala> List("How","long","are","we?") map (s => s.length)
res0: List[Int] = List(3, 4, 3, 3)

scala> List("How","capitalized","are","we?") map (s => s.toUpperCase)
res1: List[java.lang.String] = List(HOW, CAPITALIZED, ARE, WE?)

scala> List("How","backwards","are","we?") map (s => s.reverse)
res2: List[scala.runtime.RichString] = List(woH, sdrawkcab, era, ?ew)

So, that's map in general, and in Scala.

But what if we want to collect our results? That's where fold comes in (foldLeft being the version that starts on the left and works right).

Suppose we have a function f:(B,A) => B, that is, it takes a B and an A, and combines them to produce a B. Well, we could start with a B, and then feed our list of A's into it one at a time, and at the end of it all, we'd have some B. That's exactly what fold does. foldLeft does it starting from the left end of the list; foldRight starts from the right. That is,

List(a1,a2,...,aN) foldLeft(b0)(f)

produces

f( f( ... f( f(b0,a1) , a2 ) ... ), aN )

where b0 is, of course, your initial value.

So, maybe we have a function that takes an int and a string, and returns the int or the length of the string, whichever is greater--if we folded our list using that, it would tell us the longest string (assuming that we start with 0). Or we could add the length to the int, accumulating values as we go.

Let's give it a try.

scala> List("How","long","is","longest?").foldLeft(0)((i,s) => i max s.length) 
res3: Int = 8

scala> List("How","long","is","everyone?").foldLeft(0)((i,s) => i + s.length)
res4: Int = 18

Okay, fine, but what if we want to know who is the longest? One way (perhaps not the best, but it illustrates a useful pattern well) is to carry along both the length (an integer) and the leading contender (a string). Let's give that a go:

scala> List("Who","is","longest?").foldLeft((0,""))((i,s) => 
     |   if (i._1 < s.length) (s.length,s)
     |   else i
     | )
res5: (Int, java.lang.String) = (8,longest?)

Here, i is now a tuple of type (Int,String), and i._1 is the first part of that tuple (an Int).

But in some cases like this, using a fold isn't really want we want. If we want the longer of two strings, the most natural function would be one like max:(String,String)=>String. How do we apply that one?

Well, in this case, there is a default "shortest" case, so we could fold the string-max function starting with "". But a better way is to use reduce. As with fold, there are two versions, one that works from the left, the other which works from the right. It takes no initial value, and requires a function f:(A,A)=>A. That is, it takes two things and returns one of the same type. Here's an example with a string-max function:

scala> List("Who","is","longest?").reduceLeft((s1,s2) =>              
     |   if (s2.length > s1.length) s2
     |   else s1
     | )
res6: java.lang.String = longest?

Now, there are just two more tricks. First, the following two mean the same thing:

list.foldLeft(b0)(f)
(b0 /: list)(f)

Notice how the second is shorter, and it sort of gives you the impression that you're taking b0 and doing something to the list with it (which you are). (:\ is the same as foldRight, but you use it like so: (list :\ b0) (f)

Second, if you only refer to a variable once, you can use _ instead of the variable name and omit the x => part of the anonymous function declaration. Here are two examples:

scala> List("How","long","are","we?") map (_.length)
res7: List[Int] = List(3, 4, 3, 3)

scala> (0 /: List("How","long","are","we","all?"))(_ + _.length)
res8: Int = 16

At this point, you should be able to create functions and map, fold, and reduce them using Scala. Thus, if you know how your algorithm should work, it should be reasonably straightforward to implement it.

Solution 2:

The basic algorithm would go like this:

shapes.tail.foldLeft(boundingBox(shapes.head)) {
  case (box, shape) if box contains shape => box
  case (box, shape) if shape contains box => shape
  case (box, shape) => boxBounding(box, shape)
}

Now you have to write contains and boxBounding, which is a pure algorithms problem more than a language problem.

If the shapes all had the same center, implementing contains would be easier. It would go like this:

abstract class Shape { def contains(s: Shape): Boolean }
case class Rectangle(width: Int, height: Int) extends Shape {
  def contains(s: Shape): Boolean = s match {
    case Rectangle(w2, h2) => width >= w2 && height >= h2
    case Location(x, y, s) => // not the same center
    case Circle(radius) => width >= radius && height >= radius
    case Group(shapes @ _*) => shapes.forall(this.contains(_))
  }
}
case class Location(x: Int, y: Int, shape: Shape) extends Shape {
  def contains(s: Shape): Boolean = // not the same center
}
case class Circle(radius: Int) extends Shape {
  def contains(s: Shape): Boolean = s match {
    case Rectangle(width, height) => radius >= width && radius >= height
    case Location(x, y) => // not the same center
    case Circle(r2) => radius >= r2
    case Group(shapes @ _*) => shapes.forall(this.contains(_))
  }
}
case class Group(shapes: Shape*) extends Shape {
  def contains(s: Shape): Boolean = shapes.exists(_ contains s)
}

As for boxBounding, which takes two shapes and combine them, it will usually be a rectangle, but can be a circle under certain circunstances. Anyway, it is pretty straight-forward, once you have the algorithm figured out.

Solution 3:

A bounding box is usually a rectangle. I don't think a circle located at (-r,-r) is the bounding box of a circle of radius r....

Anyway, suppose you have a bounding box b1 and another b2 and a function combineBoxes that computes the bounding box of b1 and b2.

Then if you have a non-empty set of shapes in your group, you can use reduceLeft to compute the whole bounding box of a list of bounding boxes by combining them two at a time until only one giant box remains. (The same idea can be used to reduce a list of numbers to a sum of numbers by adding them in pairs. And it's called reduceLeft because it works left to right across the list.)

Suppose that blist is a list of bounding boxes of each shape. (Hint: this is where map comes in.) Then

val bigBox = blist reduceLeft( (box1,box2) => combineBoxes(box1,box2) )

You'll need to catch the empty group case separately, however. (Since it has a no well-defined bounding box, you don't want to use folds; folds are good for when there is a default empty case that makes sense. Or you have to fold with Option, but then your combining function has to understand how to combine None with Some(box), which is probably not worth it in this case--but very well might be if you were writing production code that needs to elegantly handle various sorts of empty list situations.)