Roman Cheplyaka: articles

Flavours of free applicative functors

Sun, 31 Mar 2013 00:00:00 UT

Six months ago Tom Ellis wrote the article Towards Free Applicatives, where he described his implementation of a free applicative functor. In the reddit discussion of that article a few more implementations were suggested.

In this article I would like to look in more detail how these implementations work and how they differ from each other.

The implementations are rewritten in a common style where possible, to highlight the differences and similarities. Since a picture is worth a thousand words, for each implementation there’s a diagram showing how a simple applicative expression f <$> lift ax <*> lift ay <*> lift az is represented.

Notational conventions

x, y, z, f — simple (non-functorial) values
ax, ay, az — values of the base functor type
tx, ty, tz — values of the free applicative functor type

On the diagrams

F — base functor
Tx, Ty, Tz — inner types of functorial values (e.g. ax has type F Tx). The function f has type Tx -> Ty -> Tz -> Tr.
A square denotes unit (i.e. ()) as a type, term and pattern.

Ørjan Johansen’s free applicative

data Free f a where
  Pure :: a -> Free f a
  Ap :: Free f (a -> b) -> f a -> Free f b

instance Functor f => Functor (Free f) where
  fmap f (Pure x) = Pure $ f x
  fmap f (Ap tx ay) = Ap ((f .) <$> tx) ay

instance Functor f => Applicative (Free f) where
  pure = Pure
  tx <*> Pure y = fmap ($ y) tx
  tx <*> Ap ty az = Ap ((.) <$> tx <*> ty) az

lift :: f a -> Free f a
lift = Ap (Pure id)

lower :: Applicative f => Free f a -> f a
lower (Pure x) = pure x
lower (Ap tx ay) = lower tx <*> ay

The tree grows to the left. This can be easily seen on the diagram, and follows from the fact that the first argument of Ap is a free applicative itself and the second is not. (How the tree grows depends, obviously, on the order of Ap’s arguments. The convention here is that Ap’s arguments are in the applicative order, so that we can meaningfully talk about the tree’s associativity.)

<*> pattern-matches on its right argument, effectively re-associating the tree to the left.

Note that Free f a is an applicative functor regardless of f. It stores f-values in the tree without changes. We’ll see later that this is not always the case.

Twan van Laarhoven’s free applicative

data Free f a where
  Pure :: a -> Free f a
  Ap :: Free f (a -> b) -> f a -> Free f b

instance Functor f => Functor (Free f) where
  fmap f (Pure x) = Pure $ f x
  fmap f (Ap tx ay) = Ap ((f .) <$> tx) ay

instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure f <*> tx = fmap f tx
  Ap tx ay <*> tz = Ap (flip <$> tx <*> tz) ay

lift :: f a -> Free f a
lift = Ap (Pure id)

lower :: Applicative f => Free f a -> f a
lower (Pure x) = pure x
lower (Ap tx ay) = flip id <$> ay <*> lower tx

This is a variation of Ørjan’s implementation. As can be seen from the diagrams, the only difference is that it stores the values in the opposite order, and modifies the function to accept them in that order.

As in Ørjan’s implementation, the tree grows to the left, but <*> now pattern-matches on its left argument, in order to push its right argument to the leftmost position in the tree.

The way <*> does pattern matching directly affects its algorithmic complexity. Ørjan’s implementation is linear in the size of its right argument and thus works better with left-associated applicative expressions. Twan’s version is dual: it is linear in the size of its left argument and works better with right-associated expressions. In both cases, unfortunate nesting increases complexity from linear to quadratic.

Also pay attention to the lower function. It has to take care of the effects — the right subtree must be «executed» before the left subtree in order to restore the original value faithfully.

Paolo Capriotti’s free applicative

data Free f a where
  Pure :: a -> Free f a
  Ap :: f (a -> b) -> Free f a -> Free f b

instance Functor f => Functor (Free f) where
  fmap f (Pure x) = Pure $ f x
  fmap f (Ap ax ty) = Ap (fmap (f.) ax) ty

instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure f <*> tx = fmap f tx
  Ap ax ty <*> tz = Ap (fmap uncurry ax) ((,) <$> ty <*> tz)

lift :: Functor f => f a -> Free f a
lift ax = Ap (const <$> ax) (Pure ())

lower :: Applicative f => Free f a -> f a
lower (Pure x) = pure x
lower (Ap ax ty) = ax <*> lower ty

The diagram looks more complicated here. The first thing to notice is that the tree here grows to the right, unlike in the previous versions. The actual application of our f function happens now near the top of the tree rather than at the bottom. To make that possible, the function has to be converted to the uncurried form.

All left nodes except the topmost one are functions (wrapped in the base functor). All they do is take a nested tuple of the arguments downstream and add their own value to that tuple. The topmost left node already knows the final required argument, ax, and simply applies the uncurried function to the tuple.

The functorial values are stored in a modified form, which requires f to be an actual Functor. (But note that any f can be turned into a functor using Yoneda.)

Tom Ellis’s free applicative

The code here is quite different from the previous versions, so I decided to reproduce it verbatim (except the lift and lower functions, which I’ve added myself).

data ChainA f a b = Single (f (a -> b)) | forall c. Many (f (c -> b)) (ChainA f a c)

instance Functor f => Functor (ChainA f a) where
    fmap f (Single t) = Single (fmap (f .) t)
    fmap f (Many g v) = Many (fmap (f .) g) v

chain :: ChainA f b c -> ChainA f a b -> ChainA f a c
chain (Single t) v = Many t v
chain (Many t ts) v = Many t (chain ts v)

data FreeA f a = Pure a | ChainA (ChainA f () a)

instance Functor f => Functor (FreeA f) where
    fmap f (Pure a) = Pure (f a)
    fmap f (ChainA a) = ChainA (fmap f a)

instance Functor f => Applicative (FreeA f) where
    pure = Pure
    Pure f <*> g = fmap f g
    f <*> Pure g = fmap ($ g) f
    ChainA f <*> ChainA g = ChainA $ chain (pullUnit f) g

pullUnit :: Functor f => ChainA f () (b -> c) -> ChainA f b c
pullUnit = removeUnit . pull

pass :: Functor f => ChainA f a b -> ChainA f (a,c) (b,c)
pass (Single t) = Single (fmap (\f -> \(a,c) -> (f a, c)) t)
pass (Many t ts) = Many (fmap (\f -> \(a,c) -> (f a, c)) t) (pass ts)

