StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p>In Scala, you first need to know how to create an anonymous function. It goes like so, from most general to more specific:</p> <pre><code>(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 */ </code></pre> <p>Here are some examples:</p> <pre><code>(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 </code></pre> <p>Now, the <code>map</code> method of lists and such will apply a function (anonymous or otherwise) to every element of the map. That is, if you have</p> <pre><code>List(a1,a2,...,aN) f:A => B </code></pre> <p>then</p> <pre><code>List(a1,a2,...,aN) map (f) </code></pre> <p>produces</p> <pre><code>List( f(a1) , f(a2) , ..., f(aN) ) </code></pre> <p>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 <em>one</em> element, map will do it to all elements:</p> <pre><code>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) </code></pre> <p>So, that's map in general, and in Scala.</p> <p>But what if we want to collect our results? That's where fold comes in (<code>foldLeft</code> being the version that starts on the left and works right).</p> <p>Suppose we have a function <code>f:(B,A) => B</code>, 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. <code>foldLeft</code> does it starting from the left end of the list; <code>foldRight</code> starts from the right. That is,</p> <pre><code>List(a1,a2,...,aN) foldLeft(b0)(f) </code></pre> <p>produces</p> <pre><code>f( f( ... f( f(b0,a1) , a2 ) ... ), aN ) </code></pre> <p>where <code>b0</code> is, of course, your initial value.</p> <p>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.</p> <p>Let's give it a try.</p> <pre><code>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 </code></pre> <p>Okay, fine, but what if we want to know <em>who</em> 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) <em>and</em> the leading contender (a string). Let's give that a go:</p> <pre><code>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?) </code></pre> <p>Here, <code>i</code> is now a tuple of type <code>(Int,String)</code>, and <code>i._1</code> is the first part of that tuple (an Int).</p> <p>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 <code>max:(String,String)=>String</code>. How do we apply that one?</p> <p>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 <em>reduce</em>. 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 <code>f:(A,A)=>A</code>. That is, it takes two things and returns one of the same type. Here's an example with a string-max function:</p> <pre><code>scala> List("Who","is","longest?").reduceLeft((s1,s2) => | if (s2.length > s1.length) s2 | else s1 | ) res6: java.lang.String = longest? </code></pre> <p>Now, there are just two more tricks. First, the following two mean the same thing:</p> <pre><code>list.foldLeft(b0)(f) (b0 /: list)(f) </code></pre> <p>Notice how the second is shorter, and it sort of gives you the impression that you're taking <code>b0</code> and doing something to the list with it (which you are). (<code>:\</code> is the same as <code>foldRight</code>, but you use it like so: <code>(list :\ b0) (f)</code></p> <p>Second, if you only refer to a variable once, you can use <code>_</code> instead of the variable name and omit the <code>x =></code> part of the anonymous function declaration. Here are two examples:</p> <pre><code>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 </code></pre> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload