Control.Applicative not only defines the
Alternative type classes, it also offers some useful combinators to express how often an action should be run:
many takes an action and runs it zero or more times, collecting the results in a list. Function
some does the same but performs the action at least once. Finally, there is
optional which performs its argument action zero or one time, returning a
Control.Replicate separates such replication schemes from the actual action. It, too, defines a
opt, but to actually run an action
x that many times, we give the scheme and the action in question to the run operator
*! (read: times) like so:
many *! x,
some *! x,
opt *! x.
Why is this useful? Well, it turns out that these replication schemes are highly composable, in standard ways. They themselves are instances of
Alternative. With these combinators, we can sum them, multiply them, and indicate choice, respectively. Let’s look at some examples.
Atomic building blocks
The primitive, atomic building blocks are
one. If we pass these to
*!, the action is not run at all, or run exactly once. Their types are:
zero :: b -> Replicate a b one :: Replicate a a (*!) :: Alternative f => Replicate a b -> f a -> f b
The schemes are represented by type constructor
Replicate. If we look at the type of
*!, we can see that
Replicate‘s first type parameter indicates the result type of the action, while its second type parameter indicates the type of the result after running that action so many times. In the case of
one, the two arguments are identical. In the case of
zero, the scheme will not run the action at all but it still needs to produce a
b. This is why
zero takes an argument of type
Applicative. We can create
three, the schemes that run an action exactly two and three times, using
one as building block:
two :: Replicate a (a, a) two = (,) <$> one <*> one three :: Replicate a (a, a, a) three = (,,) <$> one <*> one <*> one
Look at their result types: the tuples indicate precisely how many times the action is run. You can read
<*> as plus: 2 = 1 + 1, 3 = 1 + 1 + 1.
pure is also defined for schemes. The identity element of addition is 0, and this is exactly what
pure means. It is a synonym for the
zero we saw earlier.
Schemes also form a
Category. We can use it to multiply them. Here are two examples:
twiceThree :: Replicate a ((a, a, a), (a, a, a)) twiceThree = two . three thriceTwo :: Replicate a ((a, a), (a, a), (a, a)) thriceTwo = three . two
In both cases an action is run six times, but their results are nested differently. We will see another multiplication example in a moment.
The identity element for multiplication is 1. Scheme
one exactly matches the type of function
id in the
Category type class.
Until now the examples have only seen schemes for running an action exactly so many times. But schemes are
Alternative and can encode multiple frequencies. This is how
opt, the scheme that runs an action zero or one times, is defined:
opt :: Replicate a (Maybe a) opt = zero Nothing <|> Just <$> one
some also use choice:
many :: Replicate a [a] many = zero  <|> some some :: Replicate a [a] some = (:) <$> one <*> many
We now have many ways to combine replication schemes, and if we use choice together with sums or products, it’s not always immediately clear what the resulting scheme means. That’s why the module also exposes a function
sizes which lists the frequencies a scheme allows:
> sizes one  > sizes two  > sizes opt [0,1] > take 10 (sizes many) [0,1,2,3,4,5,6,7,8,9] > take 10 (sizes some) [1,2,3,4,5,6,7,8,9,10]
In this sense, the schemes encode sets of Peano literals, and
<|> computes the union of two sets.
Now it’s also clear what the
empty scheme is: the scheme that doesn’t allow an action to occur with any frequency; not even zero times.
> sizes empty 
As promised, another example that uses multiplication:
even :: Replicate a [(a, a)] even = many . two > take 10 (sizes even) [0,2,4,6,8,10,12,14,16,18]
This scheme allows all even occurrences of an action, and its type reflects that exactly: there is no way to capture an odd number of
Another combinator available in the module is
between :: Int -> Int -> Replicate a [a], which limits the frequency of an action to a lower and upper bound:
> sizes (between 5 10) [5,6,7,8,9,10]
What frequencies does
(,) <$> between 3 5 <*> two allow? Let’s check:
> sizes ((,) <$> between 3 5 <*> two) [5,6,7]
This makes sense: if we run an action 3, 4 or 5 times and then another two times, we’ve run it 5, 6 or 7 times.
between 7 9 . three mean? What about
three . between 7 9?
> sizes (between 7 9 . three) [21,24,27] > sizes (three . between 7 9) [21,22,23,24,25,26,27]
If the schemes become a bit more involved, it can be helpful to think about them as dice throws. Then
between 7 9 . three means: throw a die with 7, 8 and 9 eyes on it, and use the outcome to decide how many times to throw a die with exactly 3 eyes. This has possible outcomes [9,12,15].
In the other case, we throw die
between 7 9 three times, ending up with the full range 21-27 as possible outcomes.
Currently if you try to evaluate
sizes (many . opt), the program hangs. This is true not for just
opt but for any scheme that allows frequency zero. Is there a bug in the definitions of the combinators, or is it unreasonable to expect the library to produce output in this case?
Another problem is that
sizes (id . r) takes longer than just
r for no apparent good reason. (Try
r = exactly 1000.) Perhaps some profiling will show what the problem here is.
It seems that `sizes (exactly n)` already needs time quadratic in n. I think this is caused by the call to fmap, there will be n calls to fmap, each of which runs over the entire list of n things. Other things exhibit even worse scaling, such as `sizes (some . some)`
It might be better to do fmap lazily somehow, for example by storing in `Cons` a function that will be applied to the final result. Something like
data Replicate a b = Nil | forall c. Cons (c -> b) (Maybe c) (Replicate a (a -> c))
I have not yet tried whether this will work.
Also note that a value of type `Replicate a b` is equivalent to a subset of the naturals, plus for each element of this set a function of that many as to b. Your type already tries to capture this, but maybe the function and the subset could be stored separately?
The following, from your blog entry:
> sizes (between 7 9 . three)
didn’t seem right. Sure enough, with your package:
> sizes (between 7 9 Control.Category.. three)
Thanks, Dean! Fixed it.
Thank you Twan, that does seem to work.
Leave a comment!
Martijn loves to receive comments! Add yours by filling out the fields below.