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

Disclaimer

I’m not a regular DDD guy, i come from FP

FP ❤️ DDD

Even though most of the DDD litterature is illustrated with OO langs
FP maps really well to DDD (some would argue way better. I would argue that).
An obvious difference would be defaulting on entities vs value objects (mutability)
but this goes farther than that
The first is illustrated with F#
the second with scala, but that’s not the biggest difference
I’ll be closer to the second one

Algebraic design

Describe the domain model as an “algebra”.
very roughly speaking, it’s a collection of function types representing the possible operations of your model
that sounds a lot like “regular” DDD (and that’s a way of working you’re naturally nudged into when doing FP). That’s part of why i’m saying FP is adapted to DDD: it’s a natural way of working in FP languges. No need to write books or organize conferences to advertise it

Common abstractions

One thing that makes FP really shine, is how it allows abstractions. You may have heard that
it makes composition and code reuse easy thanks to immutability, all that. That’s true, but
here i’m talking about something more specific:
common abstractions (shared across projects, and even across languages)

Ubiquitous Language

these abstractions are so robust and so useful (ie not tied to the language semantics), that
it’s feasible to make them part of a shared vocabulary, and ultimately part of the model

Ubiquitous Language
Say what?!

that’s a key difference with “regular” DDD. Normally, technical concerns should not be exposed
in the model. They can be used to ease implementation, but not directly exposed 



`Money` has a monoid instance

-- addMoney a (addMoney b c) == (addMoney (addMoney a b) c)
addMoney :: Money -> Money -> Money
zeroMoney :: Money
the two are equivalent.
One requires to know what a monoid is
One has to explain it
both are valid choices, with different strengths

Tradeoffs, tradeoffs, tradeoffs

maintaining a set of common abstractions as a shared vocabulary can be extremely effective
it works because with properly defined abstractions with a precise meaning and general applicability

I’m getting to the point

I will talk about two such abstractions today. Maybe they can be used in a shared vocabulary
maybe they can just help you with implementation.

Just the implementation:
it’s still OK!

Properly defined abstractions usually provide strong intuition
even if you don’t make those part of the model, you can rely on them when implementing, and that
allows you to offload a lot of work to intuition (system 1 / system 2, as “Thinking Fast And Slow” calls them)

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

It’s a joke!

it’s so pervasive it’s a joke, but its pervasivity is not immediately obvious
“it’s a for loop” would be a bit less funny, I think

Let’s go (for real this time)

that’s it for the longest intro ever (and i’m saying this as a prog rock fan).

Promise.all

Promise.all([p1, p2, p3])
  .then(([v1, v2, v3]) => {
    console.log("Got values", v1, v2, v3);
  });
Promise.all collects all the promise in a single one

Promise.all



const myMap = new Map([
  ["p1", p1], ["p2", p2], ["p3", p3]
]);

// any iterable!
Promise.all(myMap)
  .then((vs) => {
    console.log("Got values", vs);
  });
it works with any iterable (but does not retain the original shape)

Promise.all

Promise.all is nice because it’s not hardcoded with lists.
Sadly it “forgets” the original shape

Now in Haskell (sorry)

Now in Haskell (sorry)



sequenceA [p1, p2, p3]
  >>= (\[v1, v2, v3] ->
     print ("Got values", v1, v2, v3)
  )
Same as Promise.all (except async values in haskell are lazy, not eager as JS promises) 


Promise.all([p1, p2, p3])
  .then(([v1, v2, v3]) => {
    console.log("Got values", v1, v2, v3);
  });
see how it’s close to the JS version?

It’s… sequence?

We usually don’t happen to have a list of async values lying around.
most often we have a list of values, and a function turning them into async
values. 




Promise.all(userIds.map(getUser))
  .then(users => …);

It’s really common to first apply a function with map, and then collect the results. That’s exactly what traverse does 


userIds :: [UserId]
userIds = ["1", "2", "3"]

getUser :: UserId -> IO User
getUser uid = …

allUsers :: IO [User]
allUsers = traverse getUser userIds
That’s what usually happens in real life

Does it work on any iterable?

ok so it works on lists, but is at as generic as Promise.all?

It works on any traversable
(there are lots of them)

this may sound like a joke, but it’s actually the sign that traverse
is an important function
it works on lists, maps, trees…

and it retains shapes!







getUsers :: Map Role UserId
         -> IO (Map Role User)
getUsers usersMap =
  traverse getUser usersMap

and it composes!







getUsers :: Map Role [UserId]
         -> IO (Map Role [User])
getUsers usersMap =
  traverse (traverse getUser) usersMap

and it composes!







getUsers :: Map Role [UserId]
         -> IO (Map Role [User])
getUsers usersMap =
  getCompose
    (traverse getUser (Compose usersMap))
if you nest traversables, you can traverse them all at once
(you need to tell the compiler, though)

So. Traversable.

Promise.all is a super useful function
traverse is already way more powerful because it retains shapes
and composes naturally

So. Traversable.
(this is a lie)













traverse :: Traversable t
         => (a -> IO b)
         -> t a -> IO (t b)
It allows us to “move” the IO from “inside” the t, to “outside” it.
it works for any t that is traversable

Many things are traversable

Traversable can be derived automatically for many types. 


data BinaryTree a
  = Leaf a
  | Node (BinaryTree a) (BinaryTree a)
  deriving (Eq, Show, Ord,
            Functor, Foldable,
            Traversable)
The implementation of traverse is mechanically derivable from the type
Foldable is interesting because it captures a bit the idea of promise.all
iterating over a value while forgetting its shape

That’s it for Promise.all

