How to convert function returning [] to Traversable?

Question

I have the following module which implements a directory walk:

module Walk
  ( walk
  ) where

import           Control.Monad
import           Control.Monad.IO.Class
import           Data.List
import           System.Directory
import           System.FilePath

walk :: (MonadIO m) => FilePath -> m [(FilePath, [FilePath])]
walk root = do
  entries <- liftIO $ listDirectory root
  (files, dirs) <- partition snd <$> liftM2 (<$>) zip (mapM (liftIO . doesFileExist . (root </>))) entries
  ((root, map fst files) :) . concat <$> mapM (walk . (root </>) . fst) dirs

It currently returns a list, but I'd like it to return a Traversable instead:

walk :: (MonadIO m, Traversable t) => FilePath -> m (t (FilePath, [FilePath]))

If I change the signature, I get the following error:

    • Couldn't match type ‘t’ with ‘[]’
      ‘t’ is a rigid type variable bound by
        the type signature for:
          walk :: forall (m :: * -> *) (t :: * -> *).
                  (MonadIO m, Traversable t) =>
                  FilePath -> m (t (FilePath, [FilePath]))
      Expected type: m (t (FilePath, [FilePath]))
        Actual type: m [(FilePath, [FilePath])]
    • In a stmt of a 'do' block:
        ((root, map fst files) :) . concat
          <$> mapM (walk . (root </>) . fst) dirs
      In the expression:
        do entries <- liftIO $ listDirectory root
           (files, dirs) <- partition snd
                              <$>
                                liftM2
                                  (<$>) zip (mapM (liftIO . doesFileExist .
(root </>))) entries
           ((root, map fst files) :) . concat
             <$> mapM (walk . (root </>) . fst) dirs
      In an equation for ‘walk’:
          walk root
            = do entries <- liftIO $ listDirectory root
                 (files, dirs) <- partition snd
                                    <$>
                                      liftM2
                                        (<$>)
                                        zip
                                        (mapM (liftIO . doesFileExist .
(root </>)))
                                        entries
                 ((root, map fst files) :) . concat
                   <$> mapM (walk . (root </>) . fst) dirs
    • Relevant bindings include
        walk :: FilePath -> m (t (FilePath, [FilePath]))

I think it's failing on the :? I can't be sure. How do I fix this?

Answer 1

I think it's failing on the :?

Indeed it is. If you use (:) to build the structure, the structure will be a list, and you can't change the type of walk to claim it returns an arbitrary traversable structure. There isn't really a good Traversable-centric workaround, either: Traversable means you have, via its Foldable superclass, a toList, but not a fromList.