Posted on 2017-06-16
by Oleg Grenrus

*Haskell Programming from first principles* - aka `haskellbook`

"misses" a simple, yet hopefully insightful exercise about `Alternative`

(introduced in Parser Combinators chapter). I have discovered this one, while working on a real world project:

**Exercise** Write a function with following signature:

```
count' :: Alternative f
=> Int -- ^ minimum count
-> Int -- ^ maximum count
-> f a
-> f [a]
```

`f`

could be a regular expression `RE`

from `regex-applicative`

package, in that case `count' n m re`

should work as `(re){n,m}`

in a traditional regexp syntax. In other words accept `n`

to `m`

occurrences of `re`

.

```
lambda> "a" =~ count' 2 3 (sym 'a')
Nothing
lambda> "aa" =~ count' 2 3 (sym 'a')
Just "aa"
lambda> "aaa" =~ count' 2 3 (sym 'a')
Just "aaa"
lambda> "aaaa" =~ count' 2 3 (sym 'a')
Nothing
lambda> "ab" =~ count' 2 3 (sym 'a')
Nothing
```

## Notes, hints and follow-ups

IF the exercise feels to hard to crack directly, there are few notes, hints and also few follow-ups.

### Negative numbers

If `n < m`

, e.g. `count' 2 1`

, you may return `empty`

, or accept exactly `2`

values. FWIW: JavaScript throws an exception: `Invalid regular expression: /^a{3,2}$/: numbers out of order in {}`

, let's not do that.

Also in the following sub-exercises, treat negative numbers properly: write

```
foo n | n < 0 = ... -- not n == 0, or foo 0
| otherwise = ... foo (n - 1)
```

This will save you from the infinite recursion when negative numbers are passed in.

### some and many

The definition of `many`

and `some`

in `base`

library are slightly complicated:

```
-- | One or more.
some :: f a -> f [a]
some v = some_v
where
many_v = some_v <|> pure []
some_v = (fmap (:) v) <*> many_v
-- | Zero or more.
many :: f a -> f [a]
many v = many_v
where
many_v = some_v <|> pure []
some_v = (fmap (:) v) <*> many_v
```

Write `many`

as a one-liner, using `<$>`

, `<*>`

and `<|>`

.

*Note:* `<$>`

and `<*>`

bind tighter than `<|>`

, so you can write expressions like `fun <$> with <*> parsers <|> foo <$> bar <*> quux`

, which is grouped as `(fun <$> with <*> parsers) <|> foo <$> bar <*> quux)`

.

### Exact count

A small step towards the goal is to write simpler function first:

```
count :: Alternative f
=> Int -- ^ exact count
-> f a
-> f [a]
```

That should accept the exact amount of parses. `count n re = count' n n re`

≈ `(re){n}`

in traditional regex notation.

```
lambda> "aaa" =~ count 3 (sym 'a')
Just "aaa"
```

### upto

Another variant with the same type-signature (!):

```
upto :: Alternative f
=> Int -- ^ up to this amount
-> f a
-> f [a]
```

This should accept *upto* some amount of parses. `upto n re = count' 0 n re`

≈ `(re){n}`

in traditional regex notation.

### Divide and conquer

Now, when you have defined `count`

and `upto`

, you can define `count'`

as simply as:

`count' n m p = (++) <$> count n p <*> upto (m - n) p`

GHC is smart, but not super-smart. Let's help it. Inline definition of `count`

, removing the use of (++) from above definition.

### Order of alternatives

Virtually every parser combinator library is left-biased, in other word the left hand side of `<|>`

is preferred. Explain what's the behavioral difference between

```
pure [] <|> some p
some p <|> pure []
```

Analyze your `count'`

, `count`

and `upto`

definitions, and try examples above with your backtracking parser-combinator library of choice (e.g. `trifecta`

). Do they work as expected?

### Counting other Alternatives

There are also other `Alternative`

s than parsers. For example `[]`

and `STM`

. Explain to your colleague what `count'`

does for `[]`

and `STM`

. If there are other interesting `Alternative`

s, where `count'`

does something neat, please tell me! (e.g. via Twitter).

## Solution

Fortunately, `parser-combinators`

package by Mark Karpov provides `count`

and `count'`

, so you could use them in your code, and check *the source* for one way of solving this exercise.

Site proudly generated by Hakyll