Applicative-wired monad pattern

Links
1

https://chrisdone.com/posts/applicative-wired-monad/

22 Likes
2

Thanks for sharing! I especially like the trick of writing the actions polymorphically and instantiate later.

Reminds me of provenience, in particular the data flow graph. That is what you mean by statically inspect the resulting structure, right? For my use case I needed the graph to hold all intermediate data, not only the labels, so I opted for mapping everything to pandoc.

But provenience definitely shares the pattern of returning Action (Value a). I should try to re-structure the library as a free monad!

1 Like
3

Nice! Yeah, being able to render a graph of the network before running it, exactly.

I used this pattern for a Shake-like build system at one job, it had a ā€˜planā€™ mode that would print a plan like Terraform. It could cache some things that were already ran, similar to Make/Shake.

Used the same pattern at another job for a network of Mealy machines which represented economics games like auctions, markets or so, which had a little web app and showed a literal graph with how many people were playing each game and what data was flowing between the games.

For the build system one, I did end up using a free monad and a free applicative, but that was mostly for the fun, I wouldnā€™t say itā€™s essential or necessary, though.

I did use this package, which is a clever trick entirely of its own: constrained-normal: Normalised Deep Embeddings for Constrained Type-Class Instances

4

That crucially relies on parametricity, I suppose?

Further I noticed that the Value GADT in your post looks like the free Applicative over the Either String functor, which suggests that attaching labels to actions is optional. So does that give the same functionality as sprinkling cost centre annotations in source code?

5

I believe that the Key constructor isnā€™t usually constructed but every Action requires a String to act as the label. The Key is used in the graph creation though.

6

Possibly, which type parameter do you have in mind?

Yeah, I have rewritten the Value type using a free applicative over Key (which has a vacuous Functor). Iā€™m not sure about the Either String functorā€™s role in this context.

Attaching labels to actions is entirely optional in the sense that the interpretation of the monad could generate unique names on the fly like a compiler does, then the graph would be a1, a2, etc. I can make an example of this, if helpful. (I put names in Action as I thought itā€™d be easier to digest.)

7

The example has type forall f. Applicative f => Action f IO something and specializing f = Value makes it possible to extract the graph. In a production environment one could set f = Identity.

Consider

flip Ap . either Key Pure
  :: Either String a -> Value (a -> b) -> Value b

This plays the role of Control.Applicative.Free.Ap

EDIT: But you are right: The term

flip Ap . Key . getConst
  :: Const String a -> Value (a -> b) -> Value b

works just as well, so Value is more likely the free Applicative over Const.

2 Likes
8

Right, that is crucial for the example I did. But you can pack both the real running and the graphing into one like this:

So I do think the higher order bit is the having all actions in the API returning and accepting an applicative of some name, like Value a or similar, which unlocks the structure being visible.

The parametrising of the given applicative f I think was an incidental choice. Maybe I should add this to the blog post? :thinking:

EDIT: though, the graph function builds a gimmie in that example would repeat side effects, due to each action running the inputs it needs, so one would have to be careful not to use it. Perhaps the parametrising is a little cleaner to avoid subtle issues like that.

9

I changed the example code to use a free monad and free applicative.

10

Iā€™ve enjoyed (something similar to) this too! I wonder if thereā€™s some relationship with Relative Monads, though I suspect they are differently capable.

Also, given that f necessarily has an Applicative instance, Spec could be redefined as:

 data Spec f m a where
-  Spec :: String -> f i -> (i -> m a) -> Spec f m (f a)
+  Spec :: String -> f (m a) -> Spec f m (f a)

Effectively eliminating the inlined Coyoneda f.

Cascading the changesā€¦

-act :: String -> f i -> (i -> m a) -> Action f m (f a)
-act l i f = Action $ liftF $ liftAp $ Spec l i f

+act :: String -> f (m a) -> Action f m (f a)
+act l fma = Action $ liftF $ liftAp $ Spec l fma

 example :: Applicative f => Action f IO (f (ByteString, ByteString))
 example = do
