함수형 프로그래밍, 스칼라 맵 및 왼쪽 접기

함수형 프로그래밍, 스칼라 맵 및 왼쪽 접기

---

왼쪽 접기에 대한 좋은 튜토리얼은 무엇입니까?

다른 답변에 대한 컨텍스트를 제공하기 위해 삭제 후 복원 된 원래 질문 :

사각형, 원, 위치 및 모두 Shape를 확장하는 그룹의 boudning 상자를 찾는 방법을 구현하려고합니다. 그룹은 기본적으로 모양의 배열입니다.

abstract class Shape  
case class Rectangle(width: Int, height: Int) extends Shape  
case class Location(x: Int, y: Int, shape: Shape) extends Shape  
case class Circle(radius: Int) extends Shape  
case class Group(shape: Shape*) extends Shape  

그룹 1을 제외한 세 가지 모두에 대해 경계 상자가 계산되었습니다. 이제 경계 상자 방법의 경우 map을 사용하고 Group에 대해 왼쪽으로 접어야한다는 것을 알고 있지만 정확한 구문을 찾을 수 없습니다.

object BoundingBox {  
  def boundingBox(s: Shape): Location = s match {  
    case Circle(c)=>   
      new Location(-c,-c,s)  
    case Rectangle(_, _) =>  
      new Location(0, 0, s)  
    case Location(x, y, shape) => {  
      val b = boundingBox(shape)  
      Location(x + b.x, y + b.y, b.shape)  
    }  
    case Group(shapes @ _*) =>  ( /: shapes) { } // i dont know how to proceed here.
  }
}

그룹 경계 상자는 기본적으로 모든 모양이 포함 된 가장 작은 경계 상자입니다.

---

거의 완전히 다른 질문을하도록 편집 했으므로 이제 다른 답변을 드리겠습니다. 지도와 접기에 대한 자습서를 가리키는 대신 하나만 제공하겠습니다.

Scala에서는 먼저 익명 함수를 만드는 방법을 알아야합니다. 가장 일반적인 것에서 더 구체적인 것까지 다음과 같이 진행됩니다.

(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 */

여기 예시들이 있습니다 :

(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

이제 map목록 등 의 방법은지도의 모든 요소에 함수 (익명 또는 기타)를 적용합니다. 즉,

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

그때

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

생산하다

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

이것이 유용한 이유는 여러 가지가 있습니다. 많은 문자열이 있고 각각의 길이를 알고 싶거나 모두 대문자로 만들거나 거꾸로 원할 수 있습니다. 하나의 요소에 원하는 작업을 수행하는 함수가있는 경우 map은 모든 요소에 대해 수행합니다.

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)

그래서, 그것은 일반적으로 스칼라의 맵입니다.

하지만 결과를 수집하려면 어떻게해야합니까? 그것이 폴드가 오는 곳입니다 ( foldLeft왼쪽에서 시작하고 오른쪽으로 작동하는 버전).

f:(B,A) => B즉, B와 A를 취하고 결합하여 B를 생성 한다고 가정 합니다. 음, B로 시작하여 A 목록을 한 번에 하나씩 입력 할 수 있습니다. 결국, 우리는 약간의 B를 갖게 될 것입니다. 폴드가하는 일입니다. foldLeft목록의 왼쪽 끝부터 시작합니다. foldRight오른쪽에서 시작합니다. 그건,

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

생산하다

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

b0물론 초기 값은 어디에 있습니까 ?

그래서 아마도 우리는 정수와 문자열을 받아 정수 나 문자열의 길이 중 더 큰 것을 반환하는 함수를 가지고있을 것입니다. 이것을 사용하여 목록을 접 으면 가장 긴 문자열을 알려줄 것입니다. 0으로 시작). 또는 int에 길이를 추가하여 값을 누적 할 수 있습니다.

한번 시도해 봅시다.

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.

---

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.

---

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.)

ReferenceURL : https://stackoverflow.com/questions/2293592/functional-programming-scala-map-and-fold-left