Loading

FretLink / @clementd

`$ whoami`

- Clément Delafargue
- @clementd on twitter
- blog.clement.delafargue.name on the web

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

`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

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

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

https://www.youtube.com/watch?v=y8OnoxKotPQ

let’s just keep four services for the sake of simplicity

so what we want here is to get the list of secrets based on the list of services names, by parsing the environment

how can we do that? with traverse

here i traverse my list of services names with a function that retrieves the secret

some of you may be more familiar with mapM. It’s used the same

see, the code is the same

for our more imperative-minded friends

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

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 is the same, but for historical reasons, it overconstrains the f to be a monad

forM is the same, but with the arguments flipped

`Map`

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

you guessed it, *coquinous*, for all k, (Map k) has a traversable instance

`traverse getSecret`

may appear a few times in this talk
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
how could I get a tree of secrets? I wonder if we could use…

(If you ask nicely)

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

(If you ask nicely)

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

```
{-# 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
and back to traversing things

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

what about putting a traversable in a traversable?

Now we want to group services together, so we have a list inside of our record

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

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

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

As we’ve seen,

sets are not traversable because sets are not functors, but

that’s for another day.

Is it all traverse can do?

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

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

for my η-reduction stans

for my relude stans

`traverse`

?
If you consider that

it may be more obvious that it could be done with traverse.

`Maybe`

is a list with at most one elementit may be more obvious that it could be done with traverse.

`traverse_`

!
If you don’t care about the result, you can throw away the traversable structure.

you don’t need the

you don’t need the

`Traversable`

constraint, since you don’t keep it. (That’s why it’s defined in `Data.Foldable`

)
here, we keep the original structure with traverse, just to

throw it away with void. We require a traversable constraint

for no reason

throw it away with void. We require a traversable constraint

for no reason

conditions may apply

Tuples have a

`Traversable`

instance
conditions may apply

But it may not be what you expect

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

parameters, homogeneous pairs are a special case,

parametricity dictates that only the last element can be traversed

but I still want to traverse both sides at once!

since there are two sides, we need to provide two functions

the wrapped types can be different (c, and d),

but the applicative has to be the same (f)

but the applicative has to be the same (f)

`IO`

works for any applicative (not even monad)

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/

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”

help, doc and everything. Things I couldn’t get with a monadic

parser.

We start to stray further away from “mapping on monads”

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

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

and

within the applicative context

`pure`

for “empty” structuresand

`<*>`

to reconstruct the structure by combining elementswithin the applicative context

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

only handles the

`IO`

level, not the `Validation`

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

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

notice that

`Compose`

is in the traverse argument, while getComposeis 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

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

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
The signatures themselves don’t tell the whole story, but

knowing it only uses traversable and applicative behaviour

makes things more obvious.

knowing it only uses traversable and applicative behaviour

makes things more obvious.

if the Either is a right, it’s obvious. but what happens

if the either is a Left?

if the either is a Left?

here we forget about the string if the maybe is a Nothing

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)

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

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

`Text`

?
can we use traverse with Text?

does this signature make sense? Text is not a parametric type, whereas applicative functors are parametric

`Text`

has a monoid instance, and anything that is traversable is also foldable
fold is to foldMap is what sequenceA is to traverse

i’m here for a reason after all

the reason is that it’s traverse

with a little trick, we can do that with traverse.

it even works with

is an applicative functor. That’s what Const provides

`traverse_`

. Here, what we need to use traverseis an applicative functor. That’s what Const provides

the *phantom type*:

it does not appear on the RHS. But it makes Const a parametric

type, fit to use as an applicative

`b`

type parameter here is called a it does not appear on the RHS. But it makes Const a parametric

type, fit to use as an applicative

Const provides us with an applicative instance, for any monoid

let’s see why that makes sense

let’s see why that makes sense

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

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

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)

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

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

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

whereas

`any`

,whereas

`traverse_`

acts like `all`

`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

a bit limited. traverse can be reasoned about in different ways

`traverse`

, à fond la `forM`

(titre non retenu)

still, there’s something good coming from its (maybe superficial) closeness with

Well,

- 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

`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

https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf

this paper showcases different uses of

of applicative composition (not just

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

this paper showcases different uses of

`traverse`

, different kindsof applicative composition (not just

`Compose`

). It’s rather easyto 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

http://strictlypositive.org/IdiomLite.pdf

along with “Applicative Programming with effects”, it’s a core paper

about applicative functors

along with “Applicative Programming with effects”, it’s a core paper

about applicative functors