Haskell Language
Atravesable

Introducción

Funcionalizador de funciones y plegable para una estructura transversal

import Data.Traversable as Traversable

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

Cada estructura de Traversable se puede convertir en un Foldable Functor usando las funciones fmapDefault y foldMapDefault que se encuentran en Data.Traversable .

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault se define ejecutando el traverse en el functor aplicativo de Identity .

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 se define utilizando el functor aplicativo Const , que ignora su parámetro mientras acumula un valor monoidal.

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)

Una instancia de Traversable para un árbol binario

Las implementaciones de traverse generalmente se ven como una implementación de fmap levantada en un contexto Applicative .

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

Esta implementación realiza un recorrido en orden del árbol.

ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)

--    +--'b'--+
--    |       |
-- +-'a'-+ +-'c'-+
-- |     | |     |
-- *     * *     *

ghci> traverse print myTree
'a'
'b'
'c'

La extensión DeriveTraversable permite a GHC generar instancias Traversable basadas en la estructura del tipo. Podemos variar el orden del recorrido escrito por la máquina ajustando el diseño del constructor Node .

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)
'a'
'b'
'c'
ghci> traverse print (preorder myTree)
'b'
'a'
'c'
ghci> traverse print (postorder myTree)
'a'
'c'
'b'

Atravesando una estructura en reversa

Un recorrido se puede ejecutar en la dirección opuesta con la ayuda del funtor aplicativo Backwards , que invierte un aplicativo existente para que los efectos compuestos se realicen en orden inverso.

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 se puede poner en uso en una " traverse invertida". Cuando el aplicativo subyacente de una llamada traverse se invierte con Backwards , el efecto resultante sucede en orden inverso.

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")
'c'
'b'
'a'

El Reverse newtype se encuentra en Data.Functor.Reverse.

Definición de Traversable

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 estructuras t son contenedores finitistas de elementos a que se pueden accionar con una operación effectful "visitante". La función de visitante f :: a -> fb realiza un efecto secundario en cada elemento de la estructura y la traverse compone los efectos secundarios utilizando el Applicative . Otra forma de verlo es que la sequenceA dice que las estructuras Traversable se conmutan con el Applicative s.

Transformación de una estructura transitable con la ayuda de un parámetro de acumulación

Las dos funciones mapAccum combinan las operaciones de plegado y mapeo.

--                                                       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

Estas funciones generalizan fmap en el fmap de que permiten que los valores asignados dependan de lo que sucedió anteriormente en el pliegue. Generalizan foldl / foldr en el foldr de que mapean la estructura en su lugar y la reducen a un valor.

Por ejemplo, tails pueden ser implementados utilizando mapAccumR y su hermana inits pueden implementarse utilizando 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 se implementa al atravesar el funtor aplicativo del State .

{-# 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 funciona ejecutando mapAccumL en sentido inverso .

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

Estructuras transitables como formas con contenidos.

Si un tipo t es Traversable , los valores de ta se pueden dividir en dos partes: su "forma" y su "contenido":

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

donde los "contenidos" son los mismos que los que "visitaría" utilizando una instancia Foldable .

Ir en una dirección, de ta a Traversed ta no requiere nada más que Functor y Foldable

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

Pero volviendo atrás usa la función traverse crucialmente.

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

Las leyes de Traversable requieren esa break . recombine y recombine . break son ambas identidades En particular, esto significa que hay exactamente los elementos numéricos correctos en el contents para rellenar la shape completamente sin dejar sobras.

Traversed t es Traversable sí mismo. La implementación de traverse funciona visitando los elementos utilizando la instancia de Traversable de la lista y luego volviendo a unir la forma inerte al resultado.

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

Transponer una lista de listas

Teniendo en cuenta que zip transpone una tupla de listas en una lista de tuplas,

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

y la similitud entre los tipos de transpose y 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)
--                                                |       |
--                                                +--->---+

la idea es usar la estructura de Traversable y Applicative [] para desplegar la sequenceA como una especie de zip n-ary , uniendo todas las listas internas de manera puntual.

[] 'Elección prioridad' 's por defecto Applicative instancia no es apropiado para nuestro uso - necesitamos un 'enérgico' Applicative . Para esto utilizamos el ZipList ZipList, que se encuentra en 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)

Ahora tenemos transpose de forma gratuita, por la que atraviesa en el ZipList Applicative .

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

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