#+TITLE: Programming with Applicative-like expressions
#+AUTHOR: Jan Malakhovski and Sergei Soloviev
#+EMAIL: papers@oxij.org
#+EMAIL-COMMENT: preferably with paper title in the subject line
#+AFFIL: IRIT, University of Toulouse-3 and ITMO University
#+DATE: 2015 - 2019
#+KEYWORDS: applicative functors, algebraic data types, metaprogramming, stack machines, logic, category theory
#+BEGIN_abstract
The fact that src_haskell{Applicative} type class allows one to express simple parsers in a variable-less combinatorial style is well appreciated among Haskell programmers for its conceptual simplicity, ease of use, and usefulness for semi-automated code generation (metaprogramming).
We notice that such src_haskell{Applicative} computations can be interpreted as providing a /mechanism/ to construct a data type with "ports" "pluggable" by subcomputations.
We observe that it is this property that makes them so much more convenient in practice than the usual way of building the same computations using conventional composition.
We distill this observation into a more general algebraic structure of (and/or technique for expressing) "src_haskell{Applicative}-like" computations and demonstrate several other instances of this structure.
Our interest in all of this comes from the fact that the aforementioned instances allow us to express arbitrary transformations between simple data types of a single constructor (similarly to how src_haskell{Applicative} parsing allows to transform from streams of src_haskell{Char}s to such data types) using a style that closely follows conventional src_haskell{Applicative} computations, thus greatly simplifying (if not completely automating away) a lot of boiler-plate code present in many functional programs.
#+END_abstract
@@tex:\small\tableofcontents\normalsize@@
#+BEGIN_SRC haskell :tangle TngTypes.hs :exports none
{-# LANGUAGE StandaloneDeriving #-}
module TngTypes where
#+END_SRC
#+BEGIN_SRC haskell :tangle TngMain.hs :exports none
module TngMain where
import Data.Monoid
import Data.List (foldl', intersperse)
-- import Data.ByteString (ByteString)
import TngTypes
#+END_SRC
#+BEGIN_SRC haskell :tangle TngMainGeneric.hs :exports none
{-# LANGUAGE RankNTypes, TypeFamilies, AllowAmbiguousTypes, MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies, TypeSynonymInstances #-}
import TngTypes
import TngMain
#+END_SRC
#+BEGIN_SRC haskell :tangle TngSafeCopyFake.hs :exports none
import Data.SafeCopy
import TngTypes
#+END_SRC
#+BEGIN_SRC haskell :tangle TngAeson.hs :exports none
{-# LANGUAGE OverloadedStrings #-}
import Data.Aeson hiding (FromJSON, ToJSON)
import Data.Aeson.Types (Parser)
import Control.Applicative (empty)
import TngTypes
#+END_SRC
#+BEGIN_SRC haskell :tangle TngMisc.hs :exports none
import Control.Arrow (Arrow)
import TngTypes
#+END_SRC
* Preliminaries
This paper describes an algebraic structure (and/or a technique) for expressing certain kinds of computations.
The presented derivation of said structure (technique) starts from observing Haskell's src_haskell{Applicative} type class~\cite{mcbride-paterson-08} and then generalizing it.
The result, however, is language-agnostic (the same way src_haskell{Applicative} is, as both structures can be applied to most functional programming languages in some shape or form, even if a language in question can not explicitly express required type signatures) and theoretically interesting (as it points to several curious connections to category theory and logic).
Since the idea grows from Haskell and most related literature uses Haskell, it is natural to express the derivation of the structure (technique) in Haskell.
Therefore, this paper is organized as a series of Literate Haskell programs in a single Emacs Org-Mode tree~\cite{OrgMode, Schulte:2011:MLCELPRR} (then, most likely, compiled into the representation you are looking at right now).[fn::
@@tex:\label{fn:source}@@ The source code is available at [[https://oxij.org/paper/ApplicativeLike/]].
@@tex:\ifnum 0\ifpdf 1\fi\ifxetex 1\fi\ifluatex 1\fi=0@@
It also gets embedded straight into the PDF version of the article when compiled with a modern \TeX engine.
Unfortunately, the file you are looking at was compiled using =dvipdf=.
Properly compiled version is available via the above link.
@@tex:\else
It is also embedded straight into the PDF version of this article (click here \attachfile{article.org} or look for "attachments" in
your PDF viewer).
\fi@@
All runnable code in the paper was tested with GHC~\cite{GHC} version 8.6.]
Moreover, for uniformity reasons we shall also use Haskell type class names for the names of the corresponding algebraic structures where appropriate (e.g. "src_haskell{Applicative}" instead of "applicative functor") as not to cause any confusion between the code and the rest of the text.
# The tangled sources can be extracted via
# $ emacs --batch --eval "(progn (require 'ob-tangle) (org-babel-tangle-file \"article.org\"))"
# or by openining this file in Emacs and running `M-x org-babel-tangle`.
* Introduction
Let us recall the definition of src_haskell{Applicative} type class~\cite{mcbride-paterson-08} as it is currently defined in the =base=~\cite{Hackage:base4900} package of Hackage~\cite{Hackage}
#+BEGIN_SRC haskell-spec
infixl 4 <*>
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
#+END_SRC
One can think of the above definition as simply providing a generic "constant injector" src_haskell{pure} and a somewhat generic "function application" src_haskell{(<*>)} operator.
(The referenced src_haskell{Functor} type class and any related algebraic laws can be completely ignored for the purposes of this article.)
For instance, an identity on Haskell types is obviously an src_haskell{Applicative} with src_haskell{pure = id} and src_haskell{(<*>)} being the conventional function application (the one that is usually denoted by simple juxtaposition of terms), but there are many more complex instances of this type class (see~\cite{HaskellWiki:Typeclassopedia, Malakhovski:2018:EME} for comprehensive overviews of this and related algebraic structures), most (for the purposes of this article) notably, including src_haskell{Applicative} parsing combinators.
Those are very popular in practice as they simplify parsing of simple data types ("simple" in this context means "without any type or data dependencies between different parts") to the point of triviality.
For instance, given appropriate src_haskell{Applicative} parsing machinery like Parsec~\cite{Hackage:parsec3111}, Attoparsec~\cite{Hackage:attoparsec01310} or Megaparsec~\cite{Hackage:megaparsec630} one can parse a simple data type like
#+BEGIN_SRC haskell :tangle TngTypes.hs
data Device = Device
{ block :: Bool
, major :: Int
, minor :: Int }
exampleDevice :: Device
exampleDevice = Device False 19 1
#+END_SRC
#+BEGIN_SRC haskell :tangle TngTypes.hs :exports none
deriving instance Show Device
#+END_SRC
\noindent from a straightforward serialized representation with just
#+BEGIN_SRC haskell-spec
class Parsable a where
parse :: Parser a
instance Parsable Device where
parse = pure Device <*> parse <*> parse <*> parse
#+END_SRC
While clearly limited to simple data types of a single[fn::Two or more constructors can be handled with the help of src_haskell{Alternative} type class and some tagging of choices, but that is out of scope of this article.] constructor, this approach is very useful in practice.
Firstly, since these kinds of expressions make no variable bindings and all they do is repeatedly apply src_haskell{parse} it is virtually impossible to make a mistake.
Secondly, for the same reason it is exceptionally easy to generate such expressions via Template Haskell and similar metaprogramming mechanisms.
Which is why a plethora of Hackage libraries use this approach.
In this paper we shall demonstrate a surprisingly simple technique that can be used to make computations expressing arbitrary transformations between simple data types of a single constructor while keeping the general form of src_haskell{Applicative} expressions as they were shown above.
Since we design our expressions to look similar to those produced with the help of src_haskell{Applicative} type class but the underlying structure is not src_haskell{Applicative} we shall call them "src_haskell{Applicative}-like".
\Cref{sec:examples} provides some motivating examples that show why we want to use src_haskell{Applicative}-like computations to express transformations between data types.
\Cref{sec:definition} formalizes the notion of "src_haskell{Applicative}-like" and discusses the properties we expect from such expressions.
\Cref{sec:deriving-the-technique} derives one particular structure for one of the motivating examples using LISP-encoding for deconstructing data types.
\Cref{sec:implementation} proceeds to derive the rest of motivating examples by applying the same idea, thus showing that \cref{sec:deriving-the-technique} describes a technique, not an isolated example.
\Cref{sec:implementation} ends by demonstrating the total expressive power of the technique.
\Cref{sec:scott} repeats the derivation and the implementations for Scott-encoded data types.
\Cref{sec:general-case} observes the general structure behind all of the terms used in the paper.
\Cref{sec:formally} gives a formal description of the technique and the underlying general algebraic structure.
\Cref{sec:conclusion} refers to related work and wraps everything up.
* Motivating examples
@@tex:\label{sec:examples}@@
Consider the following expressions produced with the help of first author's favorite =safecopy=~\cite{Hackage:safecopy0943} data-type-to-binary serialization-deserialization library which can be used to deserialize-serialize src_haskell{Device} with the following code snippet (simplified[fn::The actual working code for the actual library looks a bit more complex, but the =safecopy= library also provides Template Haskell functions that derive these src_haskell{SafeCopy} instances automatically, so, in practice, one would not need to write this code by hand in any case.])
#+BEGIN_SRC haskell :tangle TngSafeCopyFake.hs
instance SafeCopy Device where
getCopy = pure Device <*> getCopy <*> getCopy <*> getCopy
putCopy (Device b x y) = putCopy b >> putCopy x >> putCopy y
#+END_SRC
Note that while src_haskell{getCopy} definition above is trivial, src_haskell{putCopy} definition binds variables.
Would not it be better if we had an src_haskell{Applicative}-like machinery with which we could rewrite src_haskell{putCopy} into something like
#+BEGIN_SRC haskell-spec
putCopy = depure unDevice <**> putCopy <**> putCopy <**> putCopy
#+END_SRC
\noindent which, incidentally, would also allow us to generate both functions from a single expression?
This idea does not feel like a big stretch of imagination for several reasons:
- there are libraries that can do both parsing and pretty printing using a single expression, e.g.~\cite{Hackage:syntax1000},
- the general pattern of src_haskell{putCopy} feels very similar to computations in src_haskell{(->) a} (the type of "functions from src_haskell{a}") as it, too, is a kind of computation in a context with a constant value, aka src_haskell{Reader} src_haskell{Monad}~\cite{Hackage:transformers0520}, which is an instance of src_haskell{Applicative}.[fn::@@tex:\label{fn:function-reader}@@We shall utilize this fact in the following sections.]
Another example is the data-type-to-JSON-to-strings serialization-deserialization part of =aeson=~\cite{Hackage:aeson1420} library which gives the following class signatures to its deserializer and serializer from/to JSON respectively.
#+BEGIN_SRC haskell :tangle TngAeson.hs
class FromJSON a where
parseJSON :: Value -> Parser a
class ToJSON a where
toJSON :: a -> Value
#+END_SRC
In the above, src_haskell{Value} is a JSON value and src_haskell{Parser a} is a Scott-transformed variation of src_haskell{Either ErrorMessage a}.
Assuming src_haskell{(.:)} to be a syntax sugar for src_haskell{lookup}-in-a-map-by-name function and src_haskell{(.=)} a pair constructor, we can give the following instances for the src_haskell{Device} data type by emulating examples given in the package's own documentation
#+BEGIN_SRC haskell :tangle TngAeson.hs
instance FromJSON Device where
parseJSON (Object v) = pure Device
<*> v .: "block"
<*> v .: "major"
<*> v .: "minor"
parseJSON _ = empty
instance ToJSON Device where
toJSON (Device b x y) = object
[ "block" .= b
, "major" .= x
, "minor" .= y ]
#+END_SRC
Note that here, again, we have to bind variables in src_haskell{toJSON}.
Moreover, note that in this example even src_haskell{parseJSON} underuses the src_haskell{Applicative} structure by ignoring the fact that src_haskell{Value} can be packed into src_haskell{Parser} by making the latter into a src_haskell{Reader}.[fn::As noted under footnote~\ref{fn:function-reader} and demonstrated in detail in \cref{sec:deriving-the-technique}. However, this underuse has a reasonable explanation for =aeson=: src_haskell{Value}'s definition is /too structured/ to have a conventional parser combinator library that can make this trick work in the general case (i.e. not just in the above example).
This problem can be solved using indexed src_haskell{Monad}ic parser combinators but that is out of scope of this article.]
Other serialization-deserialization problems, e.g. conventional pretty-printing with the standard src_haskell{Show} type class~\cite{Hackage:base4900} are, of course, the instances of the same pattern, as we shall demonstrate in the following sections.
Finally, as a bit more involved example, imagine an application that benchmarks some other software applications on given inputs, records logs they produce and then computes per-application averages
#+BEGIN_SRC haskell :tangle TngTypes.hs
data Benchmark a = Benchmark
{ firstApp :: a
, firstLog :: String
, secondApp :: a
, secondLog :: String
}
type Argv = [String]
type Inputs = Benchmark Argv
type Outputs = Benchmark Integer
type Avgs = Benchmark Double
#+END_SRC
#+BEGIN_SRC haskell :tangle TngMain.hs
benchmark :: Inputs -> IO Outputs
average :: [ Outputs ] -> Avgs
#+END_SRC
#+BEGIN_SRC haskell :tangle TngMain.hs :exports none
benchmark = undefined
#+END_SRC
Assuming that we have aforementioned machinery for src_haskell{SafeCopy} we can trivially autogenerate all of the needed glue code to deserialize src_haskell{Inputs}, serialize src_haskell{Outputs} and src_haskell{Avgs}.
The src_haskell{benchmark} is the core of our application, so let us assume that it is not trivial to autogenerate and we have to write it by hand.
We are now left with the "src_haskell{average}" function.
Let us assume that for the numeric parts of the src_haskell{Outputs} type it is just a src_haskell{fold} with point-wise sum over the list of src_haskell{Outputs} followed by a point-wise divide by their src_haskell{length} and for the src_haskell{String} parts it simply point-wise concatenates all the logs.
Now, do we really want to write those binary operators completely by hand?
Note that this src_haskell{Benchmark} example was carefully crafted: it is not self- or mutually-recursive and, at the same time, it is also not particularly homogeneous as different fields require different operations.
In other words, things like SYB~\cite{Laemmel:2003:SYB}, Uniplate~\cite{Mitchell:2007:Uniplate}, Multiplate~\cite{Hackage:multiplate003} or Lenses~\cite{Kmett:Lens, Hackage:lens417} are not particularly useful in this case.[fn::Strictly speaking, both operations used in the "sum" part of "src_haskell{average}" are src_haskell{Monoid} operators, so generalized src_haskell{zip}s provided by some of the mentioned libraries can be used to implement that part, but the "divide" part is not so homogeneous.]
Of course, in this particular example, it is possible to distill the computation pattern into something like
#+BEGIN_SRC haskell :tangle TngMain.hs
lift2B :: (a -> b -> c) -> (Benchmark a -> Benchmark b -> Benchmark c)
lift2B f (Benchmark a1 l1 a2 l2) (Benchmark b1 l3 b2 l4)
= Benchmark (f a1 b1) (l1 ++ l3) (f a2 b2) (l2 ++ l4)
#+END_SRC
\noindent and then use src_haskell{lift2B} to implement both functions (with some unsightly hackery for the division part), but would not it be even better if instead we had an src_haskell{Applicative}-like machinery that would allow us to write the src_haskell{average} function directly, such as
#+BEGIN_SRC haskell :tangle TngMain.hs
average ls = runMap $ bdivide folded where
len = fromIntegral $ length ls
avg = ((/ len) . fromIntegral)
bappend = depureZip Benchmark unBenchmark unBenchmark
`zipa` (+) `zipa` (++)
`zipa` (+) `zipa` (++)
folded = foldl' (\a b -> runZip $ bappend a b)
(Benchmark 0 "" 0 "") ls
bdivide = depureMap Benchmark unBenchmark
`mapa` avg `mapa` id
`mapa` avg `mapa` id
#+END_SRC
\noindent similarly to how we would solve similar problems over homogeneous lists?
* Problem definition
@@tex:\label{sec:definition}@@
Before going into derivation of the actual implementation let us describe what we mean by "src_haskell{Applicative}-like" more precisely.
Note that the type of src_haskell{(<*>)} operator of src_haskell{Applicative}
#+BEGIN_SRC haskell-spec
(<*>) :: f (a -> b) -> f a -> f b
#+END_SRC
\noindent at least in the context of constructing data types (of which src_haskell{Applicative} parsers are a prime example), can be generalized and reinterpreted as
#+BEGIN_SRC haskell-spec
plug :: f full -> g piece -> f fullWithoutThePiece
#+END_SRC
\noindent where
- src_haskell{f full} is a computation that /provides a mechanism/ to handle the src_haskell{full} structure,
- src_haskell{g piece} is another kind of computation that /actually handles/ a src_haskell{piece} of the src_haskell{full} structure (src_haskell{g == f} for src_haskell{Applicative} parsers, of course),
- and src_haskell{f fullWithoutThePiece} is a computation that provided a mechanism to handle the leftover part.
Note that this interpretation, in some sense, reverses conventional wisdom on how such transformations are usually expressed.
For instance, conventionally, to parse (pretty-print, etc) some structure one first makes up computations that handle src_haskell{piece}s and then composes them into a computation that handles the src_haskell{full} structure, i.e.
#+BEGIN_SRC haskell-spec
compose :: f fullWithoutThePiece -> g piece -> f full
-- or
compose' :: g piece -> f fullWithoutThePiece -> f full
#+END_SRC
Meanwhile, src_haskell{Applicative}-like expressions, in some sense, work backwards: they provide up a mechanism to handle (parse, pretty-print, etc) the src_haskell{full} structure that exposes "ports" that subcomputations src_haskell{plug} with computations that handle different src_haskell{piece}s.
#+BEGIN_remark
It is rather interesting to think about the conventional function application in these terms: it describes a way to make a computation that produces src_haskell{b} given a mechanism to construct a partial version of src_haskell{b} denoted as src_haskell{a -> b} by plugging its only port with a computation that produces src_haskell{a}.
In other words, this outlook is a reminder that functions can be seen as goals, the same way Haskell's type class instance inference (or Prolog) does.
Moreover, note that while such a description sounds obvious for a lazy language, it is also a reminder that, in general, there is a distinction between values and computations.
#+END_remark
To summarize, the crucial part of src_haskell{Applicative}-like computations is the fact that they compose subcomputations in reverse order w.r.t. the types they handle.
This reversal is the cornerstone that provides three important properties:
- A sequence of subcomputations in an expression matches the sequence of parts in the corresponding data type.
- A top-level computation can decide on all data types /first/ and then delegate handing of parts to subcomputations without worrying about reassembling their results (which is why we say it "provides a mechanism" that subcomputations use).
- As a consequence, in the presence of type inference, a mechanism for ad-hoc polymorphism (be it type classes, like in Haskell, or something else) can be used to automatically select implementations matching corresponding src_haskell{piece}s.
It is the combination of these three properties that makes src_haskell{Applicative}-like expressions (including src_haskell{Applicative} parsers) so convenient in practice.
* Deriving the technique
@@tex:\label{sec:deriving-the-technique}@@
We shall now demonstrate the derivation of the main technique of the paper.
Before we start, let us encode reverses to src_haskell{Device} and src_haskell{Benchmark} constructors (i.e. "destructors") using the LISP-encoding (see below for motivation, an alternative approach using Scott-encoding is discussed in section~\ref{sec:scott}).
#+BEGIN_SRC haskell :tangle TngTypes.hs
unDeviceLISP :: Device -> (Bool, (Int, (Int, ())))
unDeviceLISP (Device b x y) = (b, (x, (y, ())))
unBenchmarkLISP :: Benchmark a -> (a, (String, (a, (String, ()))))
unBenchmarkLISP (Benchmark a b c d) = (a, (b, (c, (d, ()))))
#+END_SRC
Now, let us start by deriving an src_haskell{Applicative}-like pretty-printer for src_haskell{Device}.
The target expression is as follows
#+BEGIN_SRC haskell :tangle TngMain.hs
showDevice = depureShow unDeviceLISP `showa` show
`showa` show
`showa` show
#+END_SRC
Remember that the type pattern for the src_haskell{plug} operator from the previous section
#+BEGIN_SRC haskell-spec
plug :: f full -> g piece -> f fullWithoutThePiece
#+END_SRC
\noindent already prescribes a certain way of implementing the missing operators.
Firstly, if we follow the logic for parsing, the src_haskell{f} type-level function should construct a type that contains some internal state.
Secondly, the rest of the expression clearly requires src_haskell{depureShow} to generate the initial state and src_haskell{showa} to transform the internal state while chopping away at the parts of the src_haskell{Device}.
Let us simplify the task of deriving these functions by writing out the desired type and making src_haskell{Device} argument explicit.
Let us also apply the result of the whole computation to src_haskell{runShow} function to lift the restriction on the return type.
#+BEGIN_SRC haskell :tangle TngMain.hs
showDevice' :: Device -> String
showDevice' d = runShow $ depureShow' (unDeviceLISP d) `showa'` show
`showa'` show
`showa'` show
#+END_SRC
What should be the type of src_haskell{showa'}? Clearly, something like
#+BEGIN_SRC haskell-spec
showa' :: (s, (a, b)) -> (a -> String) -> (s, b)
#+END_SRC
\noindent should work and match the type pattern of src_haskell{plug}.
The src_haskell{a -> String} part follows from the expression itself, the src_haskell{(_ , (a, b))} and src_haskell{(_ , b)} parts come from chopping away at LISP-encoded deconstructed data type, and src_haskell{s} plays the role of the internal pretty-printing state.
We just need to decide on the value of src_haskell{s}.
The most simple option seems to be to the list of src_haskell{String}s that is to be concatenated in src_haskell{runShow}.
The rest of the code pretty much writes itself:
#+BEGIN_SRC haskell :tangle TngMain.hs
depureShow' :: a -> ([String], a)
depureShow' a = ([], a)
showa' :: ([String], (a, b)) -> (a -> String) -> ([String], b)
showa' (s, (a, b)) f = ((f a):s, b)
runShow :: ([String], b) -> String
runShow = concat . intersperse " " . reverse . fst
testShowDevice' :: String
testShowDevice' = showDevice' exampleDevice
#+END_SRC
Now, note that src_haskell{showa'} is actually a particular case of the more generic operator
#+BEGIN_SRC haskell :tangle TngMain.hs
chop :: (s, (a, b)) -> (s -> a -> t) -> (t, b)
chop (s, (a, b)) f = (f s a, b)
showa'' s f = chop s (\s a -> (f a):s) -- == showa'
#+END_SRC
Moreover, src_haskell{f} parts of that operator can be wrapped into the src_haskell{(->) r} src_haskell{Reader} (see under footnote~\ref{fn:function-reader})
#+BEGIN_SRC haskell :tangle TngMain.hs
chopR :: (r -> (s, (a, b))) -> (s -> a -> t) -> (r -> (t, b))
chopR o f r = chop (o r) f
#+END_SRC
\noindent thus allowing us to complete the original
src_haskell{showDevice}
#+BEGIN_SRC haskell :tangle TngMain.hs
showDevice :: Device -> ([String], ())
depureShow :: (t -> b) -> t -> ([String], b)
depureShow f r = ([], f r)
showa :: (r -> ([String], (a, b)))
-> (a -> String)
-> (r -> ([String], b))
showa st f = chopR st (\s a -> (f a):s)
testShowDevice :: String
testShowDevice = runShow $ showDevice exampleDevice
#+END_SRC
Note that the use of the LISP-encoding (i.e. the src_haskell{()} in the tails of the deconstructed types and, hence, the use of src_haskell{fst} in src_haskell{runShow}) as opposed to using simple stacked tuples is needed to prevent special case handling for the last argument.
Also note that the type of the second argument to src_haskell{chopR} in the definition of src_haskell{showa} is src_haskell{[String] -> a -> [String]} which is src_haskell{CoState} on a list of src_haskell{String}s.
This makes a lot of sense categorically since src_haskell{Parser} is a kind of src_haskell{State} and parsing and pretty-printing are dual.
Moreover, even the fact that src_haskell{String} is wrapped into a list makes sense if one is to note that the above pretty-printer produces /lexemes/ instead of directly producing the output string.
The above transformation from src_haskell{chop} to src_haskell{chopR} will be a common theme in the following sections, so let us distill it into a separate operator with a very self-descriptive type
#+BEGIN_SRC haskell :tangle TngMain.hs
homWrap :: (s -> a -> t)
-> (r -> s) -> a -> (r -> t)
homWrap chopper o f r = chopper (o r) f
showa''' = homWrap $ \st f -> chop st $ \s a -> (f a):s -- == showa
#+END_SRC
* Applying the technique
@@tex:\label{sec:implementation}@@
Turning attention back to src_haskell{chop} operator, note that both types in the state tuple can be arbitrary.
For instance, src_haskell{s} can be a curried data type constructor, which immediately allows to express an src_haskell{Applicative}-like step-by-step equivalent of src_haskell{map}.
#+BEGIN_SRC haskell :tangle TngMain.hs
mapa :: (r -> (x -> y, (a, b)))
-> (a -> x)
-> (r -> (y, b))
mapa = homWrap $ \st f -> chop st $ \s a -> s (f a)
depureMap :: a -> (t -> b) -> t -> (a, b)
depureMap c f r = (c, f r)
runMap = fst
mapDevice :: Device -> (Device, ())
mapDevice = depureMap Device unDeviceLISP
`mapa` not
`mapa` (+ 100)
`mapa` (+ 200)
testMapDevice :: Device
testMapDevice = runMap $ mapDevice exampleDevice
#+END_SRC
Moreover, by extending src_haskell{chop} with two LISP-encoded representations and repeating the whole derivation we can express an equivalent of src_haskell{zip}.
#+BEGIN_SRC haskell :tangle TngMain.hs
chop2 :: (s, (a, b), (c, d))
-> (s -> a -> c -> t)
-> (t, b, d)
chop2 (s, (a, b), (c, d)) f = (f s a c, b, d)
homWrap2 chopper o f ra rb = chopper (o ra rb) f
zipa :: (ra -> rb -> (x -> y, (a, b), (c, d)))
-> (a -> c -> x)
-> (ra -> rb -> (y, b, d))
zipa = homWrap2 $ \st f -> chop2 st $ \s a b -> s (f a b)
depureZip :: a -> (ra -> b) -> (rb -> c)
-> ra -> rb
-> (a, b, c)
depureZip c f g ra rb = (c, f ra, g rb)
runZip :: (s, a, b) -> s
runZip (s, _, _) = s
zipDevice :: Device -> Device -> (Device, (), ())
zipDevice = depureZip Device unDeviceLISP unDeviceLISP
`zipa` (&&)
`zipa` (+)
`zipa` (+)
testZipDevice :: Device
testZipDevice = runZip $ zipDevice exampleDevice testMapDevice
#+END_SRC
The above transformations combined with
#+BEGIN_SRC haskell :tangle TngTypes.hs
unDevice = unDeviceLISP
unBenchmark = unBenchmarkLISP
#+END_SRC
\noindent implement all the examples from \cref{sec:examples}, thus solving the problem as it was originally described.
Note, however, that the above technique can be trivially extended to src_haskell{chop}ping any number of data types at the same time and, moreover, that it is not actually required to match types or even the numbers of arguments of different constructors and destructors used by the desired transformations.
For instance, it is trivial to implement the usual stack machine operators, e.g.
#+BEGIN_SRC haskell :tangle TngMain.hs
homWrap0 :: (s -> t)
-> (r -> s) -> (r -> t)
homWrap0 chopper o r = chopper (o r)
-- syntax sugar
andThen x f = f x
pop :: (r -> (s, (a, b)))
-> (r -> (s, b))
pop = homWrap0 $ \(s, (_, b)) -> (s, b)
push = homWrap $ \(s, b) a -> (s, (a, b))
dup = homWrap0 $ \(s, (a, b)) -> (s, (a, (a, b)))
#+END_SRC
\noindent and use them to express some mapping function between data types as if Haskell was a stack machine language
#+BEGIN_SRC haskell :tangle TngMain.hs
remapDevice :: Device -> (Device, ())
remapDevice = depureMap Device unDeviceLISP
`andThen` pop
`push` True
`mapa` id
`andThen` pop
`andThen` dup
`mapa` id
`mapa` id
testRemapDevice :: Device
testRemapDevice = runMap $ remapDevice exampleDevice
#+END_SRC
In other words, in general, one can view src_haskell{Applicative}-like computations as computations for generalized multi-stack machines with arbitrary data types and/or functions as "stacks".
In practice, though, simple direct transformations in the style of src_haskell{Applicative} parsers seem to be the most useful to us.
* Scott-encoded representation
@@tex:\label{sec:scott}@@
The LISP-encoding used above is not the only generic representation for data types, in this section we shall explore the use of Scott-encoding.
Before we start, let us note that while it is trivial to simply Scott-encode all the pair constructors and destructors in the above transformations to get more complicated terms with exactly equivalent semantics~\cite{Malakhovski:2018:EME}, it just complicates things structurally, and we shall not explore that route.
The interesting question is whether it is possible to remake the above machinery directly for Scott-encoded representations of the subject data types
#+BEGIN_SRC haskell :tangle TngTypes.hs
unDeviceScott :: Device -> (Bool -> Int -> Int -> c) -> c
unDeviceScott (Device b x y) f = f b x y
unBenchmarkScott :: Benchmark a
-> (a -> String -> a -> String -> c) -> c
unBenchmarkScott (Benchmark a b c d) f = f a b c d
#+END_SRC
\noindent without reaching for anything else. In other words, would not it be nice if we could work with a Scott-encoded data type
src_haskell{(a -> b -> c -> ... -> z) -> z}
as if it was a heterogeneous list of typed values like LISP-encoding is?
Let us start by noticing that we can, in fact, prepend values to Scott-encoded representations as if they were heterogeneous lists or tuples
#+BEGIN_SRC haskell :tangle TngMain.hs
consS :: s
-> (a -> b)
-> ((s -> a) -> b)
consS s ab sa = ab (sa s)
#+END_SRC
To see why this prepends src_haskell{s} to a Scott-encoded src_haskell{a -> b} substitute, for instance, src_haskell{x -> y -> b} for src_haskell{a}.
Note, however, that there are some important differences.
For instance, Scott-encoded data types, unlike LISP-encoded ones, can not have a generic src_haskell{unconsS}
#+BEGIN_SRC haskell :tangle TngMainBroken.hs
unconsS :: ((s -> a) -> b) -> (s, a -> b)
unconsS f = (_, _)
#+END_SRC
\noindent as, in general, all the pieces of a Scott-encoded data type have to be used all at once.
This makes most of our previous derivations unusable.
However, very surprisingly, src_haskell{consS} seems to be enough.
By prepending src_haskell{s} to the Scott-encoded data type we can emulate pretty-printing code above as follows.[fn::We tried our best to make this comprehensible by making the types speak for themselves but, arguably, this and the following listings can only be really understood by playing with the Literate Haskell version in =ghci=.]
#+BEGIN_SRC haskell :tangle TngMain.hs
chopS :: ((s -> a -> b) -> c)
-> (s -> a -> t)
-> ((t -> b) -> c)
chopS i f o = i $ \s a -> o (f s a)
depureShowS f r = consS [] (f r)
showaS :: (r -> ([String] -> a -> b) -> c)
-> (a -> String)
-> (r -> ([String] -> b) -> c)
showaS = homWrap $ \st f -> chopS st $ \s a -> (f a):s
runShowS = concat . intersperse " " . reverse . (\f -> f id)
showDeviceS = depureShowS unDeviceScott
`showaS` show
`showaS` show
`showaS` show
testShowDeviceS = runShowS $ showDeviceS exampleDevice
#+END_SRC
The only new parts here are the implementation of src_haskell{chopS} function, the use of src_haskell{consS} instead of the pair constructor, and the replacement of src_haskell{fst} with src_haskell{\f -> f id}.
The rest is produced mechanically by adding =S= suffix to all function calls. The src_haskell{map} example can be similarly mechanically translated as follows.
#+BEGIN_SRC haskell :tangle TngMain.hs
mapaS :: (r -> ((x -> y) -> a -> b) -> c)
-> (a -> x)
-> (r -> (y -> b) -> c)
mapaS = homWrap $ \st f -> chopS st $ \s a -> s (f a)
depureMapS c f r = consS c (f r)
runMapS f = f id
mapDeviceS = depureMapS Device unDeviceScott
`mapaS` not
`mapaS` (+ 100)
`mapaS` (+ 200)
testMapDeviceS :: Device
testMapDeviceS = runMapS $ mapDeviceS exampleDevice
#+END_SRC
The most interesting part, however, is the reimplementation of src_haskell{zip}.
By following the terms in the previous section we would arrive at the following translation for src_haskell{depureZip}
#+BEGIN_SRC haskell :tangle TngMain.hs
depureZipS' :: s -> (ra -> a) -> (rb -> b -> c)
-> ra -> rb
-> (s -> a -> b) -> c
depureZipS' c f g r s = consS c (consS (f r) (g s))
#+END_SRC
\noindent Frustratingly, there is no src_haskell{chop2} equivalent for it
#+BEGIN_SRC haskell :tangle TngMainBroken.hs
chop2S' :: ((s -> ((a -> b) -> c) -> d -> e) -> f)
-> (s -> a -> d -> t)
-> (t -> (b -> c) -> e) -> f
chop2S' i f o = i $ \s abq d -> o _ _
#+END_SRC
\noindent because src_haskell{a} becomes effectively inaccessible in this order of src_haskell{consS}ing (as there is no src_haskell{unconsS}).
However, fascinatingly, by simply changing that order to
#+BEGIN_SRC haskell :tangle TngMain.hs
depureZipS c f g r s = consS (consS c (f r)) (g s)
#+END_SRC
\noindent we get our src_haskell{cons2S} and, by mechanical translation, all the rest of src_haskell{zipDevice} example
#+BEGIN_SRC haskell :tangle TngMain.hs
chop2S :: ((((s -> a -> b) -> c) -> d -> e) -> f)
-> (s -> a -> d -> t)
-> (((t -> b) -> c) -> e) -> f
chop2S i f o = i $ \sabc d -> o $ \tb -> sabc $ \s a -> tb $ f s a d
zipaS :: (ra -> rb -> (((((x -> y) -> a -> b) -> c) -> d -> e) -> f))
-> (a -> d -> x)
-> (ra -> rb -> (((y -> b) -> c) -> e) -> f)
zipaS = homWrap2 $ \st f -> chop2S st $ \s a b -> s (f a b)
runZipS f = f id id
zipDeviceS = depureZipS Device unDeviceScott unDeviceScott
`zipaS` (&&)
`zipaS` (+)
`zipaS` (+)
testZipDeviceS :: Device
testZipDeviceS = runZipS $ zipDeviceS exampleDevice testMapDeviceS
#+END_SRC
\noindent thus, again, implementing all the examples from \cref{sec:examples}, but now purely with Scott-encoded data types.
#+BEGIN_remark
Note that while the transformation form src_haskell{b} to src_haskell{(a, b)} for the LISP-encoding or the plain tuples is regular, the transformation from src_haskell{(a -> b -> c -> ... -> z) -> z} to src_haskell{(s -> a -> b -> c -> ... -> z) -> z} is not, the former is not a sub-expression of the latter.
Taking that into account, we feel that the very fact that the implementations demonstrated above are even possible is rather fascinating.
The fact that Scott-encoding can be used as a heterogeneous list is rather surprising as even the fact that src_haskell{consS} is possible is rather weird, not to mention the fact that useful things can be done without src_haskell{unconsS}.
We are not aware of any literature that describes doing anything similar directly to Scott-encoded data types.
#+END_remark
* General Case
@@tex:\label{sec:general-case}@@
Curiously, note that with the aforementioned order of src_haskell{consS}ing src_haskell{chop2S} is actually a special case of src_haskell{chopS}
#+BEGIN_SRC haskell :tangle TngMain.hs
chop2S' :: ((((s -> a -> b) -> c) -> d -> e) -> f)
-> (s -> a -> d -> t)
-> (((t -> b) -> c) -> e) -> f
chop2S' i f o = chopS i (\sabc d tb -> sabc $ \s a -> tb $ f s a d) o
-- == chop2S
#+END_SRC
\noindent and this pattern continues when src_haskell{consS}ing more structures
#+BEGIN_SRC haskell :tangle TngMain.hs
depureZip3S :: s -> (ra -> a -> b) -> (rb -> c -> d) -> (rc -> e -> f)
-> ra -> rb -> rc
-> (((((s -> a) -> b) -> c) -> d) -> e) -> f
depureZip3S c f g h r s t = consS (consS (consS c (f r)) (g s)) (h t)
chop3S :: ((((((s -> a -> b) -> c) -> d -> e) -> f) -> g -> h) -> i)
-> (s -> a -> d -> g -> t)
-> (((((t -> b) -> c) -> e) -> f) -> h) -> i
chop3S i f o = chop2S i (\sabc d g tb -> sabc $ \s a -> tb $ f s a d g) o
-- and so on
#+END_SRC
The same is true for LISP-encoded variant since we can use the same order of src_haskell{cons}ing there, e.g.
#+BEGIN_SRC haskell :tangle TngMain.hs
chop2' :: ((s, (a, b)), (c, d))
-> (s -> a -> c -> t)
-> ((t, b), d)
chop2' (sab, (c, d)) f = (chop sab (\s a -> f s a c), d)
-- ~~ chop2
#+END_SRC
\noindent but we think this presentation makes things look more complex there, not less.
Though, as we shall see in the next section (in its Literal Haskell version), we could have simplified the general case by using src_haskell{chop2'} above.
In other words, if we are to src_haskell{cons} LISP-encoded and src_haskell{consS} Scott-encoded data types in the right order then all of the src_haskell{Applicative}-like operators of this paper and the generalizations of src_haskell{Applicative}-like src_haskell{zip}s to larger numbers of structures can be uniformly produced from just src_haskell{chop} and src_haskell{chopS}.
* Formal Account
@@tex:\label{sec:formally}@@
The derivation of \cref{sec:deriving-the-technique}, as demonstrated by the following sections, describes a technique (as opposed to an isolated example) for expressing transformations between simple data types of a single constructor using src_haskell{Applicative}-like computations.
More formally, that technique consists of
- deconstructing the data type (into its LISP-encoded representation in \cref{sec:deriving-the-technique,sec:implementation} or Scott-encoded representation in \cref{sec:scott}),
- wrapping the deconstructed representation into the src_haskell{Applicative}-like structure in question with an operation analogous to src_haskell{Applicative}'s src_haskell{pure} (src_haskell{depureShow}, etc),
- followed by spelling out transformation steps to the desired representation by interspersing them with an operator analogous to src_haskell{Applicative}'s src_haskell{(<*>)} (src_haskell{showa}, src_haskell{mapa}, src_haskell{zipa}, etc),
- followed by wrapping the whole structure into src_haskell{(->) r} src_haskell{Reader} that is used to propagate the input argument to the front of the expression without adding explicit argument bindings to the whole expressions.
Note, however, that the last "wrapping" bit of the translation is orthogonal to the rest.
It is needed to produce a completely variable-binding-less expression, but that step can be skipped if variable-binding-lessness is not desired: one simply needs to remove the src_haskell{homWrap} wrapping, add an explicitly bound argument to the function, and then apply it to src_haskell{depureShow}.
Also remember that \cref{sec:implementation} showed that, in general, those expressions can implement any computations for generalized multi-stack machines with arbitrary data types and/or functions as "stacks". For the src_haskell{show}-, src_haskell{map}-, and src_haskell{zip}-like transformations we described in detail, however, the central src_haskell{chop} operator corresponds to a simple state transformer of the corresponding "step-by-step" src_haskell{fold}, if we are to view the deconstructed data type as a heterogeneous list.
Finally, note that while src_haskell{depureMap} and src_haskell{depureZip} (src_haskell{depureMapS} and src_haskell{depureZipS}) take more arguments than src_haskell{Applicative}'s src_haskell{pure} this fact is actually inconsequential as in \cref{sec:general-case} we noted that we can simply reorganize all our expressions to src_haskell{cons} to the left (as we had to do for Scott-encoded data types).
Thus, only the last argument to the src_haskell{depure*} functions is of any consequence to the general structure (since it is the argument we are src_haskell{fold}ing on, inductively speaking), the rest are simply baggage used internally by the corresponding operators.
** Dependently-typed src_haskell{Applicative}
Now, the obvious question is how a general structure unifying all those operators would look.
Firstly, let us note that the src_haskell{pure} function of src_haskell{Applicative} can be separated out into its own type class
#+BEGIN_SRC haskell :tangle TngMisc.hs
class Pointed f where
pure :: a -> f a
infixl 4 <*>
class (Pointed f, Functor f) => Applicative f where
(<*>) :: f (a -> b) -> f a -> f b
#+END_SRC
\noindent Moreover, note that, algebraically speaking, src_haskell{Applicative} depends on src_haskell{Pointed} only because their combination gives src_haskell{Functor}, they are independent otherwise.
Since we have no equivalent for src_haskell{Functor} with src_haskell{Applicative}-like expressions we can discuss these two parts separately.
Secondly, let us note that src_haskell{Control.Category} and src_haskell{Control.Arrow} modules of =base=~\cite{Hackage:base4900} define src_haskell{Category}~\cite{Hackage:base4900} and src_haskell{ArrowApply}~\cite{hughes-arrows-00} type classes as
#+BEGIN_SRC haskell :tangle TngMisc.hs
class Category cat where
id :: cat a a
(.) :: cat b c -> cat a b -> cat a c
class Arrow a => ArrowApply a where
app :: a (a b c, b) c
#+END_SRC
\noindent respectively.
Both of these type classes denote generalized functions over generalized function types: src_haskell{cat} and src_haskell{a} respectively.
Thirdly, if we are to look at the types of our src_haskell{showa}, src_haskell{mapa}, and src_haskell{zipa} operators and their versions for Scott-encoded data types,
the most glaring difference from the type of src_haskell{(<*>)} we will notice is the fact that the types of their second arguments and the types of their results depend on the types of their first arguments
(or, equivalently, we can say that all of those depend on another implicit type argument).
In other words, if src_haskell{(<*>)} and src_haskell{app} are two generalizations of the conventional function application, then the structure that describes our operators is a generalization of the dependently typed function application.
The simplest general encoding we have for our examples for GHC Haskell (with awful lot of extensions) looks like this
#+BEGIN_SRC haskell :tangle TngMainGeneric.hs
class ApplicativeLike f where
type C f a b :: * -- type of arrow under `f`
type G f a :: * -- type of argument dependent on `f`
type F f b :: * -- type of result dependent on `f`
(<**>) :: f (C f a b) -> G f a -> F f b
newtype Mapper r f a = Mapper { runMapper :: r -> (f, a) }
instance ApplicativeLike (Mapper e (x -> y)) where
type C (Mapper e (x -> y)) a b = (a, b)
type G (Mapper e (x -> y)) a = a -> x
type F (Mapper e (x -> y)) b = Mapper e y b
f <**> g = Mapper $ mapa (runMapper f) g
mapDeviceG :: Mapper Device Device ()
mapDeviceG = Mapper (depureMap Device unDeviceLISP)
<**> not
<**> (+ 100)
<**> (+ 200)
testMapDeviceG :: Device
testMapDeviceG = runMap $ runMapper mapDeviceG exampleDevice
newtype MapperS c r f a = MapperS
{ runMapperS :: r -> (f -> a) -> c }
instance ApplicativeLike (MapperS c e (x -> y)) where
type C (MapperS c e (x -> y)) a b = a -> b
type G (MapperS c e (x -> y)) a = a -> x
type F (MapperS c e (x -> y)) b = MapperS c e y b
f <**> g = MapperS $ mapaS (runMapperS f) g
mapDeviceGS :: MapperS c Device Device c
mapDeviceGS = MapperS (depureMapS Device unDeviceScott)
<**> not
<**> (+ 100)
<**> (+ 200)
testMapDeviceGS :: Device
testMapDeviceGS = runMapS $ runMapperS mapDeviceGS exampleDevice
-- See Literate Haskell version for many more examples.
#+END_SRC
#+BEGIN_SRC haskell :tangle TngMainGeneric.hs :exports none
newtype Printer r a = Printer
{ runPrinter :: r -> ([String], a) }
instance ApplicativeLike (Printer e) where
type C (Printer e) a b = (a, b)
type G (Printer e) b = b -> String
type F (Printer e) b = Printer e b
f <**> g = Printer $ showa (runPrinter f) g
showDeviceG :: Printer Device ()
showDeviceG = Printer (depureShow unDeviceLISP)
<**> show
<**> show
<**> show
testShowDeviceG :: String
testShowDeviceG = runShow $ runPrinter showDeviceG exampleDevice
newtype PrinterS c r a = PrinterS
{ runPrinterS :: r -> ([String] -> a) -> c }
instance ApplicativeLike (PrinterS c e) where
type C (PrinterS c e) a b = a -> b
type G (PrinterS c e) a = a -> String
type F (PrinterS c e) b = PrinterS c e b
f <**> g = PrinterS $ showaS (runPrinterS f) g
showDeviceGS :: PrinterS c Device c
showDeviceGS = PrinterS (depureShowS unDeviceScott)
<**> show
<**> show
<**> show
testShowDeviceGS :: String
testShowDeviceGS = runShowS $ runPrinterS showDeviceGS exampleDevice
newtype Zipper ra rb f a = Zipper
{ runZipper :: ra -> rb -> (f, a) }
-- we need these, because we used tuples in `zipa`
toZipper f = Zipper $ \ra rb -> (\(a, b, c) -> ((a, b), c)) $ f ra rb
fromZipper f = \ra rb -> (\((a, b), c) -> (a, b, c)) $ runZipper f ra rb
instance ApplicativeLike (Zipper e e (x -> y, (a, b))) where
type C (Zipper e e (x -> y, (a, b))) c d = (c, d)
type G (Zipper e e (x -> y, (a, b))) c = a -> c -> x
type F (Zipper e e (x -> y, (a, b))) d = Zipper e e (y, b) d
f <**> g = toZipper $ zipa (fromZipper f) g
zipDeviceG :: Zipper Device Device (Device, ()) ()
zipDeviceG = toZipper (depureZip Device unDeviceLISP unDeviceLISP)
<**> (&&)
<**> (+)
<**> (+)
testZipDeviceG :: Device
testZipDeviceG = runZip $ (\((a, b), c) -> (a, b, c))
$ runZipper zipDeviceG exampleDevice testMapDeviceG
newtype ZipperS z z' ra rb f g a = ZipperS
{ runZipperS :: ra -> rb -> (((f -> g) -> z) -> a) -> z' }
instance ApplicativeLike (ZipperS z z' e e (x -> y) (a -> b)) where
type C (ZipperS z z' e e (x -> y) (a -> b)) c d = c -> d
type G (ZipperS z z' e e (x -> y) (a -> b)) c = a -> c -> x
type F (ZipperS z z' e e (x -> y) (a -> b)) d = ZipperS z z' e e y b d
f <**> g = ZipperS $ zipaS (runZipperS f) g
zipDeviceGS :: ZipperS z z' Device Device Device z z'
zipDeviceGS = ZipperS (depureZipS Device unDeviceScott unDeviceScott)
<**> (&&)
<**> (+)
<**> (+)
testZipDeviceGS :: Device
testZipDeviceGS = runZipS $ runZipperS zipDeviceGS exampleDevice testMapDeviceGS
#+END_SRC
The operator analogous to src_haskell{pure} simply wraps the result produced by the data type destructor into the corresponding initial state, thus its generalization is not interesting (in general, it is a function src_haskell{a -> f b}).
Moreover, generalizing it actually adds problems because a generic src_haskell{depure} makes src_haskell{(<**>)} ambitious in
#+BEGIN_SRC haskell-spec
ambitiousExample a = depure unDevice <**> a <**> a <**> a
#+END_SRC
\noindent This does not happen for src_haskell{Applicative} type class since both arguments to src_haskell{(<*>)} are of the same type family src_haskell{f} there.
* Conclusion
@@tex:\label{sec:conclusion}@@
From a practical perspective, in this article we have shown that by implementing a series of rather trivial state transformers we called src_haskell{chop*} and wrappers into a src_haskell{(->) r} src_haskell{Reader} we called src_haskell{homWrap*} and then composing them one can express operators that can implement arbitrary computations for generalized multi-stack machines using a rather curious form of expressions very similar to conventional src_haskell{Applicative} parsers.
Then, we demonstrated how to use those operators to implement src_haskell{Applicative}-like pretty-printers, src_haskell{map}s, and src_haskell{zip}s between simple data types of a single constructor by first unfolding them into LISP- and Scott-encoded representations and then folding them back with custom "step-by-step" src_haskell{fold}s.
(Where the very fact that Scott-encoded case is even possible is rather fascinating as those terms are constructed using a rather unorthodox technique.)
#+BEGIN_remark
By the way, note that Haskell's src_haskell{GHC.Generics}~\cite{GHC86:base412:Generics} is not an adequate replacement for LISP- and Scott-encoded representations used in the paper: not only is the src_haskell{Rep} type family complex, its structure is not even deterministic as GHC tries to keep the resulting type representation tree balanced.
Which, practically speaking, suggests another GHC extension.
#+END_remark
From a theoretical perspective, in this article we have presented a natural generalization of the conventional src_haskell{Applicative}\cite{mcbride-paterson-08} type class (which can be viewed as a generalization of conventional function application) into dependent types with generalized arrow of src_haskell{Category}/src_haskell{ArrowApply}~\cite{Hackage:base4900, hughes-arrows-00}.
Both src_haskell{Applicative}s and src_haskell{Monad}s~\cite{moggi-89, moggi-91, Wadler:1992:EFP} (that can be viewed as a generalization of the conventional sequential composition of actions, aka "imperative semicolon") were similarly generalized to superapplicatives and supermonads in~\cite{Bracker2018:SS}.
In particular, \cite{Bracker2018:SS} starts by giving the following definition for src_haskell{Applicative}
#+BEGIN_SRC haskell-spec
class Applicative m n p where
(<*>) :: m (a -> b) -> n a -> p b
#+END_SRC
\noindent then adds constraints on top to make the type inference work, and then requires all of src_haskell{m}, src_haskell{n}, and src_haskell{p} to be src_haskell{Functor}s (producing such a long and scary type class signature as the result so that we decided against including it here).
In contrast, our src_haskell{ApplicativeLike} generalizes the arrow under src_haskell{m}, goes straight to dependent types for src_haskell{n} and src_haskell{p} instead of ad-hoc constraints, and doesn't constrain them in any other way.
#+BEGIN_remark
Which suggests syntactic (rather than algebraic) treatment of src_haskell{ApplicativeLike} structure as it seems that there are no new interesting laws about it except for those that are true for the conventional function application (e.g., congruence src_haskell{a == b => f a == f b}).
#+END_remark
In other words, our src_haskell{ApplicativeLike} can be viewed as a simpler encoding for generalized superapplicatives of~\cite{Bracker2018:SS} when those are treated syntactically rather than algebraically (since we completely ignore src_haskell{Functor}s).
Future fork on the subject consists of applying the same ideas to src_haskell{Alternative} type class to cover the multi-constructor case, which is not clear at the moment since it is not exactly clear how the canonical use of src_haskell{Alternative} for parsing tagged data types should look like in the first place, as, unlike the src_haskell{Applicative} case, different libraries use different idioms for this.