title: When to use foldr with a continuation as an accumulation function?
body: <p>There is a technique I've seen a few times with <code>foldr</code>.  It involves using a function in place of the accumulator in a <code>foldr</code>.  I'm wondering when it is necessary to do this, as opposed to using an accumulator that is just a regular value.</p>
  
  <p>Most people have seen this technique before when using <code>foldr</code> to define <code>foldl</code>:</p>
  
  <pre><code>myFoldl :: forall a b. (b -&gt; a -&gt; b) -&gt; b -&gt; [a] -&gt; b
  myFoldl accum nil as = foldr f id as nil
    where
      f :: a -&gt; (b -&gt; b) -&gt; b -&gt; b
      f a continuation b = continuation $ accum b a
  </code></pre>
  
  <p>Here, the type of the combining function <code>f</code> is not just <code>a -&gt; b -&gt; b</code> like normal, but <code>a -&gt; (b -&gt; b) -&gt; b -&gt; b</code>.  It takes not only an <code>a</code> and <code>b</code>, but a continuation (<code>b -&gt; b</code>) that we need to pass the <code>b</code> to in order to get the final <code>b</code>.</p>
  
  <p>I most recently saw an example of using this trick in the book <a href="https://simonmar.github.io/pages/pcph.html" rel="nofollow noreferrer">Parallel and Concurrent Programming in Haskell</a>.  <a href="https://github.com/simonmar/parconc-examples/blob/3fca38f01f71639cc780473026fdaac679cc230c/findpar.hs#L21-L23" rel="nofollow noreferrer">Here</a> is a link to the source code of the example using this trick.  <a href="https://web.archive.org/web/20171114090047/http://chimera.labs.oreilly.com:80/books/1230000000929/ch13.html#conc-par_00000029" rel="nofollow noreferrer">Here</a> is a link to the chapter of the book explaining this example.</p>
  
  <p>I've taken the liberty of simplifying the source code into a similar (but shorter) example.  Below is a function that takes a list of Strings, prints out whether each string's length is greater than five, then prints the full list of only the Strings that have a length greater than five:</p>
  
  <pre><code>import Text.Printf
  
  stringsOver5 :: [String] -&gt; IO ()
  stringsOver5 strings = foldr f (print . reverse) strings []
    where
      f :: String -&gt; ([String] -&gt; IO ()) -&gt; [String] -&gt; IO ()
      f str continuation strs = do
        let isGreaterThan5 = length str &gt; 5
        printf "Working on \"%s\", greater than 5? %s\n" str (show isGreaterThan5)
        if isGreaterThan5
          then continuation $ str : strs
          else continuation strs
  </code></pre>
  
  <p>Here's an example of using it from GHCi:</p>
  
  <pre><code>&gt; stringsOver5 ["subdirectory", "bye", "cat", "function"]
  Working on "subdirectory", greater than 5? True
  Working on "bye", greater than 5? False
  Working on "cat", greater than 5? False
  Working on "function", greater than 5? True
  ["subdirectory","function"]
  </code></pre>
  
  <p>Just like in the <code>myFoldl</code> example, you can see that the combining function <code>f</code> is using the same trick.</p>
  
  <p>However, it occurred to me that this <code>stringsOver5</code> function could probably be written without this trick:</p>
  
  <pre><code>stringsOver5PlainFoldr :: [String] -&gt; IO ()
  stringsOver5PlainFoldr strings = foldr f (pure []) strings &gt;&gt;= print
    where
      f :: String -&gt; IO [String] -&gt; IO [String]
      f str ioStrs = do
        let isGreaterThan5 = length str &gt; 5
        printf "Working on \"%s\", greater than 5? %s\n" str (show isGreaterThan5)
        if isGreaterThan5
          then fmap (str :) ioStrs
          else ioStrs
  </code></pre>
  
  <p>(Although maybe you could make the argument that <code>IO [String]</code> <a href="http://hackage.haskell.org/package/ghc-prim-0.5.2.0/docs/GHC-Types.html#t:IO" rel="nofollow noreferrer">is a continuation</a>?)</p>
  
  <hr>
  
  <p>I have two questions regarding this:</p>
  
  <ul>
  <li>Is it every absolutely necessary to use this trick of passing a continuation to <code>foldr</code>, instead of using <code>foldr</code> with a normal value as an accumulator?  Is there an example of a function that absolutely <em>can't</em> be written using <code>foldr</code> with a normal value?  (Aside from <code>foldl</code> and functions like that, of course.)</li>
  <li>When would I want to use this trick in my own code?  Is there any example of a function that can be significantly simplified by using this trick?</li>
  <li>Is there any sort of performance considerations to take into account when using this trick? (Or, well, when <em>not</em> using this trick?)</li>
  </ul>