Loading
FretLink / @clementd

It’s traverse!

$ whoami

dev haskell, former CTO, I've worked with several langages, I used scala a lot (not anymore). Nowadays, haskell, rust, JS (a bit)
mise en relation chargeurs et transporteurs. suivi plus transparent, aider les petits transporteurs environnement technique historique: node mongo. nouveaux services : haskell / pg

Why traverse?

as said in the abstract, it’s pervasive
it showcases really well how much mileage you can get from good abstractions
it also shows how FP lets you turn abstract concepts into concrete benefits

Reading env vars

as a concrete example, let’s consider the parsing of shared secrets from environment variables 
newtype Name = Name String
  deriving newtype (Eq, Show, IsString, Monoid)
newtype Secret = Secret String
  deriving newtype (Eq, Show, IsString)

getSecret :: Name -> IO Secret
getSecret (Name serviceName) =
  let varName = toUpper <$> serviceName <> "_SECRET"
   in Secret <$> getEnv varName
i know, it’s dirty code to do that, but bear with me 
services :: [Name]
services = [ "bingo"
           , "papaya"
           , "magicbaby"
           , "galactus"
           , "clogger"
           , "lmnop"
           , "raccoon"
           , "omegastar"
           , "olympus"
           , "eks"
           ]
here are a couple of common microservices names
microservices
https://www.youtube.com/watch?v=y8OnoxKotPQ 
services :: [Name]
services = [ "bingo"
           , "papaya"
           , "magicbaby"
           , "galactus"
           ]
let’s just keep four services for the sake of simplicity 
secrets :: [Secret]
secrets = [ "azerty123"
          , "thisissecure"
          , "lalettrea"
          , "yoloswag"
          ]
so what we want here is to get the list of secrets based on the list of services names, by parsing the environment

It’s traverse!

how can we do that? with traverse 
do
  secrets <- traverse getSecret services
  print secrets
here i traverse my list of services names with a function that retrieves the secret

It’s mapM!

some of you may be more familiar with mapM. It’s used the same 
do
  secrets <- mapM getSecret services
  print secrets
see, the code is the same

It’s forM!

for our more imperative-minded friends 
do
  secrets <- forM services getSecret
  print secrets
here the arguments are flipped. It looks more like an imperative for where the first argument is the looping part of an imperative for, and the function is the actual for body. here i’m calling a function, but I could put in a do block that spans several lines 
traverse :: (Traversable t, Applicative f)
         => (a -> f b)
         -> t a
         -> f (t b)
let’s have a look at the types. traverse lets me apply an effectful function (a -> f b) to a collection (t a), and collects the results in a single effect f (t b) 
    mapM :: (Traversable t, Monad f)
         => (a -> f b)
         -> t a
         -> f (t b)
mapM is the same, but for historical reasons, it overconstrains the f to be a monad 
    forM :: (Traversable t, Monad f)
         => t a
         -> (a -> f b)
         -> f (t b)
forM is the same, but with the arguments flipped

What about a Map?

readSecrets :: Map Name Name
            -> IO (Map Name Secret)
readSecrets = _
having names and secrets in two separate arrays is not really interesting (we lose the guarantee of having the same sizes). Here we want to have them in a Map instead: each names gives a secret. How can I get it, from a list of names?

It’s traverse!

you guessed it, coquinous, for all k, (Map k) has a traversable instance 
readSecrets :: Map Name Name
            -> IO (Map Name Secret)
readSecrets = traverse getSecret
traverse getSecret may appear a few times in this talk

What about trees?

data Rhododendron a
 = Rhododendron a [Rhododendron a]
 deriving (Show)
a labeled tree, but with an arbitrary number of subtrees at each node. Rhododendron is a french name, it’s usually called a rose tree 
readSecrets :: Rhododendron Name
            -> IO (Rhododendron Secret)
readSecrets = _
how could I get a tree of secrets? I wonder if we could use…

It’s traverse!
(If you ask nicely)

of course it’s traverse, but you have to ask GHC

It’s traverse!
(If you ask nicely)