pull :: Functor f => ChainA f a (b -> c) -> ChainA f (a,b) c
pull (Single t) = Single (fmap uncurry t)
pull (Many t ts) = Many (fmap uncurry t) (pass ts)

removeUnit :: Functor f => ChainA f ((), a) b -> ChainA f a b
removeUnit (Single t) = Single (fmap (\f -> \a -> f ((),a)) t)
removeUnit (Many t ts) = Many t (removeUnit ts)

lift :: Functor f => f a -> FreeA f a
lift ax = ChainA $ Single $ const <$> ax

lower :: Applicative f => FreeA f a -> f a
lower (Pure x) = pure x
lower (ChainA chain) = lowerChain chain <*> pure ()
  where
    lowerChain :: Applicative f => ChainA f x y -> f (x -> y)
    lowerChain (Single ax) = ax
    lowerChain (Many ax ty) = (.) <$> ax <*> lowerChain ty

Despite the superficial dissimilarity of the code, this is really a variation on Paolo’s implementation. The only difference is that unit is not passed as a part of the nested tuples. Two-level types and auxiliary functions are really just the cost of eliminating that unit.

Which one to use?

I regard Ørjan’s version as the principal one. It is simple, powerful (doesn’t require f to be a functor) and straightforward (doesn’t change the arguments order).

The free package currently uses the Twan’s version, which is the reason of the reverse effect that I mentioned in the previous article. Edward Kmett points out that the reason for choosing Twan’s implementation is that you can see the «next instruction» in O(1) when walking left to right, which is most common.

gtraverse vs gfoldl

Fri, 29 Mar 2013 00:00:00 UT

In Generalizing generic fold, I introduced the gtraverse function as an alternative to gfoldl for generic programming.

To remind the important points:

gtraverse allows more instances to be written, being more flexible about which elements can be treated as being on the same level;
on the other hand, everything that is possible to do with gfoldl seems to be possible to do with gtraverse, too.

It turns out that my intuition was wrong. There is a beautiful correspondence between gfoldl and gtraverse which shows that they are, in fact, equivalent in power. Read on to find out why, and what this means for practical generic programming.

gtraverse through gfoldl

As a quick warm-up, let’s implement gtraverse through gfoldl.

For simplicity, let’s assume that gfoldl and gtraverse are both methods of the same class, Data:

{-# LANGUAGE RankNTypes, GADTs, NoMonoLocalBinds #-}

class Data a where
  gfoldl
    :: (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g)
    -> a -> c a

  gtraverse
    :: Applicative w
    => (forall d . Data d => d -> w d)
    -> a -> w a

Then

gtraverse f = gfoldl g pure
  where
    g acc x = acc <*> f x

In plain English, when folding, we inject each element into c using the supplied function f, and then combine it with the accumulator using <*>.

gfoldl through gtraverse

It turns out that gfoldl can also be interpreted as an applicative traversal for a particular functor — namely, the free applicative functor. We’ll use the one from the free package for now.

If we run gtraverse with liftAp Identity (where Identity wraps its element into a trivial applicative functor), we’ll get a list rather than a tree, which can be easily folded in a gfoldl-like fashion.

One minor issue is that Identity has to capture the Data dictionary of the elements. We can easily achieve that using a GADT

data I a where I :: forall a . Data a => a -> I a

Now, gtraverse (liftAp . I) has type Data a => a -> Ap I a. It transforms any value for which gtraverse is defined to a (heterogeneous) list Ap I a, which contains all immediate children of that value, together with their Data dictionaries.

The next step is to fold that list:

foldAp
  :: (forall d b. Data d => c (d -> b) -> d -> c b)
  -> (forall g. g -> c g)
  -> Ap I a -> c a
foldAp f z (Pure x) = z x
foldAp f z (Ap (I x) k) = (foldAp f z k) `f` x

foldAp takes the same two functional arguments as gfoldl. But instead of working on the original value, it works on the flattened Ap-list.

After gluing the two steps together, we get

gfoldl f z = foldAp f z . gtraverse (liftAp . I)

Nice!

Consequences

So, what does this mean? Do you not need gtraverse since gfoldl can do all the same things?

No!

It is much easier to write instances for your data types using gtraverse, especially when you want to present an alternative view on the type from what is directly implied by its definition. (If you doubt it, you can still try to encode the uniform Data instance for lists and compare it with the gtraverse-based one.)

On the other hand, it is nice to know that we don’t really lose any power by adopting gtraverse instead of gfoldl.

You can try it out right now: I’ve just uploaded the first version of traverse-with-class on hackage.

Remaining issues

There are a couple of issues in our gfoldl implementation above¹:

Because of the free applicative functor usage, it has the same quadratic complexity problems as free monads.
Because of the way this free applicative works, our gfoldl is really a gfoldr: it traverses the elements in the reverse order.

I’ll talk more about these in subsequent articles.

to make it clear, there are no such issues in the library, because it doesn’t provide a gfoldl function. It provides unrelated functions gfoldl' and gfoldr with different types.↩

Ergative verbs in programming

Thu, 14 Mar 2013 00:00:00 UT

For a long time I felt uncomfortable with phrases like «my program doesn’t compile».

Of course it doesn’t compile, stupid! It’s not a compiler!

I understood that this phrase was supposed to mean «The compiler fails to compile my program». But nevertheless it seemed like a wrong usage of the verb «compile».

Well, today I learned (thanks to Edwin Ashworth) that this is a common phenomenon in English. It’s called ergative usage. There is a long list of ergative verbs on Wiktionary, and «compile» is there!

This is a list of programming-related verbs that I’ve seen being used ergatively:

parse
type-check
compile
build

You can notice that they all follow the same pattern — something that one program (usually a compiler) does to another program. I’d be curious to find computing-related ergative verbs that do not fall into this pattern.

Generalizing generic fold

Mon, 11 Mar 2013 00:00:00 UT

Uniform folding

Suppose we’ve created a new container data structure in Haskell, such as Data.Sequence.Seq. We now want to write a Data instance for it, to allow generic queries and transforms inside our container.

Let’s recall gfoldl definition for lists:

gfoldl f z [] = z []
gfoldl f z (x:xs) = z (:) `f` x `f` xs

We can define gfoldl similarly for sequences (in fact, this is the precise definition from Data.Sequence):

gfoldl f z s = case viewl s of
  EmptyL  -> z empty
  x :< xs -> z (<|) `f` x `f` xs

There are, however, downsides to this definition:

Generic map over our container would be less efficient than hand-written map, even if we ignore the costs associated with run-time type casts.

Indeed, in the generic definition we do not take advantage of the fact that we already have a proper container structure for our elements. Instead, we construct the structure from scratch, adding elements one by one. This overhead may be small for Seq, whose cons is O(1). But in case of an array-based structure, such as Vector, we’re out of luck.
If we only care about the closed recursion combinators, such as everywhere, we wouldn’t know the difference. But when open recursion is needed (e.g. gmapT), the semantics is not the one we’d expect. The intuition is that gmapT maps over the immediate «subterms» of an expression. One might expect that the subterms of Seq a are all of its elements (of type a). But no, we’re forced into this recursive list mindset, where the immediate subterms of a sequence are its head and tail.

(To be fair, it does make sense if we imagine data structures really being inductively-defined terms. But it is a very limited worldview.)

Can we define gfoldl in the uniform fashion, folding over all the elements at once? Try this yourself to understand better why it’s not easy.

I haven’t actually done it, but I think it’s achievable using some amount of type class hackery. Anyway, having to come up with such hacks defeats the point of an easy-to-use generic programming library.

In essence, the limitation of gfoldl is that it forces us to know the number of elements in advance. We cannot (easily) construct the result of the fold by recursive computation.

Generic traversals

In order to resolve the problem stated above, we need to restrict the type of gfoldl¹.

Recall its type:

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
       -> (forall g. g -> c g)
       -> a -> c a

What might the first functional argument of gfoldl do? It probably transforms d to something like c d by using its Data instance, and then combines c (d -> b) with c d to obtain c b. This is not a sure thing, of course: the caller of gfoldl knows what c exactly is, so it might combine them in unexpected ways. Let us proceed with this assumption, however; as I said above, we need to restrict the caller in order to give more power to the callee.

So, if our guess is correct, we can separate the two activities into two different functions:

gfoldl :: (forall d. Data d => d -> c d)
       -> (forall d b. c (d -> b) -> c d -> c b)
       -> (forall g. g -> c g)
       -> a -> c a

The whole thing now suddenly becomes very familiar: c is an applicative functor! The second and third arguments are <*> and pure, respectively. And the applicative laws had better hold — there are now many ways to express the same thing, and we don’t expect there to be a difference.

Using the Applicative class, we can rewrite the type as

gtraverse :: Applicative c => (forall d . GTraversable d => d -> c d) -> a -> c a

Note that I took this chance to rename our restricted gfoldl to gtraverse and Data to GTraversable. The reason is that it is a generic version of traverse from Data.Traversable, whose type is

traverse :: Applicative c => (a -> c b) -> t a -> c (t b)

Read the type of gtraverse as «traverse this structure, applying the supplied function to the immediate subterms; then use the Applicative instance to reconstruct the original structure».

We can now write the uniform instance for lists (and any other algebraic data type) without a hassle:

gtraverse f [] = pure []
gtraverse f (x:xs) = (:) <$> f x <*> gtraverse f xs

But how does it restrict the caller of gfoldl? Not much. All the usual combinators, such as gmapT, gmapQ, gmapM etc. are expressible with gtraverse. I’d be curious to see an application of gfoldl for which gtraverse is too restrictive.

Yes, the article’s title is a lie. Thanks for reading this far. What we are really generalizing, by allowing more instances, is the Data class.↩

Open your name resolution

Mon, 04 Mar 2013 00:00:00 UT

What is name resolution?

Name resolution is a program analysis which for every name decides what that name refers to.

Consider the following Haskell program as an example:

n :: Integer
n = let k = 10 in k * k

There are three names in this program: n, k and Integer. The result of name resolution in this case would be:

n refers to the global value defined in the program itself, on lines 1-2;
Integer refers to the type (implicitly) imported from Prelude;
k on line 2 is a local value defined on the same line.

This article is concerned with the following question: how should the API of a name resolution library be structured?

Annotations

The standard approach is a function that transforms a simple AST to the annotated AST, where every name is annotated with its binding information (just like we did above).

(Note that a simple map from names to binding information won’t do: the same name can refer to different things in different parts of the program.)

This is enough for most applications of name resolution, such as type checking, compilation or static analysis.

Significance of lexical environment

However, simple annotations are not enough for source-to-source transformations, like the ones performed by HaRe or HasFix.

Such transformations typically require access to the whole symbol table to avoid variable capture. As an example, imagine that in the new version of some module Mod foo has been renamed to bar, and we want to adapt our own code to use this new version. And our code looks like this:

baz x = let bar = x + 1 in foo bar

Name resolution tells us that foo on that line indeed comes from Mod and should be renamed. But if we blindly apply the renaming, we’ll get

baz x = let bar = x + 1 in bar bar

where bar no longer refers to the global value imported from Mod — it has been captured by let!

The solution is simple: rename foo to qualified name Mod.bar whenever simple bar is already defined in the enclosing lexical scope. It requires us, however, to know the lexical environment at every point.

Annotating with symbol tables

Why not store the whole symbol table at every point in the AST? This could work. In a lazy language this is not even as bad, time- and space-wise, as it might seem.

It is cumbersome, however. Every time we replace a subtree, we need manually to re-run name resolution on the new subtree (or even on the whole tree, if there’s any possibility that other annotations may become invalid as a result of the replacement).

Open recursion

In order to maintain the symbol table during the traversal, we can try to keep track of the local bindings ourselves, only to discover that it’s not that trivial, and that we’re replicating a large part of the resolution code.

The core of the problem is that the name resolution algorithm is one big-step tree traversal, and we can only observe its final result (or a trace of its execution in the form of annotations).

If we could split it up into small-step, one layer at a time, resolution functions, we could use them in our own traversals and interleave them with transformations. Another name for this approach is open recursion, hence the article’s title.

Single-sorted AST

If our AST is a single recursive data type (parameterised by the annotation type)

type VarName = String

data Exp a
  = Var a VarName
  | App a (Exp a) (Exp a)
  | Lambda a VarName (Exp a)

type SymbolTable a = Map.Map VarName a

then such a small-step resolution function would have type

resolve
  :: (SymbolTable a -> Exp -> Exp)
  ->  SymbolTable a -> Exp -> Exp

It takes an expression, the symbol table (or environment) that corresponds to the enclosing lexical context of that expression, and a transformation function. It then applies the transformation to all immediate children of the expression.

Note that the transformation function is in turn parameterised by the symbol table. It is the responsibility of resolve to update the symbol table accordingly before using it to transform the children.

An implementation of resolve might look like this

resolve f tbl e =
  case e of
    Var l n -> Var l n
    App l e1 e2 -> App l (f tbl e1) (f tbl e2)
    Lambda l n body -> Lambda l n (f (Map.insert n l tbl) body)

Now that we have resolve, it is easy to tie the knot and write the big-step recursive traversal:

resolveRec :: Exp a -> Exp a
resolveRec = fix resolve Map.empty

resolveRec doesn’t do anything interesting — it’s an identity function. But we can compose resolve with an interesting transformation before “closing” the recursion:

annotate
  :: (SymbolTable a -> Exp a -> Exp a)
  ->  SymbolTable a -> Exp a -> Exp a
annotate f tbl e =
  case e of
    Var _ n -> f tbl $ Var (tbl Map.! n) n
    _ -> f tbl e

annotateRec :: Exp a -> Exp a
annotateRec = fix (resolve . annotate) Map.empty

Let’s try it out:

*Main> annotateRec $ Lambda 1 "x" $ App 2 (Var 3 "x") (Var 4 "x")
Lambda 1 "x" (App 2 (Var 1 "x") (Var 1 "x"))

Hence, the annotation interface to a name resolution library is easy to implement given the open recursion interface. But the open recursion interface is much more powerful, allowing the transformation function to depend on the lexical environment in non-trivial ways.

Multi-sorted AST

What if our AST is represented by a multitude of mutually recursive data types, just like in haskell-src-exts? Generic programming may help here — specifically, the “Scrap your boilerplate” approach.

A stock library, such as syb-with-class, might go a long way, but let’s roll out our own. It will be simpler this way, but also more flexible (for example, it’s possible to modify this presentation to allow the traversal to change the annotation type).

How does the type of resolve change? It now has to work for any AST node type, rather than just for Exp, i.e. be polymorphic. Furthermore, the functional argument to resolve, which used to have type SymbolTable a -> Exp -> Exp, also has to be polymorphic, because the types of node’s children may be different (and may differ from the node’s type itself).

To encode this polymorphism, one can use either a type class or a GADT sum type (see this StackOverflow entry for comparison of these approaches).

Although we are dealing with a finite, closed universe (consisting of haskell-src-exts node types) in this case, I prefer the class-based approach because it’s more practical — it doesn’t force us to define a giant GADT.

Thus, resolve now becomes a class method:

class Typeable a => Resolvable a where
  resolve
    :: (forall b . Resolvable b => SymbolTable -> b -> b)
    ->                             SymbolTable -> a -> a

The Typeable superclass constraint is needed here so that we can write type-specific cases (such as case for Var in the annotate function).

Otherwise, implementing and using this approach for a multi-sorted AST is quite similar to the single-sorted case.

Conclusions

The article argues that the open recursion approach to name resolution offers more power to the user and shows how to implement it.

The presentation here is simplified for the sake of clarity. A full implementation would allow queries (folds), effectful traversals and traversal that can change the annotation type.

For Haskell (and haskell-src-exts AST), I’ve just started implementing this idea in haskell-names.

Announcing SmallCheck 1.0

Tue, 19 Feb 2013 00:00:00 UT

I am glad to announce a new major release of SmallCheck (hackage).

What is SmallCheck?

SmallCheck is a property-based testing library for Haskell.

If you are familiar with QuickCheck, you can think of SmallCheck as a better QuickCheck. The main way in which it is better is that it is non-random: whether your tests pass does not depend on the roll of the dice.

If you are not familiar with QuickCheck, the idea of SmallCheck is to check certain properties of your functions, as opposed to unit testing, where you just check the expected outcome of some particular tests.

For an introduction to property-based testing, check out Chapter 11 of Real World Haskell. It should be straightforward to translate all the examples there to SmallCheck.

What’s new in 1.0

Monadic properties

Properties are now parameterised on the monad they work in.

The two main ways a property can use the monad are:

generating test cases monadically
verifying the condition monadically

Monadic test cases generation can be used to read test cases from files. A well-known problem when testing compilers is that it is hard to enumerate or randomly generate valid programs. So here you go — just put some examples in the file system, and use them to verify some properties of your compiler.

An example of monadic verification is when you want to verify your code against an external (or otherwise impure) reference implementation.

Quantifiers

The semantics of quantifiers has changed. Previously, all variables were quantified universally by default, and a quantifier (like exists) changed the quantification of the next variable.

So, for example, exists $ \x y -> p x y was interpreted as $\exists x: \forall y. p\ x\ y$, which is probably not what one would expect.

Now the quantification operators (forAll, exists and existsUnique) set the quantification context for all subsequent variables, so the above property means $\exists x, y: p\ x\ y$.

Uniqueness quantification

There’s an interesting effect related to the uniqueness quantifier existsUnique (which was previously called exists1).

There are two ways to interpret existsUnique $ \x y -> p x y, “curried” and “uncurried”:

$\exists ! x: \exists ! y: p\ x\ y$
$\exists ! (x,y): p\ x\ y$

These two actually have different meaning. Suppose that $p\ x\ y=(|x|=|y|)$, where $|x|$ denotes the absolute value of an integer $x$. Then the first property above is true, and the second is false (be sure to check this yourself).

When mathematicians write $\exists ! x,y:p\ x\ y$, they really mean the second interpretation, so this is what SmallCheck implements (although the first interpretation would be much easier to implement).

Higher-order properties

Both SmallCheck and QuickCheck have a ==> operator, which tests an implication. The left argument of ==> has type Bool, and it’s usually a statement that the generated arguments satisfy some side condition (e.g. generated programs are valid).

In this new version of SmallCheck, the left argument of ==> can be an arbitrary property, with its own quantifiers etc. Here’s how we could test an isPrime function:

import Test.SmallCheck
import Test.SmallCheck.Series

isPrime :: Integer -> Bool
isPrime _ = True

main = 
  smallCheck 5 {- 5 is the testing depth -} $
    \(Positive n) ->
      (exists $ \(Positive d) -> d /= 1 && d /= n && n `mod` d == 0) ==> not (isPrime n)

Unsurprisingly, the result will be

Failed test no. 4.
there exists 4 such that
  condition is false

Ordered testing

SmallCheck has just got more efficient and less annoying!

Previously, if you wanted to get the minimal counterexample, you used the function smallCheck which tested the property first with depth 0, then with depth 1 and so on — up to the limit that you told it.

The reason was that the Serial instance of e.g. Integer generated the following integers for depth 3:

[-3,-2,-1,0,1,2,3]

They are tried in exactly this order, and, if all of them were counterexamples, the user would be presented with -3 as the first one.

Now the instances generate examples in the order of increasing depth, e.g.

[0,1,-1,2,-2,3,-3]

so there’s no need to try multiple depths.

Better reporting

The way SmallCheck reports its findings is now greatly improved, especially in some complex cases.

For example, consider the following property:

smallCheck 5 $ existsUnique $ \x -> (forAll $ \y -> x * y >= 0) ==> (forAll $ \y -> x * y == (0 :: Integer))

Here’s what SmallCheck 0.6.2 reports (or, to be precise, would report if it supported higher-order properties):

Depth 0:
  Completed 1 test(s) without failure.
Depth 1:
  Failed test no. 12. Test values follow.
  non-uniqueness
  -1
  0

And this is the output of SmallCheck 1.0:

Failed test no. 12.
there are at least two arguments satisfying the property:
  for 0
    condition is true
  for 1
    property is vacuously true because
      there exists -1 such that
        condition is false

Required type annotations

Because the Testable class is now multi-parameter (parameterised on the type and the monad), ambiguous types that involve this class do not get defaulted. To put it simply, most non-trivial properties now require some type annotations.

This turned out to be a very good thing for SmallCheck (which I couldn’t envision). Defaulting for properties often works in an unexpected way. For example, here’s what an older SmallCheck would tell you if you asked it whether all things are the equal:

> depthCheck 5 $ \x y -> x == y
Depth 5:
  Completed 1 test(s) without failure.

The result is unexpected, but at least we get some clue from the fact that there was just one test: the type of the variables got defaulted to ()!

Alas, QuickCheck doesn’t give us even this hint:

> quickCheck $ \x y -> x == y
+++ OK, passed 100 tests.

Luckily, with the new SmallCheck you actually get a type error:

<interactive>:10:26:
    No instance for (Eq a0) arising from a use of `=='
    The type variable `a0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)

