title: Efficient lazy ByteString generation, using random ByteString as an example
body: <p>There seems to be some impediment to efficient lazy <code>ByteString</code> generation by recursion. To demonstrate this, the chosen task is to make a lazy random <code>ByteString</code>. (Random number generation is just a reasonably meaningful operation, i.e. a placeholder for any other recursion that might be of interest.)</p>
  
  <p>Here are two attempts to create a random lazy <code>ByteString</code> of fixed length <code>n</code>. They allocate huge amounts of heap. First some imports:</p>
  
  <pre><code>import qualified Data.ByteString.Lazy as BSL
  import Data.Word8
  import System.Random
  </code></pre>
  
  <p>Now the function that uses <a href="http://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString-Lazy.html#v:cons" rel="nofollow noreferrer"><code>cons</code></a>:</p>
  
  <pre><code>lazyRandomByteString1 :: Int -&gt; StdGen -&gt; BSL.ByteString
  lazyRandomByteString1 n g = fst3 $ iter (BSL.empty, n, g) where
      fst3 (a, _, _) = a
      iter (bs', n', g') =
          if n' == 0 then (bs', 0, g')
          else iter (w `BSL.cons` bs', n'-1, g'') where
              (w, g'') = random g' :: (Word8, StdGen)
  </code></pre>
  
  <p>The same, just using <a href="http://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString-Lazy.html#v:unfoldr" rel="nofollow noreferrer"><code>unfoldr</code></a> is shorter, but almost as bad as the above:</p>
  
  <pre><code>lazyRandomByteString2 :: Int -&gt; StdGen -&gt; BSL.ByteString
  lazyRandomByteString2 n g = BSL.unfoldr f (n, g) where
      f :: (Int, StdGen) -&gt; (Int, StdGen)
      f (n', g') =
          if n' == 0 then Nothing
          else Just (w, (n'-1, g'')) where
              (w, g'') = random g' :: (Word8, StdGen)
  </code></pre>
  
  <p>Within what's provided by <a href="http://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString-Lazy.html#v:cons" rel="nofollow noreferrer"><code>Data.ByteString.Lazy</code></a> these are all the available options to create <code>ByteStrings</code> by recursion.</p>
  
  <p>Next, turn to <a href="https://hackage.haskell.org/package/bytestring-0.10.0.2/docs/Data-ByteString-Lazy-Builder.html#t:Builder" rel="nofollow noreferrer"><code>Data.ByteString.Lazy.Builder</code></a>, it was built to build lazy <code>ByteStrings</code>, surely this must be more efficient:</p>
  
  <pre><code>import Data.ByteString.Lazy.Builder (Builder, toLazyByteString, word8)
  
  lazyRandomByteString3 :: Int -&gt; StdGen -&gt; BSL.ByteString
  lazyRandomByteString3 n g = toLazyByteString builder where
      builder :: Builder
      builder = fst3 $ iter (mempty, n, g) where
          fst3 (a, _, _) = a
          iter :: (Builder, Int, StdGen) -&gt; (Builder, Int, StdGen)
          iter (b, n', g') =
              if n' == 0 then (b, 0, g')
              else iter (b &lt;&gt; (word8 w), n'-1, g'') where
                  (w, g'') = random g' :: (Word8, StdGen)
  </code></pre>
  
  <p>But it isn't.</p>
  
  <p><code>Builder</code> really should be able to do this efficiently, shouldn't it? What is wrong with <code>lazyRandomByteString3</code>?</p>
  
  <p>The source code is on <a href="https://github.com/mcmayer/lazy-random-bytestring" rel="nofollow noreferrer">github</a>.</p>