foldl and IO values

Question

I have such code:

foldl (\a x -> a ++ (f x)) [] list

All seems to be ok, but (f x) :: IO [String], and (++) gives an error ([String] != IO [String]).

How to define empty IO[String] list? I can't make clean (f x).

Answer 1

The combinator you want here is probably

Prelude Control.Monad> :t foldM
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a

and with that

foldM (\a x -> fmap (a++) (f x)) [] list

to run the actions f x in sequence and accumulate the [String]s they produce.

Answer 2

In:

foldl (\a x -> a ++ (f x)) [] list

you're trying to do a ++ f x but f x :: IO [String], so it's not working. Let's see if we can work out what's going on.

You mean for x to come from your list, so you'll be applying f in turn to each of the elements of the list, and they each give you a [String] and you want to concatenate them together as you go along.

We'll use mapM :: Monad m => (a -> m b) -> [a] -> m [b], which maps a function over a list then sequences the monad operations together into one, combining the outputs into a list.

concatMapM :: (a -> IO [String]) -> [a] -> IO [String]
concatMapM f list = fmap concat (mapM f list)

Here I've used fmap to apply the pure function concat to the result of the IO operation.

You could test it out using

fileLines :: FilePath -> IO [String]
fileLines filename = fmap lines (readFile filename)

*Main> concatMapM fileLines ["test1.txt","test2.txt"]
["This is test1.txt","It has two lines.","This is test2.txt","It has two lines too."]

This way is better than trying to foldl, because concat works more efficiently than foldl (++). To check this out for yourself, compare these for speed:

*Main> writeFile "test3.txt" $ foldl (++) [] (map show [1..10000])
*Main> writeFile "test3.txt" $ foldr (++) [] (map show [1..10000])

The trouble is that foldl does (((a++b)++c)++d)++e so runs through the list a four times - it runs through it first as it adds b, then it runs through a and b as it adds c, then it runs through a, b and c as it adds d, then runs through all four of them as it adds e. This is a big waste of effort.

foldr does a ++ (b ++ (c ++ (d ++ e))) so runs through each list once - d then c then b then a. concat is a foldr, which is much better for this list operation.