Haskell/Traversable

Мы уже изучили четыре класса типов из пяти в Prelude, которые могут быть использованы для манипуляции над структурами данных: Functor, Applicative, Monad и Foldable. Пятый - Traversable. To traverse означает "проходить по", именно это Traversable и обобщает: проход по структуре данных, собирая результаты на каждом шаге.

Функторы предназначены для проходов

Если traversing означает проход по чему-либо, то мы давно уже совершали проходы. Рассмотрим следующие похожие экземпляры Functor и Foldable для списков:

instance Functor [] where
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

instance Foldable [] where
    foldMap _ []     = mempty
    foldMap f (x:xs) = f x <> foldMap f xs

fmap f проходит по списку, применяет f для каждого элемента и собирает результаты путем построения нового списка. Подобно этому, foldMap f проходит по списку, применяет f к каждому элементу и собирает результаты, соединяя их при помощи mappend. Однако Functor и Foldable не достаточно, чтобы выразить все полезные способы прохождения. К примеру, предположим, что мы имеем следующий тест для отрицательных чисел с использованием Maybe...

deleteIfNegative :: (Num a, Ord a) => a -> Maybe a
deleteIfNegative x = if x < 0 then Nothing else Just x

... и мы хотим использовать его для реализации ...

rejectWithNegatives :: (Num a, Ord a) => [a] -> Maybe [a]

... который в ответ возвращает исходный список, обёрнутый в Just, если в нём нет отрицательных элементов, и Nothing в противном случае. Ни Foldable, ни Functor сами по себе не могут помочь. Используя Foldable можно было бы заменить структуру исходного списка любым Monoid, которое мы выберем для схлопывания fold), и и невозможно перевернуть это, чтобы дать либо исходный список, либо Nothing. Для Functor, fmap может быть заманчивым на первый взгляд...

GHCi> let testList = [-5,3,2,-1,0]
GHCi> fmap deleteIfNegative testList
[Nothing,Just 3,Just 2,Nothing,Just 0]

... но дальше нам нужен способ преврарить список из Maybe в Maybe для списка. Если хорошо приглядеться, то это чем-то похоже на fold. Однако, вместо того, чтобы просто собирать результаты, разрушая список, мы должны собрать контексты Maybe для значений и пересоздать список внутри собранного контекста. К счастью, существует класс типов, который по сути позволяет комбинировать Functor-котексты: Applicative . Applicative, в свою очередь, ведёт нас к классу, который нам нужен: Traversable.

instance Traversable [] where
    -- sequenceA :: Applicative f => [f a] -> f [a]
    sequenceA []     = pure []
    sequenceA (u:us) = (:) <$> u <*> sequenceA us

-- или:
instance Traversable [] where
    sequenceA us = foldr (\u v -> (:) <$> u <*> v) (pure []) us

Traversable для Applicative-контекстов, подобно тому как Foldable для Monoid-альных значений. С этой точки зрения, sequenceA является аналогом fold − она создаёт аппликативный итог контекстов внутри структуры и потом перестраивает структуру в новом контексте. sequenceA это то, что мы искали:

GHCi> let rejectWithNegatives = sequenceA . fmap deleteIfNegative
GHCi> :t rejectWithNegatives 
rejectWithNegatives
  :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
GHCi> rejectWithNegatives testList
Nothing
GHCi> rejectWithNegatives [0..10]
Just [0,1,2,3,4,5,6,7,8,9,10]

Существуют и другие методы для Traversable:

class (Functor t, Foldable t) => Traversable t where
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)

    -- Эти методы имеют реализации по умолчанию.
    -- Они просто являются спициализированными версиями первых двух.
    mapM      :: Monad m => (a -> m b) -> t a -> m (t b)
    sequence  :: Monad m => t (m a) -> m (t a)

Если sequenceA аналог fold, traverse аналог foldMap. Они могут быть определены в терминах друг друга, и минимальная реализация Traversable нуждается только в одном из них:

traverse f = sequenceA . fmap f
sequenceA = traverse id

Rewriting the list instance using traverse makes the parallels with Functor and Foldable obvious:

instance Traversable [] where
    traverse _ []     = pure []
    traverse f (x:xs) = (:) <$> f x <*> traverse f xs

-- Or, equivalently:
instance Traversable [] where
    traverse f xs = foldr (\x v -> (:) <$> f x <*> v) (pure []) xs

In general, it is better to write traverse when implementing Traversable, as the default definition of traverse performs, in principle, two runs across the structure (one for fmap and another for sequenceA).

We can cleanly define rejectWithNegatives directly in terms of traverse:

rejectWithNegatives :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
rejectWithNegatives = traverse deleteIfNegative

Упражнения
Give the Tree from Other data structures a Traversable instance. The definition of Tree is: data Tree a = Leaf a | Branch (Tree a) (Tree a)

Interpretations of Traversable

Traversable structures can be walked over using the applicative functor of your choice. The type of traverse...

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

... resembles that of mapping functions we have seen in other classes. Rather than using its function argument to insert functorial contexts under the original structure (as might be done with fmap) or to modify the structure itself (as (>>=) does), traverse adds an extra layer of context on the top of the structure. Said in another way, traverse allows for effectful traversals − traversals which produce an overall effect (i.e. the new outer layer of context).

If the structure below the new layer is recoverable at all, it will match the original structure (the values might have changed, of course). Here is an example involving nested lists:

