mapM on IO produces infinite output

Question

This is a bizzare behavior, even for Haskell. Look at the code segments below:

import System.Directory
import System.FilePath

-- This spins infinitely
loadCtx :: FilePath -> IO ()
loadCtx dir = do
    lsfiles <- listDirectory dir
    let files = mapM (dir </>) lsfiles
    putStrLn $ "Files " ++ show files

-- This does what I'd expect, prepending the dir path to each file
loadCtx dir = do
    lsfiles <- listDirectory dir
    let files = map (dir </>) lsfiles
    putStrLn $ "Files " ++ show files

Both definitions are accepted from the typechecker but give completely different behavior. What is the output of the first mapM? It looks like an infinite loop on reading some files. Also is it possible to compose the listDirectory do-arrow line with the map (dir </>) that prepends the path, in one-line?

Answer 1

What is the output of the first mapM? It looks like an infinite loop on reading some files.

It is not an infinite loop -- merely a very, very long one.

You are not using mapM for IO; you are using mapM in the nondeterminism monad. Here is the type of mapM, specialized to that monad:

Traversable t => (a -> [b]) -> t a -> [t b]

Read this in the following way:

• First, give me a way to turn an element of a container (type a) into a nondeterministic choice between many possible replacement elements (type [b]).
• Then give me a containerful of elements (type t a).
• I will give you a nondeterministic choice between containers with replacement elements in them (type [t b]). (And, this part is not in the type, but: the way I will do this is by taking all possible combinations; for each position in the container, I'll try each possible b, and give you every which way of making one choice for each position in the container.)

For example, if we were to define the function f :: Int -> [Char] for which f n chose nondeterministically between the first n letters of the alphabet, then we could see this kind of interaction:

> f 3
"abc"
> f 5
"abcde"
> f 2
"ab"
> mapM f [3,5,2]
["aaa","aab","aba","abb","aca","acb","ada","adb","aea","aeb","baa","bab","bba","bbb","bca","bcb","bda","bdb","bea","beb","caa","cab","cba","cbb","cca","ccb","cda","cdb","cea","ceb"]

In each result, the first letter is one of the first three in the alphabet (a, b, or c); the second is from the first five, and the third from the first two. What's more, we get every list which has this property.

Now let's think about what that means for your code. You have written

mapM (dir </>) lsfiles

and so what you will get back is a collection of lists. Each list in the collection will be exactly as long as lsfiles is. Let's focus on one of the lists in the collection; call it cs.

The first element of cs will be drawn from dir </> filename, where filename is the first element of lsfiles; that is, it will be one of the characters in dir, or a slash, or one of the characters in filename. The second element of cs will be similar: one of the characters of dir, or a slash, or one of the characters from the second filename in lsfiles. I guess you can see where this is going... there's an awful lot of possibilities here. =)

Also is it possible to compose the listDirectory do-arrow line with the map (dir </>) that prepends the path, in one-line?

Yes:

loadCtx dir = do
    files <- map (dir </>) <$> listDirectory dir
    putStrLn $ "Files " ++ show files

Answer 2

To complement Jorge's answer, here's an exponential blowup, demonstrated:

> map ("XY" </>) ["a","b","c"]
["XY\\a","XY\\b","XY\\c"]
> mapM ("XY" </>) ["a","b","c"]
["XXX","XXY","XX\\","XXc","XYX","XYY","XY\\","XYc","X\\X","X\\Y","X\\\\",
 "X\\c","XbX","XbY","Xb\\","Xbc","YXX","YXY","YX\\","YXc","YYX","YYY","YY\\","YYc",
 "Y\\X","Y\\Y","Y\\\\","Y\\c","YbX","YbY","Yb\\","Ybc","\\XX","\\XY","\\X\\",
 "\\Xc","\\YX","\\YY","\\Y\\","\\Yc","\\\\X","\\\\Y","\\\\\\","\\\\c","\\bX",
 "\\bY","\\b\\","\\bc","aXX","aXY","aX\\","aXc","aYX","aYY","aY\\","aYc","a\\X",
 "a\\Y","a\\\\","a\\c","abX","abY","ab\\","abc"]

Indeed, mapM = sequence . map, and sequence in the list monad performs the cartesian product of a list-of-lists, ["XY\\a","XY\\b","XY\\c"] in this case, so we get 4*4*4 combinations. (Ouch!)

Answer 3

Well according to the documentation,

type FilePath = String 

That is,

type FilePath = [Char]

So in this line,

let files = mapM (dir </>) lsfiles

you have that the argument of mapM, which is (dir </>), is of type FilePath -> FilePath. Now look at the type of mapM,

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
                                         ^^^^^

So the type a -> m b is instantiated to FilePath -> FilePath, which is FilePath -> [Char]. So you're performing a monadic mapping using the list monad, which is the "nondeterminism" monad in this case for values of type Char.