title: Explanation of combinators for the working man
body: <p><strong>What is a combinator??</strong>  </p>
  
  <p>Is it <strong>"a function or definition with no free variables"</strong> (as defined on SO)?</p>
  
  <p>Or how about this:  according to <a href="http://www.ittc-ku.net/Projects/SLDG/filing_cabinet/Hughes_Generalizing_Monads_to_Arrows.pdf">John Hughes</a> in his well-known paper on Arrows, <strong>"a combinator is a function which builds program fragments from program fragments"</strong>, which is advantageous because "... the programmer using combinators constructs much of the desired program automatically, rather than writing every detail by hand".  He goes on to say that <code>map</code> and <code>filter</code> are two common examples of such combinators.</p>
  
  <p>Some combinators which match the first definition:</p>
  
  <ul>
  <li>S</li>
  <li>K</li>
  <li>Y</li>
  <li>others from <a href="http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird">To Mock a Mockingbird</a> (I may be wrong -- I haven't read this book)</li>
  </ul>
  
  <p>Some combinators which match the second definition:</p>
  
  <ul>
  <li>map</li>
  <li>filter</li>
  <li>fold/reduce (presumably)</li>
  <li>any of >>=, compose, fmap ?????</li>
  </ul>
  
  <p>I'm not interested in the first definition -- those would not help me to write a real program (+1 if you convince me I'm wrong).  <strong>Please help me understand the second definition</strong>.  I think map, filter, and reduce are useful: they allow me to program at a higher level -- fewer mistakes, shorter and clearer code.  Here are some of my specific questions about combinators:</p>
  
  <ol>
  <li>What are more examples of combinators such as map, filter?</li>
  <li>What combinators do programming languages often implement?  </li>
  <li>How can combinators help me design a better API? </li>
  <li>How do I design effective combinators?</li>
  <li>What are combinators similar to in a non-functional language (say, Java), or what do these languages use in place of combinators?</li>
  </ol>
  
  <hr>
  
  <p><strong>Update</strong>  </p>
  
  <p>Thanks to @C. A. McCann, I now have a somewhat better understanding of combinators.  But one question is still a sticking point for me:</p>
  
  <p><strong>What is the difference between a functional program written with, and one written without, heavy use of combinators?</strong></p>
  
  <p>I suspect the answer is that the combinator-heavy version is shorter, clearer, more general, but I would appreciate a more in-depth discussion, if possible.</p>
  
  <p>I'm also looking for more examples and explanations of complex combinators (i.e. more complex than <code>fold</code>) in common programming languages.</p>