Haskell IntroductionData.Aeson - JSON in HaskellHaskell Applicative FunctorHaskell Arbitrary-rank polymorphism with RankNTypesHaskell ArithmeticHaskell ArrowsHaskell AttoparsecHaskell BifunctorHaskell CabalHaskell Category TheoryHaskell Common functors as the base of cofree comonadsHaskell Common GHC Language ExtensionsHaskell Common monads as free monadsHaskell ConcurrencyHaskell Containers - Data.MapHaskell Creating Custom Data TypesHaskell Data.TextHaskell DatabasesHaskell Date and TimeHaskell Fixity declarationsHaskell FoldableHaskell Foreign Function InterfaceHaskell Free MonadsHaskell Function call syntaxHaskell Function compositionHaskell FunctorHaskell Generalized Algebraic Data TypesHaskell GHCJSHaskell Google Protocol BuffersHaskell Graphics with GlossHaskell Gtk3Haskell Higher-order functionsHaskell Infix operatorsHaskell IOHaskell LensHaskell List ComprehensionsHaskell ListsHaskell LoggingHaskell ModulesHaskell Monad TransformersHaskell MonadsHaskell MonoidHaskell OptimizationHaskell Overloaded LiteralsHaskell ParallelismHaskell Parsing HTML with taggy-lens and lensHaskell Partial ApplicationHaskell Phantom typesHaskell PipesHaskell ProfunctorHaskell ProxiesHaskell QuickCheckHaskell Reactive-bananaHaskell Reader / ReaderTHaskell Record SyntaxHaskell Recursion SchemesHaskell Rewrite rules (GHC)Haskell RoleHaskell Sorting AlgorithmsHaskell StackHaskell State MonadHaskell Streaming IOHaskell StrictnessHaskell Syntax in FunctionsHaskell Testing with TastyHaskell TraversableHaskell Tuples (Pairs, Triples, ...)Haskell Type algebraHaskell Type ApplicationHaskell Type ClassesHaskell Type FamiliesHaskell Typed holesHaskell Using GHCiHaskell VectorsHaskell Web DevelopmentHaskell XMLHaskell zipWithMTemplate Haskell & QuasiQuotes

Haskell Traversable

From WikiOD

The Traversable class generalises the function formerly known as mapM :: Monad m => (a -> m b) -> [a] -> m [b] to work with Applicative effects over structures other than lists.

Traversing a structure in reverse[edit | edit source]

A traversal can be run in the opposite direction with the help of the Backwards applicative functor, which flips an existing applicative so that composed effects take place in reversed order.

newtype Backwards f a = Backwards { forwards :: f a }

instance Applicative f => Applicative (Backwards f) where
    pure = Backwards . pure
    Backwards ff <*> Backwards fx = Backwards ((\x f -> f x) <$> fx <*> ff)

Backwards can be put to use in a "reversed traverse". When the underlying applicative of a traverse call is flipped with Backwards, the resulting effect happens in reverse order.

newtype Reverse t a = Reverse { getReverse :: t a }

instance Traversable t => Traversable (Reverse t) where
    traverse f = fmap Reverse . forwards . traverse (Backwards . f) . getReverse

ghci> traverse print (Reverse "abc")

The Reverse newtype is found under Data.Functor.Reverse.

Definition of Traversable[edit | edit source]

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f

    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

    mapM :: Monad m => (a -> m b) -> t a -> m (t b)
    mapM = traverse

    sequence :: Monad m => t (m a) -> m (t a)
    sequence = sequenceA

Traversable structures t are finitary containers of elements a which can be operated on with an effectful "visitor" operation. The visitor function f :: a -> f b performs a side-effect on each element of the structure and traverse composes those side-effects using Applicative. Another way of looking at it is that sequenceA says Traversable structures commute with Applicatives.

An instance of Traversable for a binary tree[edit | edit source]

Implementations of traverse usually look like an implementation of fmap lifted into an Applicative context.

data Tree a = Leaf
            | Node (Tree a) a (Tree a)

instance Traversable Tree where
    traverse f Leaf = pure Leaf
    traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r

This implementation performs an in-order traversal of the tree.

ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)
**    +--'b'--+
**    |       |
** +-'a'-+ +-'c'-+
** |     | |     |
** *     * *     *

ghci> traverse print myTree

The DeriveTraversable extension allows GHC to generate Traversable instances based on the structure of the type. We can vary the order of the machine-written traversal by adjusting the layout of the Node constructor.

data Inorder a = ILeaf
               | INode (Inorder a) a (Inorder a)  -- as before
               deriving (Functor, Foldable, Traversable)  -- also using DeriveFunctor and DeriveFoldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving (Functor, Foldable, Traversable)

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving (Functor, Foldable, Traversable)
** injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)

preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)

postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x

ghci> traverse print (inorder myTree)
ghci> traverse print (preorder myTree)
ghci> traverse print (postorder myTree)

