{"id":777,"date":"2018-06-27T06:22:53","date_gmt":"2018-06-27T05:22:53","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=777"},"modified":"2019-08-18T21:50:00","modified_gmt":"2019-08-18T20:50:00","slug":"selective","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/selective\/","title":{"rendered":"Selective applicative functors"},"content":{"rendered":"

Update:<\/strong> I have written a paper about selective applicative functors, and it completely supersedes this blog post (it also uses a slightly different notation). You should read the paper instead<\/a>.<\/p>\n

I often need a Haskell abstraction that supports conditions (like Monad<\/span>) yet can still be statically analysed (like Applicative<\/a>). In such cases people typically point to the Arrow<\/span> class, more specifically ArrowChoice<\/span>, but when I look it up<\/a>, I find several type classes and a dozen of methods. Impressive, categorical but also quite heavy. Is there a more lightweight approach?\u00a0In this blog post I’ll explore what I call selective applicative functors<\/em>, which extend the Applicative<\/span> type class with a single method that makes it possible to be selective about effects.<\/p>\n

Please meet Selective<\/span>:<\/p>\n

class<\/span> Applicative<\/span> f<\/span> => Selective<\/span> f<\/span> where<\/span>\r\n    handle<\/span> ::<\/span> f<\/span> (Either<\/span> a<\/span> b<\/span>) -><\/span> f<\/span> (a<\/span> -><\/span> b<\/span>) -><\/span> f<\/span> b<\/span>\r\n<\/pre>\n
Think of handle<\/span> as a\u00a0selective function application<\/em>: you apply a handler function of type a\u00a0\u2192\u00a0b<\/span> when given a value of type Left a<\/span>, but can skip the handler (along with its effects) in the case of Right b<\/span>. Intuitively, handle<\/span> allows you to\u00a0efficiently<\/em>\u00a0handle errors, i.e. perform the error-handling effects only when needed.<\/p>\n
<\/p>\n
Note that you can write a function with this type signature using Applicative<\/span> functors, but it will always execute the effect associated with the handler so it’s potentially less efficient:<\/p>\n
handleA<\/span> ::<\/span> Applicative<\/span> f<\/span> =><\/span> f<\/span> (Either<\/span> a<\/span> b<\/span>) -><\/span> f<\/span> (a<\/span> -><\/span> b<\/span>) -><\/span> f<\/span> b<\/span>\r\nhandleA x f =<\/span> (\\<\/span>e f -><\/span> either f id<\/span> e) <$><\/span> x <<\/span>*><\/span> f\r\n<\/pre>\n
Selective<\/span> is more powerful(*)<\/sup><\/span> than Applicative<\/span>:\u00a0you can recover the application operator <*><\/span> as follows (I’ll use the suffix S<\/span> for Selective<\/span>).<\/p>\n
apS<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span> f<\/span> (a<\/span> -><\/span> b<\/span>) -><\/span> f<\/span> a<\/span> -><\/span> f<\/span> b<\/span>\r\napS f x =<\/span> handle (Left<\/span> <$><\/span> f) (flip<\/span> ($)<\/span> <$><\/span> x)\r\n<\/pre>\n
Here we tag a given function a \u2192 b<\/span> as an error and turn a value of type\u00a0a<\/span> into an error-handling function ($a)<\/span>, which simply applies itself to the error a \u2192 b<\/span> yielding b<\/span> as desired. We will later define laws for the Selective<\/span> type class which will ensure that apS<\/span> is a legal application operator <*><\/span>, i.e. that it satisfies the laws of the Applicative<\/span> type class.<\/p>\n
The select<\/span> function is a natural generalisation of handle<\/span>: instead of skipping one unnecessary effect, it selects which of the two given effectful functions to apply to a given value. It is possible to implement select<\/span> in terms of handle<\/span>, which is a good puzzle (try it!):<\/p>\n
select<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span>\r\n    f (Either<\/span> a b) -><\/span> f (a -><\/span> c) -><\/span> f (b -><\/span> c) -><\/span> f c\r\nselect =<\/span> ...<\/span> -- Try to figure out the implementation!<\/span>\r\n<\/pre>\n
Finally, any Monad<\/span> is Selective<\/span>:<\/p>\n
handleM<\/span> ::<\/span> Monad<\/span> f<\/span> =><\/span> f<\/span> (Either<\/span> a<\/span> b<\/span>) -><\/span> f<\/span> (a<\/span> -><\/span> b<\/span>) -><\/span> f<\/span> b<\/span>\r\nhandleM mx mf =<\/span> do<\/span>\r\n    x <-<\/span> mx\r\n    case<\/span> x of<\/span>\r\n        Left<\/span>  a -><\/span> fmap<\/span> ($<\/span>a) mf\r\n        Right<\/span> b -><\/span> pure b\r\n<\/pre>\n
Selective functors are sufficient for implementing many conditional constructs, which traditionally require the (more powerful) Monad<\/span> type class. For example:<\/p>\n
ifS<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span> f<\/span> Bool<\/span> -><\/span> f<\/span> a<\/span> -><\/span> f<\/span> a<\/span> -><\/span> f<\/span> a<\/span>\r\nifS i t e =<\/span> select\r\n    (bool (Right<\/span> ()<\/span>) (Left<\/span> ()<\/span>) <$><\/span> i) (const<\/span> <$><\/span> t) (const<\/span> <$><\/span> e)\r\n<\/pre>\n
Here we turn a Boolean value into Left ()<\/span> or Right ()<\/span> and then select<\/span> an appropriate branch. Let’s try this function in a GHCi session:<\/p>\n
\u03bb><\/span> ifS (odd<\/span> .<\/span> read<\/span> <$><\/span> getLine<\/span>) (putStrLn<\/span> \"Odd\"<\/span>) (putStrLn<\/span> \"Even\"<\/span>)\r\n0<\/span>\r\nEven<\/span>\r\n\r\n\u03bb><\/span> ifS (odd<\/span> .<\/span> read<\/span> <$><\/span> getLine<\/span>) (putStrLn<\/span> \"Odd\"<\/span>) (putStrLn<\/span> \"Even\"<\/span>)\r\n1<\/span>\r\nOdd<\/span>\r\n<\/pre>\n
As desired, only one of the two effectful functions is executed. Note that here f = IO<\/span> with the default selective instance: handle = handleM<\/span>.<\/p>\n
Using ifS<\/span> as a building block, we can implement other useful functions:<\/p>\n
-- | Conditionally apply an effect.<\/span>\r\nwhenS<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span> f<\/span> Bool<\/span> -><\/span> f<\/span> ()<\/span> -><\/span> f<\/span> ()<\/span>\r\nwhenS x act =<\/span> ifS x act (pure ()<\/span>)\r\n\r\n-- | A lifted version of lazy Boolean OR.<\/span>\r\n(<||>)<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span> f<\/span> Bool<\/span> -><\/span> f<\/span> Bool<\/span> -><\/span> f<\/span> Bool<\/span>\r\n(<||>)<\/span> a b =<\/span> ifS a (pure True<\/span>) b\r\n<\/pre>\n
See more examples in the repository<\/a>. (Note: I recently renamed handle<\/span> to select<\/span>, and select<\/span> to branch<\/span> in the repository. Apologies for the confusion.)<\/p>\n
Static analysis<\/h3>\n
Like applicative functors, selective functors can be analysed statically. As an example, consider the following useful data type Validation<\/span>:<\/p>\n
data<\/span> Validation<\/span> e a =<\/span> Failure<\/span> e |<\/span> Success<\/span> a\r\n    deriving<\/span> (Functor<\/span>, Show<\/span>)\r\n\r\ninstance<\/span> Semigroup<\/span> e<\/span> =><\/span> Applicative<\/span> (Validation<\/span> e<\/span>) where<\/span>\r\n    pure =<\/span> Success<\/span>\r\n    Failure<\/span> e1 <<\/span>*><\/span> Failure<\/span> e2 =<\/span> Failure<\/span> (e1 <><\/span> e2)\r\n    Failure<\/span> e1 <<\/span>*><\/span> Success<\/span> _  =<\/span> Failure<\/span> e1\r\n    Success<\/span> _  <<\/span>*><\/span> Failure<\/span> e2 =<\/span> Failure<\/span> e2\r\n    Success<\/span> f  <<\/span>*><\/span> Success<\/span> a  =<\/span> Success<\/span> (f a)\r\n\r\ninstance<\/span> Semigroup<\/span> e<\/span> =><\/span> Selective<\/span> (Validation<\/span> e<\/span>) where<\/span>\r\n    handle (Success<\/span> (Right<\/span> b)) _ =<\/span> Success<\/span> b\r\n    handle (Success<\/span> (Left<\/span>  a)) f =<\/span> Success<\/span> ($<\/span>a) <<\/span>*><\/span> f\r\n    handle (Failure<\/span> e        ) _ =<\/span> Failure<\/span> e\r\n<\/pre>\n
This data type is used for validating complex data: if reading one or more fields has failed, all errors are accumulated (using the operator <><\/span> from the semigroup e<\/span>)\u00a0to be reported together. By defining the Selective<\/span> instance, we can now validate data with conditions. Below we define a function to construct a Shape<\/span> (a Circle<\/span> or a Rectangle<\/span>) given a choice of the shape s :: f Bool<\/span>\u00a0and the shape’s parameters (Radius<\/span>, Width<\/span> and Height<\/span>) in an arbitrary selective context f<\/span>.<\/p>\n
type<\/span> Radius<\/span> =<\/span> Int<\/span>\r\ntype<\/span> Width<\/span>  =<\/span> Int<\/span>\r\ntype<\/span> Height<\/span> =<\/span> Int<\/span>\r\n\r\ndata<\/span> Shape<\/span> =<\/span> Circle<\/span> Radius<\/span> |<\/span> Rectangle<\/span> Width<\/span> Height<\/span> deriving<\/span> Show<\/span>\r\n\r\nshape<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span>\r\n    f Bool<\/span> -><\/span> f Radius<\/span> -><\/span> f Width<\/span> -><\/span> f Height<\/span> -><\/span> f Shape<\/span>\r\nshape s r w h =<\/span> ifS s (Circle<\/span> <$><\/span> r) (Rectangle<\/span> <$><\/span> w <<\/span>*><\/span> h)\r\n<\/pre>\n
We choose f = Validation [String]<\/span>\u00a0to report the errors that occurred when reading values. Let’s see how it works.<\/p>\n
\u03bb><\/span> shape (Success<\/span> True<\/span>) (Success<\/span> 10<\/span>)\r\n    (Failure<\/span> [\"no width\"<\/span>]) (Failure<\/span> [\"no height\"<\/span>])\r\nSuccess<\/span> (Circle<\/span> 10<\/span>)\r\n\r\n\u03bb><\/span> shape (Success<\/span> False<\/span>) (Failure<\/span> [\"no radius\"<\/span>])\r\n    (Success<\/span> 20<\/span>) (Success<\/span> 30<\/span>)\r\nSuccess<\/span> (Rectangle<\/span> 20<\/span> 30<\/span>)\r\n\r\n\u03bb><\/span> shape (Success<\/span> False<\/span>) (Failure<\/span> [\"no radius\"<\/span>])\r\n     (Success<\/span> 20<\/span>) (Failure<\/span> [\"no height\"<\/span>])\r\nFailure<\/span> [\"no height\"<\/span>]\r\n\r\n\u03bb><\/span> shape (Success<\/span> False<\/span>) (Failure<\/span> [\"no radius\"<\/span>])\r\n    (Failure<\/span> [\"no width\"<\/span>]) (Failure<\/span> [\"no height\"<\/span>])\r\nFailure<\/span> [\"no width\"<\/span>,<\/span>\"no height\"<\/span>]\r\n\r\n\u03bb><\/span> shape (Failure<\/span> [\"no choice\"<\/span>]) (Failure<\/span> [\"no radius\"<\/span>])\r\n    (Success<\/span> 20<\/span>) (Failure<\/span> [\"no height\"<\/span>])\r\nFailure<\/span> [\"no choice\"<\/span>]\r\n<\/pre>\n
In the last example, since we failed to parse which shape has been chosen, we do not report any subsequent errors. But it doesn’t mean we are short-circuiting the validation. We will continue accumulating errors as soon as we get out of the opaque conditional:<\/p>\n
twoShapes<\/span> ::<\/span> Selective<\/span> f<\/span> =><\/span> f<\/span> Shape<\/span> -><\/span> f<\/span> Shape<\/span> -><\/span> f<\/span> (Shape<\/span>, Shape<\/span>)\r\ntwoShapes s1 s2 =<\/span> (,)<\/span> <$><\/span> s1 <<\/span>*><\/span> s2\r\n\r\n\u03bb><\/span> s1 =<\/span> shape (Failure<\/span> [\"no choice 1\"<\/span>]) (Failure<\/span> [\"no radius 1\"<\/span>])\r\n    (Success<\/span> 20<\/span>) (Failure<\/span> [\"no height 1\"<\/span>])\r\n\u03bb><\/span> s2 =<\/span> shape (Success<\/span> False<\/span>) (Failure<\/span> [\"no radius 2\"<\/span>])\r\n    (Success<\/span> 20<\/span>) (Failure<\/span> [\"no height 2\"<\/span>])\r\n\u03bb><\/span> twoShapes s1 s2\r\nFailure<\/span> [\"no choice 1\"<\/span>,<\/span>\"no height 2\"<\/span>]\r\n<\/pre>\n
Another example of static analysis of selective functors is the Task<\/span> abstraction from\u00a0the previous blog post<\/a>.<\/p>\n
instance<\/span> Monoid<\/span> m<\/span> =><\/span> Selective<\/span> (Const<\/span> m<\/span>) where<\/span>\r\n    handle =<\/span> handleA\r\n\r\ntype<\/span> Task<\/span> c k v =<\/span> forall f.<\/span> c f =><\/span> (k -><\/span> f v) -><\/span> k -><\/span> Maybe<\/span> (f v)\r\n\r\ndependencies<\/span> ::<\/span> Task<\/span> Selective<\/span> k<\/span> v<\/span> -><\/span> k<\/span> -><\/span> [k<\/span>]\r\ndependencies task key =<\/span> case<\/span> task (\\<\/span>k -><\/span> Const<\/span> [k]) key of<\/span>\r\n                            Nothing<\/span>         -><\/span> []<\/span>\r\n                            Just<\/span> (Const<\/span> ks) -><\/span> ks\r\n<\/pre>\n
The definition of the Selective<\/span> instance for the Const<\/span> functor simply falls back to the applicative handleA<\/span>, which allows us to extract the static structure of any selective computation very similarly to how this is done with applicative computations. In particular, the function dependencies<\/span> returns an approximation of dependencies of a given key: instead of ignoring opaque conditional statements as in Validation<\/span>, we choose to inspect both<\/em> branches collecting dependencies from both of them.<\/p>\n
Here is an example from the Task<\/span>\u00a0blog post<\/a>, where we used the\u00a0Monad<\/span> abstraction to express a spreadsheet with two formulas:\u00a0B1 = IF(C1=1,B2,A2)<\/span> and\u00a0B2 = IF(C1=1,A1,B1)<\/span>.<\/p>\n
task<\/span> ::<\/span> Task<\/span> Monad<\/span> String<\/span> Integer<\/span>\r\ntask fetch \"B1\"<\/span> =<\/span> Just<\/span> $<\/span> do<\/span> c1 <-<\/span> fetch \"C1\"<\/span>\r\n                            if<\/span> c1 ==<\/span> 1<\/span> then<\/span> fetch \"B2\"<\/span>\r\n                                       else<\/span> fetch \"A2\"<\/span>\r\ntask fetch \"B2\"<\/span> =<\/span> Just<\/span> $<\/span> do<\/span> c1 <-<\/span> fetch \"C1\"<\/span>\r\n                            if<\/span> c1 ==<\/span> 1<\/span> then<\/span> fetch \"A1\"<\/span>\r\n                                       else<\/span> fetch \"B1\"<\/span>\r\ntask _     _    =<\/span> Nothing<\/span>\r\n<\/pre>\n
Since this task<\/span> description is monadic we could not analyse it statically. But now we can! All we need to do is rewrite it using Selective<\/span>:<\/p>\n
task<\/span> ::<\/span> Task<\/span> Selective<\/span> String<\/span> Integer<\/span>\r\ntask fetch \"B1\"<\/span> =<\/span> Just<\/span> $<\/span>\r\n    ifS ((1<\/span>==<\/span>) <$><\/span> fetch \"C1\"<\/span>) (fetch \"B2\"<\/span>) (fetch \"A2\"<\/span>)\r\ntask fetch \"B2\"<\/span> =<\/span> Just<\/span> $<\/span>\r\n    ifS ((1<\/span>==<\/span>) <$><\/span> fetch \"C1\"<\/span>) (fetch \"A1\"<\/span>) (fetch \"B1\"<\/span>)\r\ntask _     _    =<\/span> Nothing<\/span>\r\n<\/pre>\n
We can now apply the function dependencies<\/span> defined above and draw the dependency graph using your favourite graph\u00a0library<\/a>:<\/p>\n
\u03bb><\/span> dependencies task \"B1\"<\/span>\r\n[\"A2\"<\/span>,<\/span>\"B2\"<\/span>,<\/span>\"C1\"<\/span>]\r\n\u03bb><\/span> dependencies task \"B2\"<\/span>\r\n[\"A1\"<\/span>,<\/span>\"B1\"<\/span>,<\/span>\"C1\"<\/span>]\r\n\u03bb><\/span> dependencies task \"A1\"<\/span>\r\n[]<\/span>\r\n\r\n\u03bb><\/span> writeFile<\/span> \"task.dot\"<\/span> $<\/span> exportAsIs $<\/span> graph (dependencies task) \"B1\"<\/span>\r\n\u03bb><\/span> :!<\/span> dot -<\/span>Tsvg<\/span> task.<\/span>dot -<\/span>o task.<\/span>svg\r\n<\/pre>\n
This produces the graph below, which matches the one<\/a> I had to draw manually last time, since I had no Selective<\/span> to help me.<\/p>\n
\"Static<\/a><\/p>\n
Laws<\/h3>\n
Instances of the Selective<\/span> type class must satisfy a few laws to make it possible to refactor selective computations. These laws also allow us to establish a formal relation with the Applicative<\/span> and Monad<\/span> type classes. The laws are complex, but I couldn’t figure out how to simplify them. Please let me know if you find an improvement.<\/p>\n