How to convert function returning [] to Traversable?

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?

Solution

Polymorphic production of lists, and designing classes for polymorphic containers in general, has proven to be more difficult than it might first appear. GHC's current solution for producing fully polymorphic containers, vs just operating over a pre-existing container such as with Traversable, is the IsList class.

Defined in GHC.Exts as:

class IsList l where
  type Item l
  fromList  :: [Item l] -> l
  ...

There are already instances for lists, non empty lists, maps, and most other types coming from what you'd think of as standard Haskell libraries.

Notice the type parameter, l, is of kind * and not what you might expect from a container of * -> *. You provide the fully applied type and can constrain the Item l type with type equality if desired. For example:

{-# LANGUAGE TypeFamilies #-}
module Walk
  ( walk
  ) where

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

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