our Rhododendron does not have a traversable instance yet, since it’s a newly created type

What about trees?

{-# LANGUAGE DeriveTraversable #-}

data Rhododendron a
 = Rhododendron a [Rhododendron a]
 deriving (Show, Functor, Foldable, Traversable)
Traversable can be automatically derived by GHC with the right extensions 
readSecrets :: Rhododendron Name
            -> IO (Rhododendron Secret)
readSecrets = traverse getSecret
and back to traversing things

With records

usually, our microservices topology is fixed (not the actual deployments, but the microservices graph). So we’d like to be able to be more typesafe and have the guarantee that a secret is available for every service we care about 
{-# LANGUAGE DeriveTraversable #-}

data Services a
 = Services
 { bingo     :: a
 , papaya    :: a
 , magicbaby :: a
 , galactus  :: a
 }
 deriving (Show, Functor, Foldable, Traversable)
a record gives us the guarantee that every value is defined. A polymorphic record can be seen as a collection, that you can traverse 
secrets :: IO (Services Secret)
secrets = traverse getSecret $
  Services
    { bingo     = "bingo"
    , papaya    = "papaya"
    , magicbaby = "magicbaby"
    , galactus  = "galactus"
    }
of course it’s traverse

Nested traversables

what about putting a traversable in a traversable? 
secrets :: Services [Name]
        -> IO (Services [Secret])
secrets = _
Now we want to group services together, so we have a list inside of our record

Is it traverse?

looks like we could use traverse here 
:t traverse @Services @IO getSecret
Services Name -> IO (Services Secret)
not exactly though, traverse only handles the outer layer

Of course it’s traverse!

but, as you know, “it’s always traverse”, so let’s have a try 
secrets :: Services [Name]
        -> IO (Services [Secret])
secrets = traverse traverseList
  where
    traverseList :: [Name]
                 -> IO [Secret]
    traverseList = traverse getSecret
first I traverse the list, and this gives me a function that can be used to traverse the record it could work for any two traversables: we only use traverse, no type-specific functions. 
newtype Compose f g a
 = Compose
 { getCompose :: f (g a)
 }
 
instance (Traversable f, Traversable g)
  => Traversable (Compose f g)
this pattern can be captured in code: Composes allows us to tell the compiler that we want to traverse two layers at once 
secrets :: Services [Name]
        -> IO (Services [Secret])
secrets = magicTraverse getSecret

  where
  
    magicTraverse f =
      fmap getCompose . traverse f . Compose
In real code, I tend to not use compose for readability, but:
it can be useful in abstract code (like in libraries), and
knowing compose exists mean that you know you can freely
compose traversables with no hidden surprises

Traversing collections

As we’ve seen, traverse allows to run an effectful function on any kind of collection (lists, trees, records)
sets are not traversable because sets are not functors, but
that’s for another day.
Is it all traverse can do?

Conditional execution

something we often do is conditionally run some code if a value is defined. In imperative languages, it’s often a if with a side effect and no else 
printIfAvailable :: Maybe String
                 -> IO ()
printIfAvailable (Just s) = putStrLn s
printIfAvailable Nothing  = pure ()
Here we can pattern match, but that’s close 
printIfAvailable :: Maybe String
                 -> IO ()
printIfAvailable =
  maybe (pure ()) putStrLn
for my η-reduction stans 
printIfAvailable :: Maybe String
                 -> IO ()
printIfAvailable =
  maybe pass putStrLn
for my relude stans

Is it traverse?

If you consider that Maybe is a list with at most one element
it may be more obvious that it could be done with traverse.

It is traverse_!

If you don’t care about the result, you can throw away the traversable structure.
you don’t need the Traversable constraint, since you don’t keep it. (That’s why it’s defined in Data.Foldable) 
printIfAvailable :: Maybe String
                 -> IO ()
printIfAvailable = traverse_ putStrLn
printIfAvailable :: Maybe String
                 -> IO ()
printIfAvailable = void . traverse putStrLn
here, we keep the original structure with traverse, just to
throw it away with void. We require a traversable constraint
for no reason

What about tuples?

It’s traverse!*
conditions may apply

Tuples have a Traversable instance

It’s traverse!*
conditions may apply

But it may not be what you expect 
λ> traverse getSecret ("magicbaby", "galactus")
("magicbaby", "yoloswag")
it only fetched the second secret: tuples have two type
parameters, homogeneous pairs are a special case,
parametricity dictates that only the last element can be traversed

What about traversing both sides?

but I still want to traverse both sides at once!

It’s bitraverse!

It’s bitraverse!

λ> bitraverse
     getSecret
     getSecret
     ("magicbaby", "galactus")
("lalettrea", "yoloswag")
since there are two sides, we need to provide two functions 
bitraverse
  :: (Bitraversable t, Applicative f) =>
     (a -> f c) -> (b -> f d)
  -> t a b -> f (t c d)
the wrapped types can be different (c, and d),
but the applicative has to be the same (f)

Not just IO

works for any applicative (not even monad)

EnvParser

has an applicative instance, but no monad instance 
secretParser :: Name
             -> Parser Secret
secretParser (Name s) =
  required $ nonEmptyString (toUpper <$> s <> "_SECRET")
see my blog post on applicative env parsers https://tech.fretlink.com/environment-variables-parsing-for-free-applicatives/

It’s traverse!

secretsParser :: Services Name
              -> Parser (Services Secret)
secretParser = traverse secretParser
here I get a composite parser for all the services, with
help, doc and everything. Things I couldn’t get with a monadic
parser.
We start to stray further away from “mapping on monads”

Why applicative?

the traversable constraint is how we define traverse, but
why the applicative one? we can have a look at the traversable
list instance to better understand 
instance Traverse [] where

  traverse :: Applicative f
           => (a -> f b)
           -> [a] -> f [b]
           
  traverse _ [] = pure []
  
  traverse f (x : xs) = 
    (:) <$> f x <*> traverse f xs
here we can see that we need pure for “empty” structures
and <*> to reconstruct the structure by combining elements
within the applicative context

What about nested applicatives?

parseJSONFile :: FilePath
              -> IO (Validation [String] Parsed)
parseJSONFile = …

parseFiles :: [FilePath]
           -> IO (Validation [String] [Parsed])
parseFiles = _
here we have two levels of applicative. traversing once
only handles the IO level, not the Validation

It’s traverse!

you already knew it 
parseFiles :: [FilePath]
           -> IO (Validation [String] [Parsed])
parseFiles = magicTraverse2 parseJSONFile

  where
  
    magicTraverse2 f =
      getCompose $ traverse (Compose . f)
Compose also lets us combine two applicatives in a single one.
notice that Compose is in the traverse argument, while getCompose
is outside. For traversables, Compose was outside, and getCompose was
fmapped inside the applicative context.
While composing traversables is obvious, composing applicatives is not as
much. So compose for applicatives can come in handy even when the applicatives
are known

What about things that are both applicative and traversable?

Until now, the examples had traversables that were clearly data structures,
while the applicatives where more about control flow. But a lot of data structures
also have an applicative instance.
Here i’ll use sequenceA instead of traverse, as the type signatures are a bit simpler 
sequenceA @[] @(Either String)

     [Either String a]
  -> Either String [a]
The signatures themselves don’t tell the whole story, but
knowing it only uses traversable and applicative behaviour
makes things more obvious. 
sequenceA @(Either String) @[] 

     Either String [a]
  -> [Either String a]
if the Either is a right, it’s obvious. but what happens
if the either is a Left? 
sequenceA @((,) String) @Maybe

     (String, Maybe a)
  -> Maybe (String, a)
here we forget about the string if the maybe is a Nothing 
sequenceA Maybe @((,) String)

      Maybe (String, a)
  -> (String, Maybe a)
here for instance, there’s something not entirely obvious
going on, that becomes unambiguous if you think about the
constraints. Spot it?
If the maybe is a nothing, we have to provide a string from
thin air. Since we now the tuple is built through its applicative
constraint, we know that the first element will be the monoid
identity (the empty string)

traverse and sequenceA

as helpers, to play with maybe, tuples and everything, they’re
super helpful. It might lead to dense code some times, so check
with your team if it’s okay. in any case, when you spot the pattern
it’s a great way to get going, and to do so with principled functions
since you know it uses traversable and applicative to work

What about Text?

can we use traverse with Text? 
scream :: [Text]
       -> Text
scream = _
does this signature make sense? Text is not a parametric type, whereas applicative functors are parametric

It’s foldMap!

Text has a monoid instance, and anything that is traversable is also foldable 
λ> foldMap (<> "! ") ["witness", "me"]
"witness! me! "
fold is to foldMap is what sequenceA is to traverse

But what if I told you…

i’m here for a reason after all

It’s still traverse!

the reason is that it’s traverse 
λ> getConst $ traverse (Const . (<> "! ")) ["witness", "me"]
"witness! me! "
with a little trick, we can do that with traverse. 
λ> getConst $ traverse_ (Const . (<> "! ")) ["witness", "me"]
"witness! me! "
it even works with traverse_. Here, what we need to use traverse
is an applicative functor. That’s what Const provides

Const

newtype Const a b = Const { getConst :: a }
the b type parameter here is called a phantom type:
it does not appear on the RHS. But it makes Const a parametric
type, fit to use as an applicative

Const

instance Monoid m => Applicative (Const m) where
Const provides us with an applicative instance, for any monoid
let’s see why that makes sense

Applicative / Monoid

mempty :: Monoid m => m
(<>)   :: Monoid m => m -> m -> m

pure       :: Applicative f => a -> f a
liftA2 (,) :: Applicative f => f a -> f b -> f (a, b)
try to see the similarities between monoid and applicative
the key here is to disregard completely the type parameters
in category theory, an applicative functor is also called “strong lax monoidal functor”
const allows us to lift any monoid to an applicative, using the monoidal behaviour.
for the rest, the values are discarded, so we don’t care

Some are both

A type can’t really be both an applicative and a monoid because
they have different kinds, but the applicative can have monoid
instances on applied types (eg IO or Validation) 
instance Monoid a => Monoid (IO a)

λ> foldMap putStrLn ["yolo", "swag"]
yolo
swag
λ> traverse_ putStrLn ["yolo", "swag"]
yolo
swag
in some cases the instances are consistent

Not always aligned

in some cases the instances are inconsistent 
instance Monoid e => Monoid (Validation e a)

isEven :: Int
       -> Validation [String] ()
isEven n | even n = Success ()
         | otherwise = Failure [show n <> " is not even"]
here we’ll take advantage of the monoid instance of Validation
not the monoid constraint is on the error type. we can expect
errors to be accumulated and the first success to be kept 
λ> foldMap isEven [2, 5]
Success ()

λ> traverse_ isEven [2, 5]
Failure ["5 is not even"]

λ> getConst $ traverse_ (Const . isEven) [2, 5]
Success ()
in some cases they are not: here foldMap acts like any,
whereas traverse_ acts like all

More than just mapM

the intution of “well it’s just a map that works on monads” is true, albeit
a bit limited. traverse can be reasoned about in different ways

traverse, à fond la forM
(titre non retenu)

Bref.

still, there’s something good coming from its (maybe superficial) closeness with for, as evidenced by the name forM. It makes it easier to understand why traverse is useful in so many context. the for loop is also pervasive in imperative languages so pervasive that we don’t even have jokes about it.
Well, traverse is a double generalization of for loops:
- all traversable types (more or less done in some langages with iterators)
- all applicative functors (virtually not done outside of functional languages)
even better, traverse works with composed types, on both axes

The essence of the iterator pattern

https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf
this paper showcases different uses of traverse, different kinds
of applicative composition (not just Compose). It’s rather easy
to read (there are some notation quirks due to the fact that applicative
was not a super type of monad at the time of writing) and enlightening

Applicative programming with effects

http://strictlypositive.org/IdiomLite.pdf
along with “Applicative Programming with effects”, it’s a core paper
about applicative functors

Thanks!