And indeed, the problem is easy to fix once you know it’s there:

> smallCheck 5 $ \x y -> x == (y :: Integer)
Failed test no. 2.
there exist 0 1 such that
  condition is false

Simpler interface

I took this chance to clean the API and make it more orthogonal.

Previously SmallCheck had functions like

forAllElem :: (Show a, Testable b) => [a] -> (a -> b) -> Property

which did three things at once:

made the variable universally quantified
converted the list to a depth-independent series
quantified the variable over that series

No wonder the API suffered from the combinatorial explosion. Now these things are all done separately:

generate :: (Depth -> [a]) -> Series m a

can be used to turn a list into a series;

over :: (Monad m, Show a, Testable m b) => Series m a -> (a -> b) -> Property m

sets the domain of quantification; and

forAll :: Testable m a => a -> Property m

sets the quantification context.

Generic uncurry

Tue, 29 Jan 2013 00:00:00 UT

For the next version of SmallCheck I needed a generic uncurry function in Haskell. To my surprise, I couldn’t google anything simple and ready to use.

So here it is, for future reference.

{-# LANGUAGE TypeFamilies, DefaultSignatures, UndecidableInstances #-}
class Uncurry a where
  type Uncurried1 b a
  type Uncurried1 b a = b -> a

  unc1 :: (b -> a) -> Uncurried1 b a
  default unc1 :: (b -> a) -> (b -> a)
  unc1 = id

  type Uncurried a
  type Uncurried a = a

  unc :: a -> Uncurried a
  default unc :: a -> a
  unc = id

instance Uncurry y => Uncurry (x -> y) where
  type Uncurried1 z (x -> y) = Uncurried1 (z, x) y
  unc1 = unc1 . uncurry

  type Uncurried (x -> y) = Uncurried1 x y
  unc = unc1

You also need to make the final type an instance of Uncurry. For example, if you need to uncurry Int -> Bool -> Double, Double has to be an instance of Uncurry. But thanks to default method signatures and associated type synonym defaults, it is as easy as

instance Uncurry Double

Uncurry1 and unc1 are implementation details. The useful parts are Uncurry, which converts the type to its uncurried version, and unc, which uncurries the function itself.

After loading the code in ghci, you can see that it works by:

*Uncurry> :kind! Uncurried (Int -> Bool -> Char -> Double)
Uncurried (Int -> Bool -> Char -> Double) :: *
= ((Int, Bool), Char) -> Double

*Uncurry> :t unc $ \x y z -> (x + y * z :: Double)
unc $ \x y z -> (x + y * z :: Double)
  :: ((Double, Double), Double) -> Double

*Uncurry> unc (\x y z -> (x + y * z :: Double)) ((1,2),3)
7.0

I tested this with GHC 7.6, but I think it should work with GHC 7.4 as well.

Subtractable values are torsors

Tue, 08 Jan 2013 00:00:00 UT

A group is an abstraction for things that can be «added» and «subtracted» (in some sense).

Most of the groups that programmers deal with are numeric, although some interesting groups arise in graphics and cryptography.

If we only require that things can be added, but not subtracted, we get semigroups and monoids (the difference is that a monoid also has a «zero» element). These are plentiful, with applications ranging from diagrams to regular expressions.

The reason is, of course, that addition is very natural — we can consider any way to combine objects together an addition as soon as it is associative — while subtraction, the inverse of addition, often doesn’t make sense.

Dates

But there are also things that can be subtracted, but not added. The simplest example is dates. You can subtract two dates to get the time interval between them, but you cannot add two dates. It doesn’t make sense to ask what today plus tomorrow is. You could try to add the numeric values corresponding to the dates and convert the answer back to a date, but the result would depend on whether you count from the start of the Common Era, the Unix epoch, or something else.

While adding two dates is not possible, it is possible to add a time interval to a date («five days from today»). This suggests that we should not confound dates and time intervals — they are different types of values.

For example, in the Haskell time package, there are types UTCTime and NominalDiffTime, and the following functions:

addUTCTime :: NominalDiffTime -> UTCTime -> UTCTime
diffUTCTime :: UTCTime -> UTCTime -> NominalDiffTime

Time intervals can also be added and subtracted, as witnessed by the Num NominalDiffTime instance.

Ask mathematics

What is the mathematical notion that characterizes dates? It should involve two sets: the set V of values and the set D of value differences.

The set D must form an additive group, so that we can add and subtract the differences. (The word «additive» means that we assume that the group operation, identity element and inverse operation are called +, 0 and − respectively. In group theory it is more common to call them *, 1 and ⁻¹.)

Thus we have the “zero” difference 0∈D and operations +:D×D→D, −:D→D which satisfy the usual group laws:

+/0 (identity element): 0+x=x+0=x
+/+ (associativity): (x+y)+z=x+(y+z)
+/− (inverse element): x+(−x)=(−x)+x=0

(We can write x−y as a shorthand for x+(−y).)

We do not require + to be commutative to preserve generality, even though it is commutative for our current example.

We need to be able to add a difference to a value. Thus, we need a function add:D×V→V. We would expect it to play well with the group structure of D:

add/0: add(0,v)=v
add/+: add(x+y,v)=add(x,add(y,v))

An alternative view on these laws is that the curried version of add, curry(add):D→(V→V), is a group homomorphism from D to the group of bijections on V.

The mathematical abstraction corresponding to our add function is an action of group D on the set V. But it doesn’t yet capture the fact that we can subtract two values to get a difference. For that we need a function diff:V×V→D inverse to add:

diff/add: diff(add(x,v),v)=x
add/diff: add(diff(u,v),v)=u

If such a function exists, the set V is called a torsor over the group D.

Thus, it is the mathematical notion of torsor that characterizes subtractable values.

Conal Elliott defines torsors in Haskell under the name of affine spaces.

Other examples

Points

Another simple example of a torsor is points. In linear algebra we get used to conflating points and vectors, because we consider vectors originating at zero.

But the geometrical intuition suggests that vectors do not have to be tied to zero. A vector is a directed segment which can be freely translated (shifted) on the plane (or in the space).

We can subtract two points to get a vector from one point to another. We can add a vector to a point, by translating it so that its origin becomes the given point. The end point of the vector then becomes the result of addition.

Vectors form an additive group, and points form a torsor over the vectors.

Like with dates, results of torsor operations on points and vectors do not depend on (and do not require the existence of) a coordinate system, while the «sum» of two points will change if you change the origin.

Files

There are also some examples that look very much like torsors, but do not satisfy all the laws.

One of such examples is files. The difference of two files is what we call a patch, or a diff. We can diff two files and apply the resulting patch to a third file («cherry-picking»).

Although patches do not form a group, they can be modelled as inverse semigroups. This motivates us to consider torsors based on inverse semigroups rather than on groups.

Haskell dialects

Haskell dialects can be considered as a torsor-like structure over Haskell extensions. We can add extensions to languages, e.g. add(RankNTypes+GADTs−MonomorphismRestriction, Haskell2010).

We can also subtract two languages to find out the difference between them in terms of extensions: diff(Haskell2010, Haskell98)=DoAndIfThenElse+PatternGuards+ForeignFunctionInterface+EmptyDataDecls−NPlusKPatterns.

Extensions do not form a group. The easiest way to see that is to observe that extensions are idempotent, i.e. X+X=X for any extension X. However, in a group there is only one idempotent element — zero.

Extensions do form an inverse semigroup, though. Thus we again arrive at inverse semigroup torsors.

Acknowledgements

A recent discussion with Niklas Broberg about Haskell extensions motivated me to explore these concepts. His HIW’12 lightning talk on Haskell Modular Mindset is also relevant.

Oleksandr Manzyuk kindly pointed me to the concept of a torsor.

Monads in dynamic languages

Wed, 26 Dec 2012 00:00:00 UT

Are monads possible outside of Haskell?

Of course, it depends on what you call a monad.

The definition that is usually accepted in the Haskell context — that a monad is an instance of the particular type constructor class, Monad, with two methods satisfying three laws — is very much tied to Haskell’s language features — most importantly, types, type constructors and type constructor classes. Hence, this or similar notion of monad can only exist in a language rather close to Haskell.

If we drop the type constructor class requirement, then a monad is a triple consisting of a type constructor M and two polymorphic functions

return :: forall a . a -> M a
(>>=) :: forall a b . M a -> (a -> M b) -> M b

This is the definition originally used by Wadler in The essence of functional programming. By this definition, Monads can be implemented in other Hindley-Milner based languages, like Miranda and ML.

But what if we take this to extreme? What if we consider a dynamically typed functional language?

A dynamically typed language is nothing else than a static language with a single type, which we shall call here U. Thus, the signatures of >>= and return become

return :: U -> U
(>>=) :: U -> (U -> U) -> U

(We could as well say that >>= and return both have type U — remember, there’s only one type!) The functions themselves are still presumed to satisfy the usual laws.

This has been done many times before, most recent example being Douglas Crockford’s keynote at YUIConf. Douglas’s presentation has received a lot of criticism (and I’m not going to defend him), but some critics even have expressed the doubt that these are not «genuine» monads.

To settle this, let’s turn to the category theory — after all, that’s where monads come from. Haskell’s monads are category theory monads, where the type constructor is considered as an endofunctor on Hask, the category of Haskell types and functions.

What changes when we go from Haskell to a unityped language is that all the diversity of Haskell types collapses into the single type, U. That doesn’t stop it from forming a category, though. Because it has a single object, we don’t need a type constructor to represent the functorial action on objects — it’s always identity. We only need to know the functorial action on arrows (called fmap in Haskell) — but it is already determined by return and >>=.

To summarize, there doesn’t seem to be any reason to think that monads are somehow impossible in dynamic functional languages. And, although Haskellers usually consider monads as something closely tied to types, in a dynamic language all you need to define a monad is to define a pair of functions satisfying the monad laws.

Surprises of the Haskell module system (part 1)

Tue, 25 Dec 2012 00:00:00 UT

While basics of the Haskell module system are easy to understand, there are certainly interesting corner cases and non-obvious (mis)features. In this and the following articles we will explore some curious examples.

All of these are documented in the Haskell report, but the tricky details are hard to notice and recognize (although the reader is encouraged to read the report nevertheless!). Another good read on this subject is A Formal Specification for the Haskell 98 Module System by Iavor S. Diatchki, Mark P. Jones, and Thomas Hallgren.

Empty module header

What happens when the export list is omitted, like in the following example?

module M where

foo = 42

This one is easy — all the locally defined types, classes and values are exported.

We might presume that something similar happens when we omit the module header entirely — like if we just put

foo = 42

in a file by itself.

Contrary to this intuition and according to the standard, when you omit the module header, it is assumed to be module Main(main) where.

Sometimes you want to check whether some Haskell snippet compile. You may put it into a file and try ghc test.hs. But even if the snippet itself doesn’t contain errors, you’ll get a message

test.hs:1:1: The function `main' is not defined in module `Main'

The message may seem confusing at first — what’s the module Main it’s talking about, and why do I need this main function? Well, above is the answer.

Module re-exports

You probably know that you can re-export a whole module from your own module. The syntax is

module M (module N) where
...

The semantics of this re-export is a bit tricky, though. For example, what can we say about the following module?

module M (module Data.List) where
import qualified Data.List

You’d probably think that module M now export everything that is exported by Data.List. Not at all! The standard says (emphasis is mine):

The form module M names the set of all entities that are in scope with both an unqualified name e and a qualified name M.e.

Since we imported Data.List qualified, nothing from it is in scope under an unqualified name. So, M doesn’t export anything. Right? Not quite.

The last thing we need to observe here is that although the single module imported by M explicitly is Data.List, there’s always an implicit import — Prelude. And these two share quite a lot in common — functions like foldr, map, length etc. All these satisfy the criterion above — they are in scope with both unqualified and qualified names, although these names come from different modules.

To summarize, the module M defined above will export exactly the intersection of Prelude and Data.List, plus instances exported by either of these modules.

Haskell recipe: reading list of lines

Thu, 25 Oct 2012 00:00:00 UT

import Prelude hiding (readList)
import Control.Applicative
import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Maybe
import Data.Maybe

Suppose we need to ask the user to enter a list of lines, terminated by an empty line. The usual way to do it is through recursion:

readList :: IO [String]
readList = do
  l <- getLine
  if null l
    then return []
    else (l :) <$> readList

This is fine, but can we do better?

A good style in Haskell is to replace explicit recursion with high-level recursion combinators where it is possible and doesn’t harm readability.

What is the pattern here? Those who are familiar with parser combinator libraries will easily recognize the many combinator. It tries to recognize as many items as possible and returns the list of recognized items (in this case successful recognition means that we got a non-empty line).

A generalization of the many combinator works for any applicative functor which is an instance of the Alternative class:

many :: Alternative f => f a -> f [a]

The IO functor is not an instance of Alternative, but we can fix it by layering a MaybeT transformer on top of it. MaybeT will be our means to distinguish failure from success.

readList :: IO [String]
readList = fmap (fromMaybe []) $ runMaybeT $ many $ do
  l <- lift getLine
  guard $ not $ null l
  return l

The inner do-block is the code which reads one line, and, depending on whether that line is null, returns it or signals about the failure.

Some more details about what’s going on there.

lift getLine lifts getLine from IO String to MaybeT IO String by assuming that it always succeeds (in MaybeT sense).
guard is a function from the MonadZero class that checks the condition and, if it does not hold, declares failure. It is somewhat similar to an assert function, except it is used for control flow rather than debugging purposes.
Finally, if guard did not abort the computation, we get to the last line that simply returns the line we’ve just read.

(If you want to learn more about how monad transformers work, please refer to Composing monadic effects.)

The outer code does boring stuff: runMaybeT transforms MaybeT IO String to IO (Maybe String) (which is the same thing but newtyped), and fromMaybe interprets Nothing as the empty list.

It is interesting that only the first line of readList definition gives us a hint that MaybeT works here. The rest of the code just uses overloaded functions many, lift, guard and return.

Was the rewrite worth it? It is debatable, since a function did get a bit more complicated. But in my opinion, the answer is yes — we got rid of explicit recursion, and the idea of the function became more clear.

Reasoning about space usage in Haskell

Sun, 08 Apr 2012 00:00:00 UT

This article describes why it’s hard to reason about space usage of Haskell programs.

Operational semantics

The standard (“The Haskell Report”) does not specify an operational semantics for Haskell. Thus, in order to talk about space usage of Haskell programs, we need to fix a particular semantics. A good choice is the STG semantics as defined in the fast curry paper. First, it is formally defined; second, it has significant practical value, since it is used in GHC, the de-facto standard Haskell compiler.

Note, however, that the STG operational semantics is defined for STG programs, not Haskell programs (STG defines its own small functional language). It’s not always obvious what STG program corresponds to a given Haskell program because of numerous optimizations performed by the compiler, but GHC allows to see the resulting STG code using the -ddump-stg flag.

Operational properties are context-dependent

In eager languages, usually we can easily express time and space complexity, e.g. using O-notation.

In Haskell, operational properties are largely context-dependent, and there’s no existing framework to express them.

Laziness

One source of context dependency is a direct consequence of lazy evaluation: the function result may be evaluated to different extents by different callers.

For example, it may seem that [1..n] requires O(n) memory, but when called from take m [1..n], it takes only O(min(m,n)) memory.

Garbage collection

Another source of context dependency is interaction between laziness and automatic memory management.

For example, the following two functions look equivalent in terms of space usage (although the second one is somewhat less time-efficient):

f1 list = foldl' (\(!a,!b) x -> (a + x, b * x)) (0, 1) list

f2 list = (foldl' (\a x -> a + x) 0 list, foldl' (\b x -> b * x) 1 list)

It would seem that these functions run in constant space. Of course, by “constant space” we really mean “constant additional space” – we do not count the space occupied by the list itself, because the function doesn’t create the list. Well, in a lazy language it does!

The difference becomes clear if we consider f1 [1..n] and f2 [1..n]: the former indeed runs in constant space, while the latter requires linear space.

The reason is that f1 can process the list incrementally. It demands the next value from the list, updates its accumulators and throws the value away.

In f2, the first fold evaluates the list, but it has to be kept in memory to be used for the second fold. As a result, by the time the first fold is evaluated, the whole list is evaluated and none of it is garbage collected.

Thunks

It’s not enough to track how much space our data occupies. Another kind of heap inhabitants is thunks. When more thunks are created than necessary, we have a thunk leak.

By the way, how many thunks may be necessary? Are there examples where having more than O(1) thunks at some point of program execution is the best solution to the problem? I don’t know yet.

In any case, we need to be able to reason about the number of thunks that are created by a function.

To complicate things further, creation of thunks depends on how the function result is evaluated. For example, a function returns a (lazy) tuple. We force the first element of that tuple. During the evaluation, everything that is needed to evaluate that first element is evaluated immediately, but values needed only for the second element are stored in thunks.

If we evaluated the second element, the picture would be dual, and the number of thunks probably would be different.

Conclusions

Currently, if we want to reason about space usage of Haskell programs, we need:

study the source code of each function. A function documentation typically includes its type, denotational semantics and perhaps some O-figures, but that’s not enough, as we’ve seen;
for each function, understand how its result is evaluated by all callers.

Clearly, this breaks abstraction and modularity.

In practice, GHC’s strictness analyser is very smart, so most of the time we don’t notice any problems. Still, it’s very important to have a framework in which we could analyse and document functions’ operational behaviour in a modular and composable way.

Composing monadic effects

Mon, 02 Jan 2012 00:00:00 UT

In Haskell, monad transformers are used to combine effects provided by multiple monads.

Boring example: Writer, Reader, State

For instance, if we want to have a read-only environment plus a write-only logging facility, we can start with the Reader monad and add a logging facility to it with the WriterT monad transformer:

type MyMonad w r a = WriterT w (Reader r) a

Or, we could start with the Writer monad and put the ReaderT transformer on top of it:

type MyMonad w r a = ReaderT r (Writer w) a

In the end, it doesn’t matter which way we choose, as both are isomorphic to

type MyMonad w r a = r -> (a, w)

If we want to have a state as well, we can plug in the StateT transformer anywhere in the stack, and again the order doesn’t matter. The resulting monad is now isomorphic to the standard RWS (Reader-Writer-State) monad.

So, we say about those transformers that they commute (recall that Reader is just the ReaderT transformer applied to the Identity monad).

More interesting example: Either + Writer

Not every two transformers commute, though.

Suppose we want to write log messages, plus to be able to abort the computation.

There are two quite different ways to compose these effects.

There’s

type MyMonad e w a = ErrorT e (Writer w) a

isomorphic to (Either e a, w), and then there’s

type MyMonad e w a = WriterT w (Either e) a

isomorphic to Either r (a, w).

We can already see the difference from the types. In the first case, the w is there independently of the value of Either. In the second case, if the computation failed, the whole thing is Left msg, and we don’t get our log w back.

Let’s try the following to confirm our expectations:

> runWriter $ runErrorT $ tell "foo" >> throwError "err" >> tell "bar"
(Left "err","foo")
> runErrorT $ runWriterT $ tell "foo" >> throwError "err" >> tell "bar"
Left "err"

Developing intuition

When reasoning about a stack of monad transformers, it’s useful to keep in mind that a transformer knows nothing about its inner monad. It has to work “inside” that monad. It has no ability to alter or cancel the effects that happened before in that monad. (It can prevent those effects from happening, though – see tell "bar" above.)

In the first example above, which corresponds to ErrorT e (Writer w), the Error monad had to work inside the Writer monad. It simply had no way to tell the writer monad to “forget” what had been told to it before.

In the second example, corresponding to WriterT w (Either e) a, the main monad is now Either e. If it decides to fail, it will return just the error, and nothing else.

The same logic answers the question why there’s no IOT, an IO monad transformer. Imagine this:

do
    targetHit <- launchMissiles
    when targetHit $
        throwError "oops I did it again"

Since throwError happens in the base monad, the whole thing is just Left "oops I did it again" – nothing mentions any IO. But what about the missiles?

If this shallow explanation is not enough to make you comfortable with transformers, I’d advise to read (or even to write) the implementation of some standard transformers.

Even more interesting example: Parsec + State

The Parsec monad already allows us to have our own state, but let’s see how we can add one independently.

Again, we have two ways to layer ParsecT and StateT transformers on top of Identity: ParsecT s () (State u) a and StateT u (Parsec s ()) a. Is there a difference?

Recall that Parsec is a backtracking monad. It can execute one branch, fail, and then execute another branch. Do we observe the state changes that happened in the aborted branch?

This will be our test code:

((put 1 >> char 'b') <|> char 'a') >> get

We’ll try to run it with the input "a" and initial state 0. First, Parsec executes the left branch of <|>, fails, and proceeds with the right branch. If the state is “global”, then the final result will be 1. If the state is subject to backtracking, then we’ll see 0.

In the ParsecT s () (State u) a case, the base monad is State. ParsecT works inside that monad and cannot revert the effects that happened there. (It may seem that it could remember the state of a branch using get and then restore it using put; but a monad transformer has to be polymorphic in the underlying monad and thus cannot rely on existence of get and put.)

And indeed, the code

import Text.Parsec
import Control.Monad.State

main = print $ flip evalState 0 $ runParserT p () "-" "a"
    where p = ((put 1 >> char 'b') <|> char 'a') >> get

prints Right 1.

Let’s now try the second option: layering StateT on top of Parsec. We cannot use the code above as is, because types do not match: e.g. char 'b' has type Parsec s () Char, but we need StateT u (Parsec s ()) Char. Such an upgrade is done by the lift function.

Sometimes, however, we need to “downgrade” computations from StateT u (Parsec s ()) a to Parsec s () a.

For example, to implement a <|> operator of type

(<|>) :: StateT u (Parsec s ()) a -> StateT u (Parsec s ()) a -> StateT u (Parsec s ()) a

we need first to downgrade the arguments to plain Parsec computation, invoke Parsec’s own <|> and then upgrade the result back to StateT.

import Text.Parsec as P
import Control.Monad.State

main = print $ runParser (evalStateT p 0) () "-" "a"
  where
    p = ((put 1 >> char 'b') <|> char 'a') >> get

    char = lift . P.char

    a <|> b = StateT $ \s ->
        runStateT a s P.<|> runStateT b s

Notice how we explicitly run both branches of <|> with the same state. It’s no surprise now that the state will be “backtracked” and the result will be Right 0. By the way, this is the same result as would be achieved using Parsec’s internal state.