GHCi> traverse (\x -> [0..x]) [0..3]
[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,0,3],[0,0,1,0],[0,0,1,1]
,[0,0,1,2],[0,0,1,3],[0,0,2,0],[0,0,2,1],[0,0,2,2],[0,0,2,3]
,[0,1,0,0],[0,1,0,1],[0,1,0,2],[0,1,0,3],[0,1,1,0],[0,1,1,1]
,[0,1,1,2],[0,1,1,3],[0,1,2,0],[0,1,2,1],[0,1,2,2],[0,1,2,3]
]

The inner lists retain the structure the original list − all of them have four elements. The outer list is the new layer, corresponding to the introduction of nondeterminism through allowing each element to vary from zero to its (original) value.

We can also understand Traversable by focusing on sequenceA and how it distributes context.

GHCi> sequenceA [[1,2,3,4],[5,6,7]]
[[1,5],[1,6],[1,7],[2,5],[2,6],[2,7]
,[3,5],[3,6],[3,7],[4,5],[4,6],[4,7]
]

In this example, sequenceA can be seen distributing the old outer structure into the new outer structure, and so the new inner lists have two elements, just like the old outer list. The new outer structure is a list of twelve elements, which is exactly what you would expect from combining with (<*>) one list of four elements with another of three elements. One interesting aspect of the distribution perspective is how it helps making sense of why certain functors cannot possibly have instances of Traversable (how would one distribute an IO action? Or a function?).

Упражнения

Having the applicative functors chapter fresh in memory can help with the following exercises. Consider a representation of matrices as nested lists, with the inner lists being the rows. Use Traversable to implement transpose :: [[a]] -> [[a]] which transposes a matrix (i.e. changes columns into rows and vice-versa). For the purposes of this exercise, we don't care about how fake "matrices" with rows of different sizes are handled. Explain what traverse mappend does. Time for a round of Spot The Applicative Functor. Consider: mapAccumL :: Traversable t =>Шаблон:Indent(a -> b -> (a, c)) -> a -> t b -> (a, t c) Does its type remind you of anything? Use the appropriate Applicative to implement it with Traversable. As further guidance, here is the description of mapAccumL in the Шаблон:Haskell lib documentation: The mapAccumL function behaves like a combination of fmap and foldl; it applies a function to each element of a structure, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.

The Traversable laws

Sensible instances of Traversable have a set of laws to follow. There are the following two laws:

traverse Identity = Identity -- identity
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f -- composition

Plus a bonus law, which is guaranteed to hold:

-- If t is an applicative homomorphism, then
t . traverse f = traverse (t . f) -- naturality

Those laws are not exactly self-explanatory, so let's have a closer look at them. Starting from the last one: an applicative homomorphism is a function which preserves the Applicative operations, so that:

-- Given a choice of f and g, and for any a,
t :: (Applicative f, Applicative g) => f a -> g a

t (pure x) = pure x
t (x <*> y) = t x <*> t y

Note that not only this definition is analogous to the one of monoid homomorphisms which we have seen earlier on but also that the naturality law mirrors exactly the property about foldMap and monoid homomorphisms seen in the chapter about Foldable.

The identity law involves Identity, the dummy functor:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

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

The law says that all traversing with the Identity constructor does is wrap the structure with Identity, which amounts to doing nothing (as the original structure can be trivially recovered with runIdentity). The Identity constructor is thus the identity traversal, which is very reasonable indeed.

The composition law, in turn, is stated in terms of the Compose functor:

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
    pure x = Compose (pure (pure x))
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

Compose performs composition of functors. Composing two Functors results in a Functor, and composing two Applicatives results in an Applicative . The instances are the obvious ones, threading the methods one further functorial layer down.

The composition law states that it doesn't matter whether we perform two traversals separately (right side of the equation) or compose them in order to walk across the structure only once (left side). It is analogous, for instance, to the second functor law. The fmaps are needed because the second traversal (or the second part of the traversal, for the left side of the equation) happens below the layer of structure added by the first (part). Compose is needed so that the composed traversal is applied to the correct layer.

Identity and Compose are available from Шаблон:Haskell lib and Шаблон:Haskell lib respectively.

The laws can also be formulated in terms of sequenceA:

sequenceA . fmap Identity = Identity -- identity
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA -- composition
-- For any applicative homomorphism t:
t . sequenceA = sequenceA . fmap t -- naturality

Though it's not immediately obvious, several desirable characteristics of traversals follow from the laws, including :

• Traversals do not skip elements.
• Traversals do not visit elements more than once.
• traverse pure = pure
• Traversals cannot modify the original structure (it is either preserved or fully destroyed).

Recovering fmap and foldMap

We still have not justified the Functor and Foldable class constraints of Traversable. The reason for them is very simple: as long as the Traversable instance follows the laws traverse is enough to implement both fmap and foldMap. For fmap, all we need is to use Identity to make a traversal out of an arbitrary function:

fmap f = runIdentity . traverse (Identity . f)

To recover foldMap, we need to introduce a third utility functor: Const from Шаблон:Haskell lib:

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

instance Functor (Const a) where
    fmap _ (Const x) = Const x

Const is a constant functor. A value of type Const a b does not actually contain a b value. Rather, it holds an a value which is unaffected by fmap. For our current purposes, the truly interesting instance is the Applicative one

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

(<*>) simply combines the values in each context with mappend . We can exploit that to make a traversal out of any Monoid m => a -> m function that we might pass to foldMap. Thanks to the instance above, the traversal then becomes a fold:

foldMap f = getConst . traverse (Const . f)

We have just recovered from traverse two functions which on the surface appear to be entirely different, and all we had to do was pick two different functors. That is a taste of how powerful an abstraction functors are .