Skip to content

Instantly share code, notes, and snippets.

@divarvel
Last active May 13, 2020 16:33
Show Gist options
  • Save divarvel/cb41f9af736b3219739b572d7810eb88 to your computer and use it in GitHub Desktop.
Save divarvel/cb41f9af736b3219739b572d7810eb88 to your computer and use it in GitHub Desktop.

% It's traverse! % Clément Delafargue % DDDDD 2020-05-15


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

  • DDD Made Functional (Scott Wlaschin)
  • Functional And Reactive Domain Modelling (Debasish Gosh)
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

  • collects results
  • works on any iterable
  • does not retain the original iterable
`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 => …);

</big>

<details role="note">
It's really common to first apply a function with map, and then collect the
results. That's exactly what traverse does
</details>

---

```haskell


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

  • Lists
  • Maps
  • Trees
  • Maybe
  • Either
  • your own types
`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?






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

What the hell is
an applicative context?






pure :: Applicative f
     -> a -> f a
     
lift :: 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
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 =
  let readAndParse =
        Compose . fmap parseFile . readFile path
  in getCompose . traverse readAndParse
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

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 <=> 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]
[(String, a)] -> (String, [a])
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

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?

- properly defined abstractions require work, but pay off later - traverse being polymorphic on two axes make it really versatile - the data structure / control flow flexibility of FP make it even more - traverse makes composition easy on both axes

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

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment