title: Haskell self-referential List termination
body: <p><strong><em>EDIT:</strong> see <strong><a href="https://stackoverflow.com/questions/46478088/haskell-handling-deadlocked-self-referential-lists">this followup question</a></strong> that simplifies the problem I am trying to identify here, and asks for input on a GHC modification proposal.</em></p>
  
  <p>So I was trying to write a generic breadth-first search function and came up with the following:</p>
  
  <pre><code>bfs :: (a -&gt; Bool) -&gt; (a -&gt; [a]) -&gt; [a] -&gt; Maybe a
  bfs predf expandf xs = find predf bfsList
      where bfsList = xs ++ concatMap expandf bfsList
  </code></pre>
  
  <p>which I thought was pretty elegant, however in the does-not-exist case it blocks forever. </p>
  
  <p>After all the terms have been expanded to <code>[]</code>, <code>concatMap</code> will never return another item, so <code>concatMap</code> is blocking waiting for another item from itself? Could Haskell be made smart enough to realize the list generation is blocked reading the self-reference and terminate the list?</p>
  
  <p>The best replacement I've been able to come up with isn't quite as elegant, since I have to handle the termination case myself:</p>
  
  <pre><code>    where bfsList = concat.takeWhile (not.null) $ iterate (concatMap expandf) xs
  </code></pre>
  
  <p>For concrete examples, the first search terminates with success, and the second one blocks:</p>
  
  <pre><code>bfs (==3) (\x -&gt; if x&lt;1 then [] else [x/2, x/5]) [5, 3*2**8]
  bfs (==3) (\x -&gt; if x&lt;1 then [] else [x/2, x/5]) [5, 2**8]
  </code></pre>