Add Traversable instance for ListT

[treeowl]

I don't have a good enough sense of how this stuff all fits together to come up with a nice, direct definition. This, however, passes the type checker and seems to make some sort of sense. So it can probably be transformed into something nice.

instance (Monad m, Foldable m) => Traversable (ListT m) where
  traverse f xs = Select . each <$> traverse f (F.toList xs)

OTOH, it may be that there's no way to make it terribly efficient, in which case this simple definition will do.

[treeowl]

In case you're reading by email, I weakened the constraint some. Not that there are terribly many foldable monads that aren't traversable.

[Gabriella439]

So I think there should be some sort of elegant solution for this, given that GHC can derive Traversable for the following ListT:

{-# LANGUAGE DeriveFoldable    #-}
{-# LANGUAGE DeriveFunctor     #-}
{-# LANGUAGE DeriveTraversable #-}

module Test where

import Data.Foldable
import Data.Traversable

data ListT m a = ListT { next :: m (Step m a) }
    deriving (Functor, Foldable, Traversable)

data Step m a = Cons a (ListT m a) | Nil
    deriving (Functor, Foldable, Traversable)

If I dump the derived Traversable instance, I get this:

$ ghc -ddump-deriv Test.hs
==================== Derived instances ====================
Derived instances:
  instance GHC.Base.Functor m_aiG =>
           GHC.Base.Functor (Test.Step m_aiG) where
    GHC.Base.fmap f_apE (Test.Cons a1_apF a2_apG)
      = Test.Cons
          (f_apE a1_apF) (GHC.Base.fmap (\ b1_apH -> f_apE b1_apH) a2_apG)
    GHC.Base.fmap f_apI Test.Nil = Test.Nil

  instance Data.Foldable.Foldable m_aiG =>
           Data.Foldable.Foldable (Test.Step m_aiG) where
    Data.Foldable.foldr f_apJ z_apK (Test.Cons a1_apL a2_apM)
      = f_apJ
          a1_apL
          (Data.Foldable.foldr
             (\ b1_apN b2_apO -> f_apJ b1_apN b2_apO) z_apK a2_apM)
    Data.Foldable.foldr f_apP z_apQ Test.Nil = z_apQ

  instance Data.Traversable.Traversable m_aiG =>
           Data.Traversable.Traversable (Test.Step m_aiG) where
    Data.Traversable.traverse f_apR (Test.Cons a1_apS a2_apT)
      = (Control.Applicative.<*>)
          (GHC.Base.fmap Test.Cons (f_apR a1_apS))
          (Data.Traversable.traverse (\ b1_apU -> f_apR b1_apU) a2_apT)
    Data.Traversable.traverse f_apV Test.Nil
      = Control.Applicative.pure Test.Nil

  instance GHC.Base.Functor m_aiI =>
           GHC.Base.Functor (Test.ListT m_aiI) where
    GHC.Base.fmap f_apW (Test.ListT a1_apX)
      = Test.ListT
          (GHC.Base.fmap
             (\ b1_apY -> GHC.Base.fmap (\ b2_apZ -> f_apW b2_apZ) b1_apY)
             a1_apX)

  instance Data.Foldable.Foldable m_aiI =>
           Data.Foldable.Foldable (Test.ListT m_aiI) where
    Data.Foldable.foldr f_aq0 z_aq1 (Test.ListT a1_aq2)
      = Data.Foldable.foldr
          (\ b1_aq3 b2_aq4
             -> Data.Foldable.foldr
                  (\ b3_aq5 b4_aq6 -> f_aq0 b3_aq5 b4_aq6) b2_aq4 b1_aq3)
          z_aq1
          a1_aq2

  instance Data.Traversable.Traversable m_aiI =>
           Data.Traversable.Traversable (Test.ListT m_aiI) where
    Data.Traversable.traverse f_aq7 (Test.ListT a1_aq8)
      = GHC.Base.fmap
          Test.ListT
          (Data.Traversable.traverse
             (\ b1_aq9
                -> Data.Traversable.traverse (\ b2_aqa -> f_aq7 b2_aqa) b1_aq9)
             a1_aq8)

So now I'm just working backwards from that to see how it should be done for the pipes ListT.

[Gabriella439]

Ok, I think I figured it out. This works:

instance (Monad m, Traversable m) => Traversable (ListT m) where
    traverse k (Select p) = fmap Select (traverse_ p)
      where
        traverse_ (Request v _ ) = closed v
        traverse_ (Respond a fu) = _Respond <$> k a <*> traverse_ (fu ())
          where
            _Respond a_ a' = Respond a_ (\_ -> a')
        traverse_ (M       m   ) = fmap M (sequenceA (fmap traverse_ m))
        traverse_ (Pure     r  ) = pure (Pure r)

[treeowl]

sequenceA (fmap ...) should be traverse .... Have you checked that this matches the Foldable instance? On May 29, 2016 12:40 PM, "Gabriel Gonzalez" notifications@github.com wrote:

Closed #171 https://github.com/Gabriel439/Haskell-Pipes-Library/issues/171 via f09c636 https://github.com/Gabriel439/Haskell-Pipes-Library/commit/f09c636cba067f3af1338a7e2a8d08002f0aa34a .

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Gabriel439/Haskell-Pipes-Library/issues/171#event-675457856, or mute the thread https://github.com/notifications/unsubscribe/ABzi_cVpWVZ5zTSS3dO5EzLOYvy0Rqn2ks5qGcGJgaJpZM4IpUd9 .

[Gabriella439]

I fixed sequenceA (fmap traverse_ m) to just be traverse traverse_ m

Also, I did verify that this matches the Foldable instance

[treeowl]

Excellent! I don't know if this instance will be useful, but it's great to have it.