haskellfunctional-programminglanguage-lawyerproofio-monad

Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?


This was actually something I wanted to understand with my previous question, but I misworded it by giving for granted the solution would somehow have to build on sequence and repeat, so I got an intersting answer, which is definitely useful to solve the problem at hand, but I didn't actually solve my curiosity as well, so I'm rephrasing the quesition as in the title.

As you can see from the linked question, I initially wrote

main :: IO ()
main = do
  x <- takeWhile (/= 'q') <$> sequence (repeat getChar)
  print "you pressed q"

thinking x would be a finite-length [Char].

But I'm now under the impression that I've not "just" used the wrong tool above (takeWhile, a pure function), but that there's actually no (orthodox) tool at all to bail out of that IO [Char] that is sequence (repeat getChar).

Am I correct?

If not, then how do you bail out of that?

Beware, I'm not asking now the same question as before. I'm looking for a solution that does make use of sequence (repeat getChar) and still manages to get to the print "you pressed q" action, or the explanatin of why such a solution doesn't exist.


Solution

  • If you sequence an infinite list of IO operations, you can't bail out via "pure" program logic. So, you are correct that there is no "orthodox" tool to bail out of sequence (repeat getChar).

    The only way to bail out is to invoke an IO effect to do "impure" bailing, for example by raising an exception, killing the thread, exiting the program, or similar. In these cases, you can't easily return a value, so this wouldn't be very useful for your use case. Alternatively, instead of bailing out, you can "cheat" and use unsafe lazy I/O, which allows you to execute an initial prefix of the infinite list of actions and inspect the initial prefix of the returned list. You can either continue processing the list indefinitely or "abandon" the list after processing some finite number of elements.

    In general, though, either of these approaches are going to be bad practice, at least for your problem.

    If you want to write a proper monadic action that reads characters until the first 'q', then the right way to do it with elementary Haskell code is something like this:

    getToQ :: IO String
    getToQ = do
      c <- getChar
      if c == 'q' then pure [] else do
        cs <- getToQ
        pure (c:cs)
    

    The technical reason you can't use sequence to implement this logic is that this is a fundamentally monadic algorithm but sequence is "only" an applicative combinator. Applicative combinators can't use the results of applicative actions to influence the "structure" of the computation. When you sequence an infinite list of IO actions, you have committed to executing an infinite loop, and the results of the actions cannot change this into a finite loop, except as a side effect (exception, etc.). In particular sequence can't implement the part of getToQ where we inspect the return value c and decide whether the rest of the computation is going to be pure [] or a recursive call to getToQ to do more getChars. You can see this from the following (simplified) definition of sequence:

    sequence [] = pure []
    sequence (x:xs) = do
      a <- x
      as <- sequence xs
      pure (a:as)
    

    See how the returned a value from the x action cannot be used to influence whether or not the sequence xs action in the next line executes? That's how sequence differs structurally from getToQ.

    Now, there are some packages, like extra and monad-loops that provide monadic combinators that can be used to succinctly write the equivalent of getToQ. For example, from monad-loops, the unfoldWhileM will do exactly what you want:

    unfoldWhileM (/= 'q') getChar
    

    There's nothing magical about these combinators. A simplified implementation of this combinator would be:

    unfoldWhileM :: Monad m => (a -> Bool) -> m a -> m [a]
    unfoldWhileM p x = do
      a <- x
      if p a then do
          as <- unfoldWhileM p x
          pure (a:as)
        else pure []
    

    See how this combinator, in contrast to sequence, is fundamental a non-applicative, monadic combinator. It uses the return value a from the action x to determine the structure of the rest of the computation: (i) recurse to execute more x actions; or (ii) end the computation.