git » homepage.git » master » tree

[master] / archive / linked-pages / raw / f964c5792f0df968.html

<!DOCTYPE html>
<script>var __pbpa = true;</script><script>var translated_warning_string = 'Warning: Never enter your Tumblr password unless \u201chttps://www.tumblr.com/login\u201d\x0ais the address in your web browser.\x0a\x0aYou should also see a green \u201cTumblr, Inc.\u201d identification in the address bar.\x0a\x0aSpammers and other bad guys use fake forms to steal passwords.\x0a\x0aTumblr will never ask you to log in from a user\u2019s blog.\x0a\x0aAre you absolutely sure you want to continue?';</script><script type="text/javascript" language="javascript" src="http://assets.tumblr.com/assets/scripts/pre_tumblelog.js?_v=458fd058fd98acfbef62c7255aaa6b24"></script>
<!DOCTYPE html>
<html>
<head prefix="og: http://ogp.me/ns# fb: http://ogp.me/ns/fb# blog: http://ogp.me/ns/blog#">
	<meta charset="UTF-8">
	<title>Polyglot Folding (Ruby, Clojure, Scala) - alan dipert</title>
	<link rel="shortcut icon" href="http://24.media.tumblr.com/avatar_4ae064934cfd_16.png">
	<link rel="alternate" type="application/rss+xml" href="http://alan.dipert.org/rss">
    
    <meta name="description" content="Polyglot Folding (Ruby, Clojure, Scala) fold in a nutshell It&rsquo;s common to use the fold family of higher order functions (inject, reduce, and friends, depending on the language) to &ldquo;reduce&rdquo; some..." />
          
	<meta name="if:Show notes" content="1">
	<meta name="text:Disqus Shortname" content="" />
	<meta name="color:Post Background" content="#F2F2F2" />		
	<link rel="stylesheet" href="http://static.tumblr.com/26l8vc7/ej3lr0jwd/style.css">
	<style type="text/css">
		.post{background: #F2F2F2;}
		
	</style>
    <script type="text/javascript" src="http://shjs.sourceforge.net/sh_main.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_css.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_html.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_java.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_sh.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_c.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_scala.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_cpp.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_php.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_ruby.min.js">

</script>

<script type="text/javascript" 

src="http://shjs.sourceforge.net/lang/sh_javascript.min.js">

</script>

<link type="text/css" rel="stylesheet" href="http://shjs.sourceforge.net/sh_style.css">
<script type="text/javascript">

  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-965358-1']);
  _gaq.push(['_trackPageview']);

  (function() {
    var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
    ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
  })();

</script>

<!-- BEGIN TUMBLR FACEBOOK OPENGRAPH TAGS -->
<!-- If you'd like to specify your own Open Graph tags, define the og:url and og:title tags in your theme's HTML. -->
<!-- Read more: http://ogp.me/ -->
<meta property="fb:app_id" content="48119224995" />
<meta property="og:title" content="Polyglot Folding (Ruby, Clojure, Scala)" />
<meta property="og:url" content="http://alan.dipert.org/post/307586762/polyglot-folding-ruby-clojure-scala" />
<meta property="og:description" content="fold in a nutshell
It&rsquo;s common to use the fold family of higher order functions (inject, reduce, and friends, depending on the language) to &ldquo;reduce&rdquo; some sequence to a single value through sequential..." />
<meta property="og:type" content="tumblr-feed:entry" />
<!-- END TUMBLR FACEBOOK OPENGRAPH TAGS -->


<!-- TWITTER TAGS -->
<meta charset="utf-8">
            <meta name="twitter:card" content="summary" />
            <meta name="twitter:description" content="fold in a nutshell
 It&amp;#8217;s common to use the fold family of higher order functions (inject, reduce, and friends, depending on the language) to &amp;#8220;reduce&amp;#8221; some sequence to a single value through sequential application of a function taking two arguments. &nbsp;It&amp;#8217;s often used to do things like sum an array of integers. &nbsp;Because this usage is so common, fold is often thought of as a &amp;#8220;destructive&amp;#8221; or &amp;#8220;information-losing&amp;#8221; operation.
 It doesn&amp;#8217;t need to be. &nbsp;Below you&amp;#8217;ll find examples offered up in Ruby, Scala, and Clojure that demonstrate use of an explicity supplied accumulator value. &nbsp;This technique allows for more powerful folds and serves as a way to more concisely write what in imperative languages would involve a loop and a temporary variable.
 This post is probably more for me than for you, but I hope you enjoy it nonetheless, and I welcome comments and suggestions.

 intro to folding
 in Ruby
 In Ruby, to find the sum of an array of numbers, one might write something like this:
[1,2,3].inject{|l,r| l+r}

 In this case [1], the Proc {|l,r| l+r} is passed to the inject [2] method of the Array class. &nbsp;inject calls the function with arguments l = 1 and r = 2, the left-most elements in the array. &nbsp;The result of this application is the number 3, which is stored.
 As long as elements remain in the sequence, the result of the previous application is stored and used as the &amp;#8220;left&amp;#8221; argument to the function, and the next element of the sequence is used as the &amp;#8220;right&amp;#8221; argument. &nbsp;This continual application of the function using the current result and next element continues left to right, until no elements remain.
 So, after the result 3 stored, {|l,r| l+r} is called again with l = 3 and r = 3. &nbsp;The result of this call is 6, which is then returned, since no elements remain. [3]
 in Scala
 Scala, like Ruby, supports the notion of first-class functions and as such provides also a &amp;#8220;reduce&amp;#8221; method on collections like arrays.
 The most Ruby-like example might be:
Array(1,2,3).reduceLeft((l,r) =&amp;gt; l+r))

 As in the Ruby example, a method taking two arguments is passed to reduceLeft and elements in the array are sequentially added together left to right, and a sum is returned when no elements remain. [4]
 in Clojure
 While Clojure&amp;#8217;s syntax is much different than Ruby&amp;#8217;s or Scala&amp;#8217;s, the basic ingredients of folding can be recognized in this snippet:
(reduce (fn [l r] (+ l r)) [1 2 3])
 Here, the function reduce is called with two arguments: a function taking two arguments, and a sequence (in this case a vector) of values on which to operate.
 The idiomatic way to write this, which doesn&amp;#8217;t require us to wrap + with an anonymous function, looks like this [5]:
(reduce + [1 2 3])
 nondestructive folding
 So far, the examples have assumed that the &amp;#8220;accumulator&amp;#8221; value - the value that is continually passed as the left argument to the function as fold moves left to right - is of the same type as the elements of the sequence. &nbsp;In the examples, this has been an integer. &nbsp;Because the accumulator is also the value that is returned by fold, all of the examples above return not an array but an integer value: the sum.
 However, many implementations of &amp;#8220;fold left&amp;#8221; allow specifying an initial value manually. &nbsp;This value can be any type, including an array or sequence, as long as the function provided recognizes the left argument as such.
 This allows for &amp;#8220;nondestructive folding,&amp;#8221; since in some sense the accumulator value now has the same ability to store information as the sequence on which fold is operating.
 the running sums problem
 Suppose you have a sequence of numbers like [1,2,3], and that you&amp;#8217;d like to create an array representing the &amp;#8220;running sum&amp;#8221; of these numbers. &nbsp;That is, you&amp;#8217;d like to create a new array, [1,3,6], that stored at each old element&amp;#8217;s position the sum of the old element and all of the old elements to its left.
 I can&amp;#8217;t find the logs, but this was a question posed in #scala IRC a few months ago. &nbsp;Paul Phillips offered a solution similar to this one:
List(1,2,3).foldLeft(List(0))((xs,y) =&amp;gt; List(xs.head + y) ++ xs).reverse.tail
 wtf
 in Scala
 Instead of Array.reduceLeft, we&amp;#8217;re using List.foldLeft, which takes two arguments:
 an initial value for the accumulator: List(0)
 a function taking the initial value as its first argument, and an element from the original List as its second argument: ((xs,y) =&amp;gt; List(xs.head + y) ++ xs)
 So, when foldLeft first calls ((xs,y)&amp;#8230;, xs = List(0) and y = 1. &nbsp;In the function body, the statement:
xs.head + y
 ..adds the &amp;#8220;head&amp;#8221; (or first element) of xs, which is 0, to the first element of the original list, which is 1. &nbsp;This result is then used to create another list containing a single value, the result of this addition:
List(xs.head + y)
 Then, we use List&amp;#8217;s concatenation method, ++, to prepend the contents of this list to xs:
List(xs.head + y) ++ xs
 This value, the product of appending our new list with the old one, is returned and stored by foldLeft as the new value of the accumulator. &nbsp;It&amp;#8217;s subsequently passed again to ((xs,y) =&amp;gt;&amp;#8230; as xs, with y = 2, the next value in the original list.
 This passing, evaluation, and array-munging continues until every original element has been iterated over. &nbsp;The final result of foldLeft by itself:
List(1,2,3).foldLeft(List(0))((xs,y) =&amp;gt; List(xs.head + y) ++ xs)
 &amp;#8230; is actually&nbsp;List(6, 3, 1, 0), because we &amp;#8220;built&amp;#8221; the accumulator backwards and kept its first element, 0. &nbsp;To get the result we want, we must reverse the list (List.reverse) and drop the 0 (List.tail). &nbsp;We then end up with paulp&amp;#8217;s solution. [6]
 in Ruby
 Ruby&amp;#8217;s Array class doesn&amp;#8217;t provide a foldLeft method, but it does offer a two argument form of inject that behaves exactly the same way. &nbsp;It takes an initial value, and a function to execute for each element, which is expected to take the accumulator value as the first argument.
 It looks like this:
[1,2,3].inject([0]){|xs,y| xs.unshift(xs.first + y) }.reverse.slice(1..-1)
 Ruby&amp;#8217;s semantics for prepending an element to an array (unshift) and for dropping the first element of an array (slice(1..-1)) differ from Scala&amp;#8217;s, but the spirit of the code is basically the same. &nbsp;Like the Scala implementation, variations are possible that might be more efficient. [6]
 in Clojure
 Clojure, owing to Lisp syntax, is sort of the inside-out version of the previous two implementations:
(rest (reverse (reduce (fn [xs y] (cons (+ (first xs) y) xs)) &#039;(0) [1 2 3])))
 Clojure&amp;#8217;s reduce, like Ruby&amp;#8217;s inject, provides a form capable of taking an initial value instead of a separate function like Scala&amp;#8217;s foldLeft.
 I&amp;#8217;m pretty new to Clojure, but I think a more idiomatic approach might be to use Clojure&amp;#8217;s short hand function definition:
(rest (reverse (reduce #(cons (+ (first %1) %2) %1) &#039;(0) [1 2 3])))
 Like Ruby and Scala, many variations are possible, and they all depend on your particular problem and the affordances of available data structures.
 For instance, in this Clojure version, we might use a vector instead of a list and shorten it up a bit:
(rest (reduce #(conj %1 (+ (last %1) %2)) [0] [1 2 3]))
 I haven&amp;#8217;t tested whether this is faster or better in any way, but it seems to work.
 &amp;#8220;summing&amp;#8221; up
 There&amp;#8217;s a lot to &amp;#8220;functional programming style,&amp;#8221; and I don&amp;#8217;t claim to be an expert. &nbsp;paulp&amp;#8217;s running sums solution was the first example I&amp;#8217;d seen of using a collection as an accumulator, but I&amp;#8217;ve since had a lot of fun with folding in both Ruby and Clojure. &nbsp;It seems to be a pretty neat way to tighten up what in other languages would be explicit loops.
 While fold is a functional standby and will probably be available in languages for a very long time, it&amp;#8217;s not without criticism. &nbsp;In a recent presentation, Guy Steele considered foldl and foldr &amp;#8220;slightly harmful&amp;#8221; and emphasized the importance of a &amp;#8220;divide and&nbsp;conquer&amp;#8221; &nbsp;approach instead of an &amp;#8220;accumulator&amp;#8221; approach. &nbsp;The PDF of his presentation elaborates on this.
 notes
 A shorter, cleverer, and somewhat mystical way to sum an array in Ruby is
[1,2,3].inject(:+)
Reg Braithwaite put together a comprehensive blog post covering the nuances of Ruby&amp;#8217;s inject, if you&amp;#8217;d like to learn more. 
 Ruby&amp;#8217;s inject is comparable to the foldl or &amp;#8220;fold left&amp;#8221; of other languages, but is named in the Smalltalk tradition.
 Many languages offer also a foldr, or &amp;#8220;fold right&amp;#8221; function which behaves like inject except operates from right to left in the sequence.
 Like Ruby, Scala provides a shortcut:
Array(1,2,3).reduceLeft(_+_)
Because this use of reduceLeft is so common, Scala 2.8 provides a &amp;#8220;sum&amp;#8221; method on numeric collections:
Array(1,2,3).sum

 In the two argument form, Clojure&amp;#8217;s reduce is equivalent to apply:
(apply + [1 2 3])

 It&amp;#8217;s possible implement this in such a way as to append, rather than prepend, results.  This approach means that reverse isn&amp;#8217;t necessary, but might be slower and/or more complicated depending on the implementation of the collection.
" />
            <meta name="twitter:title" content="Polyglot Folding (Ruby, Clojure, Scala)" />
            <meta name="twitter:url" content="http://alan.dipert.org/post/307586762/polyglot-folding-ruby-clojure-scala" />
            <meta name="twitter:site" content="tumblr" />
            <meta name="twitter:app:name:iphone" content="Tumblr" />
            <meta name="twitter:app:name:ipad" content="Tumblr" />
            <meta name="twitter:app:name:googleplay" content="Tumblr" />
            <meta name="twitter:app:id:iphone" content="305343404" />
            <meta name="twitter:app:id:ipad" content="305343404" />
            <meta name="twitter:app:id:googleplay" content="com.tumblr" />
            <meta name="twitter:app:url:iphone" content="tumblr://x-callback-url/blog?blogName=alandipert&amp;postID=307586762&amp;referrer=twitter-cards" />
            <meta name="twitter:app:url:ipad" content="tumblr://x-callback-url/blog?blogName=alandipert&amp;postID=307586762&amp;referrer=twitter-cards" />
            <meta name="twitter:app:url:googleplay" content="tumblr://x-callback-url/blog?blogName=alandipert&amp;postID=307586762&amp;referrer=twitter-cards" />
    

<script type="text/javascript" src="http://assets.tumblr.com/assets/scripts/tumblelog.js?_v=6e220a0140f545ead40966867db8d6db"></script><meta http-equiv="x-dns-prefetch-control" content="off"/></head>
<body>
	<div id="wrapper">
		<div id="header" role="banner">
			<h1><a href="/">alan dipert</a></h1>
			
			
			<div id="description">
				<p><p><a href = "http://twitter.com/alandipert/">twitter</a>&nbsp;<a href = "http://github.com/alandipert/">github</a>&nbsp;<a href = "mailto:adipert@acm.org">email</a></p></p>
			</div>
			
		</div>
		
		<div id="content" role="main">
    		
    
    
    
    
			
			
					
					<div class="post text">
						 
						<div class="date">
							<p><span class="day">30</span> 12 / 2009</p>
						</div>
						
						
						<div class="content">
							
							<h2>Polyglot Folding (Ruby, Clojure, Scala)</h2>
							
		
							<p><b>fold in a nutshell</b></p>
<p>It&#8217;s common to use the <a href="http://en.wikipedia.org/wiki/Fold_(higher-order_function)">fold</a> family of higher order functions (inject, reduce, and friends, depending on the language) to &#8220;reduce&#8221; some sequence to a single value through sequential application of a function taking two arguments.  It&#8217;s often used to do things like sum an array of integers.  Because this usage is so common, fold is often thought of as a &#8220;destructive&#8221; or &#8220;information-losing&#8221; operation.</p>
<p>It doesn&#8217;t need to be.  Below you&#8217;ll find examples offered up in Ruby, Scala, and Clojure that demonstrate use of an explicity supplied accumulator value.  This technique allows for more powerful folds and serves as a way to more concisely write what in imperative languages would involve a loop and a temporary variable.</p>
<p>This post is probably more for me than for you, but I hope you enjoy it nonetheless, and I welcome comments and suggestions.</p>
<!-- more -->
<p><b>intro to folding</b></p>
<p><i>in Ruby</i></p>
<p>In Ruby, to find the sum of an array of numbers, one might write something like this:</p>
<pre class="sh_ruby">[1,2,3].inject{|l,r| l+r}
</pre>
<p>In this case [1], the Proc {|l,r| l+r} is passed to the inject [2] method of the Array class.  inject calls the function with arguments l = 1 and r = 2, the left-most elements in the array.  The result of this application is the number 3, which is stored.</p>
<p>As long as elements remain in the sequence, the result of the previous application is stored and used as the &#8220;left&#8221; argument to the function, and the next element of the sequence is used as the &#8220;right&#8221; argument.  This continual application of the function using the current result and next element continues left to right, until no elements remain.</p>
<p>So, after the result 3 stored, {|l,r| l+r} is called again with l = 3 and r = 3.  The result of this call is 6, which is then returned, since no elements remain. [3]</p>
<p><i>in Scala</i></p>
<p>Scala, like Ruby, supports the notion of first-class functions and as such provides also a &#8220;reduce&#8221; method on collections like arrays.</p>
<p>The most Ruby-like example might be:</p>
<pre class="sh_scala">Array(1,2,3).reduceLeft((l,r) =&gt; l+r))
</pre>
<p>As in the Ruby example, a method taking two arguments is passed to reduceLeft and elements in the array are sequentially added together left to right, and a sum is returned when no elements remain. [4]</p>
<p><i>in Clojure</i></p>
<p>While Clojure&#8217;s syntax is much different than Ruby&#8217;s or Scala&#8217;s, the basic ingredients of folding can be recognized in this snippet:</p>
<pre>(reduce (fn [l r] (+ l r)) [1 2 3])</pre>
<p>Here, the function reduce is called with two arguments: a function taking two arguments, and a sequence (in this case a vector) of values on which to operate.</p>
<p>The idiomatic way to write this, which doesn&#8217;t require us to wrap + with an anonymous function, looks like this [5]:</p>
<pre>(reduce + [1 2 3])</pre>
<p><b>nondestructive folding</b></p>
<p>So far, the examples have assumed that the &#8220;accumulator&#8221; value - the value that is continually passed as the left argument to the function as fold moves left to right - is of the same type as the elements of the sequence.  In the examples, this has been an integer.  Because the accumulator is also the value that is returned by fold, all of the examples above return not an array but an integer value: the sum.</p>
<p>However, many implementations of &#8220;fold left&#8221; allow specifying an initial value manually.  This value can be any type, including an array or sequence, as long as the function provided recognizes the left argument as such.</p>
<p>This allows for &#8220;nondestructive folding,&#8221; since in some sense the accumulator value now has the same ability to store information as the sequence on which fold is operating.</p>
<p><b>the running sums problem</b></p>
<p>Suppose you have a sequence of numbers like [1,2,3], and that you&#8217;d like to create an array representing the &#8220;running sum&#8221; of these numbers.  That is, you&#8217;d like to create a new array, [1,3,6], that stored at each old element&#8217;s position the sum of the old element and all of the old elements to its left.</p>
<p>I can&#8217;t find the logs, but this was a question posed in #scala IRC a few months ago.  <a href="http://www.improving.org/paulp/">Paul Phillips</a> offered a solution similar to this one:</p>
<pre class="sh_scala">List(1,2,3).foldLeft(List(0))((xs,y) =&gt; List(xs.head + y) ++ xs).reverse.tail</pre>
<p><b>wtf</b></p>
<p><i>in Scala</i></p>
<p>Instead of Array.reduceLeft, we&#8217;re using List.foldLeft, which takes two arguments:</p>
<ul><li>an initial value for the accumulator: List(0)</li>
<li>a function taking the initial value as its first argument, and an element from the original List as its second argument: ((xs,y) =&gt; List(xs.head + y) ++ xs)</li>
</ul><p>So, when foldLeft first calls ((xs,y)&#8230;, xs = List(0) and y = 1.  In the function body, the statement:</p>
<pre class="sh_scala">xs.head + y</pre>
<p>..adds the &#8220;head&#8221; (or first element) of xs, which is 0, to the first element of the original list, which is 1.  This result is then used to create another list containing a single value, the result of this addition:</p>
<pre class="sh_scala">List(xs.head + y)</pre>
<p>Then, we use List&#8217;s concatenation method, ++, to prepend the contents of this list to xs:</p>
<pre class="sh_scala">List(xs.head + y) ++ xs</pre>
<p>This value, the product of appending our new list with the old one, is returned and stored by foldLeft as the new value of the accumulator.  It&#8217;s subsequently passed again to ((xs,y) =&gt;&#8230; as xs, with y = 2, the next value in the original list.</p>
<p>This passing, evaluation, and array-munging continues until every original element has been iterated over.  The final result of foldLeft by itself:</p>
<pre class="sh_scala">List(1,2,3).foldLeft(List(0))((xs,y) =&gt; List(xs.head + y) ++ xs)</pre>
<p>&#8230; is actually List(6, 3, 1, 0), because we &#8220;built&#8221; the accumulator backwards and kept its first element, 0.  To get the result we want, we must reverse the list (List.reverse) and drop the 0 (List.tail).  We then end up with paulp&#8217;s solution. [6]</p>
<p><i>in Ruby</i></p>
<p>Ruby&#8217;s Array class doesn&#8217;t provide a foldLeft method, but it does offer a<a href="http://ruby-doc.org/core/classes/Enumerable.html#M003129"> two argument form of inject</a> that behaves exactly the same way.  It takes an initial value, and a function to execute for each element, which is expected to take the accumulator value as the first argument.</p>
<p>It looks like this:</p>
<pre class="sh_ruby">[1,2,3].inject([0]){|xs,y| xs.unshift(xs.first + y) }.reverse.slice(1..-1)</pre>
<p>Ruby&#8217;s semantics for prepending an element to an array (unshift) and for dropping the first element of an array (slice(1..-1)) differ from Scala&#8217;s, but the spirit of the code is basically the same.  Like the Scala implementation, variations are possible that might be more efficient. [6]</p>
<p><i>in Clojure</i></p>
<p>Clojure, owing to Lisp syntax, is sort of the inside-out version of the previous two implementations:</p>
<pre>(rest (reverse (reduce (fn [xs y] (cons (+ (first xs) y) xs)) '(0) [1 2 3])))</pre>
<p>Clojure&#8217;s reduce, like Ruby&#8217;s inject, provides a form capable of taking an initial value instead of a separate function like Scala&#8217;s foldLeft.</p>
<p>I&#8217;m pretty new to Clojure, but I think a more idiomatic approach might be to use Clojure&#8217;s short hand function definition:</p>
<pre>(rest (reverse (reduce #(cons (+ (first %1) %2) %1) '(0) [1 2 3])))</pre>
<p>Like Ruby and Scala, many variations are possible, and they all depend on your particular problem and the affordances of available data structures.</p>
<p>For instance, in this Clojure version, we might use a vector instead of a list and shorten it up a bit:</p>
<pre>(rest (reduce #(conj %1 (+ (last %1) %2)) [0] [1 2 3]))</pre>
<p>I haven&#8217;t tested whether this is faster or better in any way, but it seems to work.</p>
<p><b>&#8220;summing&#8221; up</b></p>
<p>There&#8217;s a lot to &#8220;functional programming style,&#8221; and I don&#8217;t claim to be an expert.  paulp&#8217;s running sums solution was the first example I&#8217;d seen of using a collection as an accumulator, but I&#8217;ve since had a lot of fun with folding in both Ruby and Clojure.  It seems to be a pretty neat way to tighten up what in other languages would be explicit loops.</p>
<p>While fold is a functional standby and will probably be available in languages for a very long time, it&#8217;s not without criticism.  In a recent presentation, Guy Steele considered foldl and foldr &#8220;slightly harmful&#8221; and emphasized the importance of a &#8220;divide and conquer&#8221;  approach instead of an &#8220;accumulator&#8221; approach.  The <a href="http://research.sun.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf">PDF of his presentation</a> elaborates on this.</p>
<p><b>notes</b></p>
<ol><li>A shorter, cleverer, and somewhat mystical way to sum an array in Ruby is
<pre class="sh_ruby">[1,2,3].inject(:+)</pre>
Reg Braithwaite put together <a href="http://weblog.raganwald.com/2008/02/1100inject.html">a comprehensive blog post</a> covering the nuances of Ruby&#8217;s inject, if you&#8217;d like to learn more. </li>
<li>Ruby&#8217;s inject is comparable to the foldl or &#8220;fold left&#8221; of other languages, but is named in the Smalltalk tradition.</li>
<li>Many languages offer also a foldr, or &#8220;fold right&#8221; function which behaves like inject except operates from right to left in the sequence.</li>
<li>Like Ruby, Scala provides a shortcut:
<pre class="sh_scala">Array(1,2,3).reduceLeft(_+_)</pre>
Because this use of reduceLeft is so common, Scala 2.8 provides a &#8220;sum&#8221; method on numeric collections:
<pre class="sh_scala">Array(1,2,3).sum</pre>
</li>
<li>In the two argument form, Clojure&#8217;s reduce is equivalent to apply:
<pre>(apply + [1 2 3])</pre>
</li>
<li>It&#8217;s possible implement this in such a way as to append, rather than prepend, results.  This approach means that reverse isn&#8217;t necessary, but might be slower and/or more complicated depending on the implementation of the collection.</li>
</ol>
						</div>
						
						<div class="info">							
							
							<p><a href="http://alan.dipert.org/post/307586762/polyglot-folding-ruby-clojure-scala">Permalink</a> <span class="notes">2 notes</span> <span style="float: right;"><a class="dsq-comment-count" href="http://alan.dipert.org/post/307586762/polyglot-folding-ruby-clojure-scala#disqus_thread"></a></span></p>
						</div>
					</div>
					

					
					
					
					
					

					
					
					
					
					
					

		
		
		
		
		
					

					
					
					
					

					
					
					
					
					

					
					
					
					
					
					

					
					
					
					
					


            
                
                    <div class="notecontainer">
                        <div id="disqus_thread"></div>
                        <script type="text/javascript" src="http://disqus.com/forums/alandipert/embed.js"></script>
                        <noscript><a href="http://alandipert.disqus.com/?url=ref">View the discussion thread</a></noscript>
                    </div>
                
            
			
						
			
			
			

			
			
			


			
			
			
			
			
			<div id="pagination" role="navigation">
				<p>																										
					
					<a href="http://alan.dipert.org/post/332027463" class="newer">Next post &raquo;</a>
					
					
					
					<a href="http://alan.dipert.org/post/172774481" class="older">&laquo; Previous post</a>
					
				</p>
			</div>
			
		</div>				
	</div>

	
	<div id="footer">
		<div class="wrapper">
			<ul class="links" role="navigation">
				<li><a href="/archive">Archive</a></li>
				
				<li><a href="http://alan.dipert.org/rss">RSS</a></li>
			</ul>
			<p class="info-theme" role="contentinfo">Powered by <a href="http://www.tumblr.com">Tumblr</a> and designed by <a href="http://kcmr.tumblr.com">Kcmr</a>.</p>
		</div>
	</div>

    
        <script type="text/javascript">
            //<![CDATA[
            (function() {
                var links = document.getElementsByTagName('a');
                var query = '?';
                for(var i = 0; i < links.length; i++) {
                    if(links[i].href.indexOf('#disqus_thread') >= 0) {
                        query += 'url' + i + '=' + encodeURIComponent(links[i].href) + '&';
                    }
                }
                document.write('<script charset="utf-8" type="text/javascript" src="http://disqus.com/forums/alandipert/get_num_replies.js' + query + '"></' + 'script>');
            })();
            //]]>
        </script>
    
<!-- BEGIN TUMBLR CODE -->
        
    
        <iframe scrolling="no" frameborder="0" id="tumblr_controls" src="http://assets.tumblr.com/assets/html/iframe.html?_v=55aa5b1908226d4608b734ece2c8028c&amp;src=http%3A%2F%2Falan.dipert.org%2Fpost%2F307586762%2Fpolyglot-folding-ruby-clojure-scala&amp;pid=307586762&amp;rk=xyMl54R8&amp;lang=en_US&amp;name=alandipert&amp;brag=false&amp;avatar=http%3A%2F%2F25.media.tumblr.com%2Favatar_4ae064934cfd_64.png&amp;title=alan+dipert&amp;url=http%3A%2F%2Falan.dipert.org%2F" width="330" height="25" style="position:absolute; z-index:2147483647; top:0; right:0; border:0; background-color:transparent; overflow:hidden; "></iframe>    
        
    <!--[if IE]><script type="text/javascript">document.getElementById('tumblr_controls').allowTransparency=true;</script><![endif]-->
    
    <script type="text/javascript">var s=new Image(1,1);s.src=((r='http://www.tumblr.com/impixu?T=1369685037&J=eyJ0eXBlIjoiYmxvZyIsImJsb2dpZCI6IjQzOTQ2OCIsInVybCI6Imh0dHA6XC9cL2FsYW4uZGlwZXJ0Lm9yZ1wvcG9zdFwvMzA3NTg2NzYyXC9wb2x5Z2xvdC1mb2xkaW5nLXJ1YnktY2xvanVyZS1zY2FsYSIsInJlcXR5cGUiOjB9&U=KOICBGCLJN&K=938a97dfbe3add002241a39521f61d65266e057f9fb92f860bf7e4823e430923&R='.replace(/&R=[^&$]*/,'')) + ('&R='+escape(document.referrer)).substr(0, 2000-r.length).replace(/%.?.?$/,''));</script><noscript><img style="position:absolute;z-index:-3334;top:0px;left:0px;visibility:hidden;" src="http://www.tumblr.com/impixu?T=1369685037&J=eyJ0eXBlIjoiYmxvZyIsImJsb2dpZCI6IjQzOTQ2OCIsInVybCI6Imh0dHA6XC9cL2FsYW4uZGlwZXJ0Lm9yZ1wvcG9zdFwvMzA3NTg2NzYyXC9wb2x5Z2xvdC1mb2xkaW5nLXJ1YnktY2xvanVyZS1zY2FsYSIsInJlcXR5cGUiOjAsIm5vc2NyaXB0IjoxfQ==&U=KOICBGCLJN&K=ea3f34451d19b061208db0459c0410dcb5e1fd8506ab9bc3aee69f148576c74f&R="></noscript>    <!-- END TUMBLR CODE -->

<iframe src="http://assets.tumblr.com/analytics.html?4344dcb6da7e8742c4c5ab1d76ffafae" scrolling="no" width="1" height="1" frameborder="0" style="background-color:transparent; overflow:hidden; position:absolute; top:0; left:0 z-index:9999;" id="ga_target"></iframe>

    <script>
        var COMSCORE = true;
        window.setTimeout(function() {
            var analytics_frame = document.getElementById('ga_target');
            analytics_frame.contentWindow.postMessage('enable_comscore;' + window.location, analytics_frame.src.split('/analytics.html')[0]);
        }, 1000);
    </script>



    <script type="text/javascript">
      var _qevents = _qevents || [];

      (function() {
       var elem = document.createElement('script');

       elem.src = (document.location.protocol == "https:" ? "https://secure" : "http://edge") + ".quantserve.com/quant.js";
       elem.async = true;
       elem.type = "text/javascript";
       var scpt = document.getElementsByTagName('script')[0];
       scpt.parentNode.insertBefore(elem, scpt);
      })();
    </script>
    <script type="text/javascript">
        _qevents.push( { qacct: 'p-19UtqE8ngoZbM' } );
    </script>
    <noscript>
        <div style="display: none;"><img src="//pixel.quantserve.com/pixel/'p-19UtqE8ngoZbM'.gif" height="1" width="1" alt="Quantcast"/></div>
    </noscript>


    <script type="text/javascript">var s=new Image(1,1);s.src=((r='http://www.tumblr.com/impixu?T=1369685037&J=eyJ0eXBlIjoidXJsIiwidXJsIjoiaHR0cDpcL1wvYWxhbi5kaXBlcnQub3JnXC9wb3N0XC8zMDc1ODY3NjJcL3BvbHlnbG90LWZvbGRpbmctcnVieS1jbG9qdXJlLXNjYWxhIiwicmVxdHlwZSI6MH0=&U=JNBKCIBMNE&K=f37c39ccc173f468ee28135548181925ff28a3315796530193f0f9ad0288e76e&R='.replace(/&R=[^&$]*/,'')) + ('&R='+escape(document.referrer)).substr(0, 2000-r.length).replace(/%.?.?$/,''));</script><noscript><img style="position:absolute;z-index:-3334;top:0px;left:0px;visibility:hidden;" src="http://www.tumblr.com/impixu?T=1369685037&J=eyJ0eXBlIjoidXJsIiwidXJsIjoiaHR0cDpcL1wvYWxhbi5kaXBlcnQub3JnXC9wb3N0XC8zMDc1ODY3NjJcL3BvbHlnbG90LWZvbGRpbmctcnVieS1jbG9qdXJlLXNjYWxhIiwicmVxdHlwZSI6MCwibm9zY3JpcHQiOjF9&U=JNBKCIBMNE&K=e1b2db6e9b3d92a61fb81044eee4208dba7fd833f43ab3250b5e7af2d58317fe&R="></noscript><script type="text/javascript">var s=new Image(1,1);s.src=((r='http://www.tumblr.com/impixu?T=1369685037&J=eyJ0eXBlIjoicG9zdCIsInVybCI6Imh0dHA6XC9cL2FsYW4uZGlwZXJ0Lm9yZ1wvcG9zdFwvMzA3NTg2NzYyXC9wb2x5Z2xvdC1mb2xkaW5nLXJ1YnktY2xvanVyZS1zY2FsYSIsInJlcXR5cGUiOjAsInBvc3RzIjpbeyJwb3N0aWQiOiIzMDc1ODY3NjIiLCJibG9naWQiOiI0Mzk0NjgiLCJzb3VyY2UiOjMzfV19&U=COGFBMPOEJ&K=ecd178b5bc97af2b44ce4240d3932255d1589edf41154e0a4f00cef21abfe702&R='.replace(/&R=[^&$]*/,'')) + ('&R='+escape(document.referrer)).substr(0, 2000-r.length).replace(/%.?.?$/,''));</script><noscript><img style="position:absolute;z-index:-3334;top:0px;left:0px;visibility:hidden;" src="http://www.tumblr.com/impixu?T=1369685037&J=eyJ0eXBlIjoicG9zdCIsInVybCI6Imh0dHA6XC9cL2FsYW4uZGlwZXJ0Lm9yZ1wvcG9zdFwvMzA3NTg2NzYyXC9wb2x5Z2xvdC1mb2xkaW5nLXJ1YnktY2xvanVyZS1zY2FsYSIsInJlcXR5cGUiOjAsInBvc3RzIjpbeyJwb3N0aWQiOiIzMDc1ODY3NjIiLCJibG9naWQiOiI0Mzk0NjgiLCJzb3VyY2UiOjMzfV0sIm5vc2NyaXB0IjoxfQ==&U=COGFBMPOEJ&K=2ce4ca19f7d0ab14881d4702b43ec4459faa38e04a0836bc7467c5d6597ea7a1&R="></noscript></body>
</html>