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.