generalizing on many data types is super useful. Maps, lists, trees, it’s
nice, but not 100% mindblowing. Let’s look at another data type that’s traversable

Conditional execution

i want to run this code, only if i have a value

Is it traverse?







traverse  :: (a -> IO b) 
          -> Maybe a -> IO (Maybe b)
maybe is like optional. this is what traverse looks like with Maybe

It’s traverse_!







traverse_ :: (a -> IO b)
          -> Maybe a -> IO ()
here we don’t care about the result, we care only about side effects

Control flow as data structures

That’s a sub-result of what we’ve seen earlier, but it’s slightly unexpected
this showcases a great strength of (typed fp): use data structures for control flow

I lied

a few slides ago, I showed you the signature of traverse. This was a lie.

traverse, for real







traverse :: (Traversable t, Applicative f)
         => (a -> f b)
         -> t a -> f (t b)
not just IO, any “context” works

What the hell is a context?

i won’t delve into details, but the idea is that we talk about values
that comes with a context. For IO, it’s side effects and asynchronicity

What the hell is
an applicative context?

here we need the context to be able to do specific things 









fuse :: Applicative f
     => (f a, f b)
     -> f (a, b)
i have two value with two contexts: i can combine the two contexts
into a single one 









pure :: Applicative f
     -> a -> f a
     
fmap :: Applicative f
     => (a  -> b)
     -> f a -> f b
i also need two things: creating an “empty” context
and making a regular function work within a context
with all this, you may be able to see how it relates to
traverse: while iterating, you need to collect the results

(yeah, I know, it’s abstract)

this seems quite abstract, let’s see a couple examples

Input validation

A nice improvement over exceptions for input parsing

Single check for multiple values









parseInt :: String -> Validation [Error] Int
parseInt = …

parseValues :: [String] -> Validation [Error] [Int]
parseValues values =
  traverse parseInt values
parse each value independently, collect errors as needed
a bogus value won’t prevent the other values to be checked
we still need each value to parse for the result to be a success

Multiple checks for a single value









checks :: [String -> Validation [Error] ()]
checks = …

checkValue :: String -> Validation [Error] ()
checkValue v =
  traverse_ (\check -> check v) checks
runs every check in the list on a single value, and collects errors, if any
here we are only interested in the context, not in the value being wrapped
each check is run independently. a check failure won’t prevent other checks
to be run

Building parsers

“I can parse this from the environment” is a context 


parseString :: String -> Parser String
parseString = …

parseVariables :: [String]
               -> Parser [String]
parseVariables names =
  traverse parseString names
Here we build a parser of list from a list of parsers

Contexts compose

remember how we combined traversables with compose?

Contexts compose








readFile :: FilePath -> IO String
readFile = …

parseFile :: String -> Validation [Errors] Value
parseFile = …
we can do the same with contexts

Contexts compose







parseFiles :: [FilePath]
           -> IO (Validation [Errors] [Value])
parseFiles paths =
  let readAndParse path =
        Compose (fmap parseFile (readFile path))
  in getCompose (traverse readAndParse paths)
here we compose two contexts (IO and Validation)
we still need to tell the compiler we want to fuse the two contexts
so Compose and getCompose, but apart from that, it’s a regular traverse

Data <=> control flow

here, we have been using mostly the traversable as a data structure
and the applicative as a control flow context
turns out data structures can be view as applicatives

Data manipulation








(a, Maybe b)  -> Maybe (a, b)
Either a [b]  -> [Either a b]
[Either a b]  -> Either a [b]
[a -> b] -> (a -> [b])
here both the traversable and the context are data structures
here, sequence makes things more obvious
it’s super handy to quickly move between representations
it’s not unusual to have multiple calls of sequenceA working on different
contexts. Just the implementation may be hard to read, but what matters is
types. chained sequenceA calls just tell you that the inversions are
standard and that no trick business is happening. that’s good!

Data manipulation







(a, Maybe b)  -> Maybe (a, b)
Here, we invert the tuple and the maybe
in a way, we lose information about the tuple’s left
(it was always defined, now it’s in the maybe)

Data manipulation







Either a [b]  -> [Either a b]
Here, we invert the either and the list
think of what can happen: if the either is a right, we’ll get
a list of rights. If the either is a left, we’ll get a list containing a single left

Data manipulation







[Either a b]  -> Either a [b]
the other direction now
if all the eithers are right, we collect them
if at least one of them is a Left, we get it (the first one)

Data manipulation







Monoid a => [Validation a  b]
         ->  Validation a [b]
almost the same, except here we have a validation, and the left is a list
this does the same thing if every validation is a success
but it will accumulate errors in a list instead of returning only the first one

Function composition








combineResults :: [Context -> Value]
               -> Context -> [Value]
combineResults fns = sequenceA fns
I’m using sequence again since here it makes more sense
the tricky part here is that the context itself is Context ->
what this actually does is call every function in the list with
the provided value and collect the results
a common use case for this is dependency injection (which is glorified function application)

Data manipulation

many traversable structures are also applicative contexts so it can go both ways
here the properties guaranteed by traverse let you know what happens
you would not have that with hand-rolled functions
it’s very convenient to know what happens at a glance, but it can be hard to read for
some. In case of doubt, types are here to help

What have we learned?

Good abstractions change
the way you think

not only it provides intuition and frees you from details
it also comes with checkable laws (ie free unit tests)
so the behaviour is predictable

Good abstractions change
the way you talk

once they’re properly understood, they allow to be extremely precise
when talking with other people

“it’s a for loop”

traverse actually captures the idea of a for loop
“The essence of the iterator pattern” explores that
(really interesting, it showcases different ways of composing contexts)

Thanks!