Instantiating Functor and Foldable for a Traversable structure[edit | edit source]

import Data.Traversable as Traversable

data MyType a =  -- ...
instance Traversable MyType where
    traverse = -- ...

Every Traversable structure can be made a Foldable Functor using the fmapDefault and foldMapDefault functions found in Data.Traversable.

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault is defined by running traverse in the Identity applicative functor.

newtype Identity a = Identity { runIdentity :: a }

instance Applicative Identity where
    pure = Identity
    Identity f <*> Identity x = Identity (f x)

fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f = runIdentity . traverse (Identity . f)

foldMapDefault is defined using the Const applicative functor, which ignores its parameter while accumulating a monoidal value.

newtype Const c a = Const { getConst :: c }

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)

Traversable structures as shapes with contents[edit | edit source]

If a type t is Traversable then values of t a can be split into two pieces: their "shape" and their "contents":

data Traversed t a = Traversed { shape :: t (), contents :: [a] }

where the "contents" are the same as what you'd "visit" using a Foldable instance.

Going one direction, from t a to Traversed t a doesn't require anything but Functor and Foldable

break :: (Functor t, Foldable t) => t a -> Traversed t a 
break ta = Traversed (fmap (const ()) ta) (toList ta)

but going back uses the traverse function crucially

import Control.Monad.State
** invariant: state is non-empty
pop :: State [a] a
pop = state $ \(a:as) -> (a, as)

recombine :: Traversable t => Traversed t a -> t a
recombine (Traversed s c) = evalState (traverse (const pop) s) c

The Traversable laws require that break . recombine and recombine . break are both identity. Notably, this means that there are exactly the right number elements in contents to fill shape completely with no left-overs.

Traversed t is Traversable itself. The implementation of traverse works by visiting the elements using the list's instance of Traversable and then reattaching the inert shape to the result.

instance Traversable (Traversed t) where
    traverse f (Traversed s c) = fmap (Traversed s) (traverse f c)

Transforming a Traversable structure with the aid of an accumulating parameter[edit | edit source]

The two mapAccum functions combine the operations of folding and mapping.

**                                                       A Traversable structure
**                                                                   |
**                                                     A seed value  |
**                                                             |     |
**                                                            |-|  |---|
mapAccumL, mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
**                                      |------------------|              |--------|
**                                               |                            |
**                       A folding function which produces a new mapped       |
**                         element 'c' and a new accumulator value 'a'        |
**                                                                            |
**                                                            Final accumulator value
**                                                             and mapped structure

These functions generalise fmap in that they allow the mapped values to depend on what has happened earlier in the fold. They generalise foldl/foldr in that they map the structure in place as well as reducing it to a value.

For example, tails can be implemented using mapAccumR and its sister inits can be implemented using mapAccumL.

tails, inits :: [a] -> [[a]]
tails = uncurry (:) . mapAccumR (\xs x -> (x:xs, xs)) []
inits = uncurry snoc . mapAccumL (\xs x -> (x `snoc` xs, xs)) []
    where snoc x xs = xs ++ [x]

ghci> tails "abc"
["abc", "bc", "c", ""]
ghci> inits "abc"
["", "a", "ab", "abc"]

mapAccumL is implemented by traversing in the State applicative functor.

{*# LANGUAGE DeriveFunctor #-}

newtype State s a = State { runState :: s -> (s, a) } deriving Functor
instance Applicative (State s) where
    pure x = State $ \s -> (s, x)
    State ff <*> State fx = State $ \s -> let (t, f) = ff s
                                              (u, x) = fx t
                                          in (u, f x)

mapAccumL f z t = runState (traverse (State . flip f) t) z

mapAccumR works by running mapAccumL in reverse.

mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse

Transposing a list of lists[edit | edit source]

Noting that zip transposes a tuple of lists into a list of tuples,

ghci> uncurry zip ([1,2],[3,4])
[(1,3), (2,4)]

and the similarity between the types of transpose and sequenceA,

** transpose exchanges the inner list with the outer list
**           +---+-->--+-+
**           |   |     | |
transpose :: [[a]] -> [[a]]
**            | |     |   |
**            +-+-->--+---+
** sequenceA exchanges the inner Applicative with the outer Traversable
**                                             +------>------+
**                                             |             |
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
**                                                |       |
**                                                +--->---+

the idea is to use []'s Traversable and Applicative structure to deploy sequenceA as a sort of n-ary zip, zipping together all the inner lists together pointwise.

[]'s default "prioritised choice" Applicative instance is not appropriate for our use - we need a "zippy" Applicative. For this we use the ZipList newtype, found in Control.Applicative.

newtype ZipList a = ZipList { getZipList :: [a] }

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

Now we get transpose for free, by traversing in the ZipList Applicative.

transpose :: [[a]] -> [[a]]
transpose = getZipList . traverse ZipList

ghci> let myMatrix = [[1,2,3],[4,5,6],[7,8,9]]
ghci> transpose myMatrix