-  file1 <- act "read_file_1" (pure ()) $ const $ S.readFile "file1.txt"
+  file1 <- act "read_file_1" (pure $ S.readFile "file1.txt")
-  file2 <- act "read_file_2" file1 $ S.readFile .  unwords . words . S8.unpack
+  file2 <- act "read_file_2" (S.readFile .  unwords . words . S8.unpack <$> file1)
   pure $ (,) <$> file1 <*> file2

 runIO :: Action Identity IO a -> IO a
 runIO = foldFree (runAp io) . runAction where
   io :: Spec Identity IO x -> IO x
   io = \case
-    Spec name input act' -> do
+    Spec name input -> do
       putStrLn $ "Running " ++ name
-      out <- act' $ runIdentity input
+      out <- runIdentity input
       pure $ Identity out

An alternative cascade would be to keep the type of act mostly as it was but require Functor f and do an explicit fmap. However the file1 example becomes a bit nicer with act fully altered. ( Note that you could have this version of act even without eliminating the Coyoneda just by passing id for i ā†’ m a. )

3 Likes
11

Nice, I like this simplification, thank you! :folded_hands:

12

One fun follow-up: if one wants to avoid explicitly labelling their nodes, one could use StaticPtr, and thereā€™s the IsStatic class, to get something like: act $ static (readFile <$> file1), as StaticPtr already contains the package file and line/col, it would make reporting easy enough. Havenā€™t tested it, but in principle itā€™d work.

1 Like
13

Similarly HasCallStack!

14

Yep, I considered that first, but because it can be elided, itā€™s a bit unfortunate. The three options I know of:

  • HasCallStack - convenient but not sound when moving code around. So itā€™s a bit hacky.
  • StaticPtr - requires a keyword, but is sound wrt moving things around (modulo SPJā€™s recent comments)
  • $foo - sound and accurate, but slows down compilation a bit to run some TH code to get the location.

Pros and cons all round.

3 Likes
15

Thereā€™s require-callstack by @parsonsmatt, which prevents it from being elided.

4 Likes
16

Does that address this Callstacks change when constraints are substituted with type aliases in GHC 9.8 (#25529) Ā· Issues Ā· Glasgow Haskell Compiler / GHC Ā· GitLab ? Thatā€™s what I understood by ā€œelidedā€.

17

Interesting, I had no idea about that and I have no idea whether require-callstack addresses it!

18

Iā€™ve been doing some reading and I think this is essentially ā€œjustā€ relative monads (i.e. given some monad F and a functor G, F āˆ˜ G is a relative monad) which is pretty cool since I havenā€™t really seen them used in real code aside from some niche Jane Street stuff.

1 Like
19

Hi! :waving_hand: Can you expand on that please? Iā€™m squinting at it but finding it hard to make them line up.

20

Oh sure. Essentially a relative monad in Haskell is a type constructor with the following operations:

-- f is a functor, but not necessarily an endofunctor
class Relative f g where
  rPure :: g a -> f a
  rBind :: (g a -> f b) -> f a -> f b

with some laws (which are essentially the same as those for regular monads):

rBind rPure = id -- left unit
rBind f . rPure = f -- right unit
rBind f . rBind g = rBind (rBind f . g) -- associativity

Every monad is a relative monad if you pick g to be Identity. But non-trivial examples include the type for well-scoped lambda terms where rBind performs parallel substitution:

type data Nat = Zero | Succ Nat

data Fin :: Nat -> Type where
  FZ :: Fin (Succ n)
  FS :: Fin n -> Fin (Succ n)

data Term :: Nat -> Type where
  Var :: Fin n -> Term n
  Lam :: Term (Succ n) -> Term n
  App :: Term n -> Term n -> Term n

as well as arrows (see page 13. of this pdf).

Additionally if we take any monad f and a functor g, Compose f g is a relative monad on g (see page 14. of this pdf):

instance Monad f => Relative (Compose f g) g where
  rPure = Compose . pure
  rBind k x = Compose (getCompose x >>= getCompose . k)

It seems like the core idea of the Applicative Wired pattern is using relative monads under the hood. Functions taking Value a and returning Action (Value b) are rPure-like and functions that use >>= for Action must return Action (Value a) to interface with the rest of the API.

Jane Streetā€™s Bonsai library uses a similar pattern to provide a nicer interface for arrows and Leo White gave a talk called ā€œArrows as applicatives in a monadā€ on the same idea.

9 Likes