# Parsec for primes and fibs

I decided to spend some time working with parsec. I've written some code to check for primality and for whether something is a Fibonacci number. I'm mainly hoping for feedback on readability, but if you have any performance tips I'd be interested in those as well.

import Text.Parsec
import Text.Parsec.Error
import Control.Applicative hiding ((<|>))

toXTerminatedAs :: Int -> String
toXTerminatedAs = end . parse (manyAccum acc digit) "" . show
where acc digit cur = concat (replicate 10 cur) ++ toAs digit
toAs digit    = replicate (fromEnum digit - 48) 'a'
end (Left _)  = error "I can't deal with negative numbers, sorry"
end (Right x) = x ++ "x"

isLeft :: Either a b -> Bool
isLeft (Left _) = True
isLeft _        = False

fib :: Int -> Bool
fib = not . isLeft . parse (fibParser "a" "") "" . toXTerminatedAs

fibParser a b = char 'x' <|> (\_ -> fibParser b (a++b)) =<< string a

prime :: Int -> Bool
prime = isLeft . parse (char 'x' <|> primeParser "a") "" . tail . toXTerminatedAs

primeParser x = (\c -> try (many1 (string (c:x)) *> char 'x') <|> primeParser (c:x)) =<< char 'a'


toXTerminatedAs is pretty ugly, but I haven't been able to think of any improvements. As the name/signature implies it turns a number n into n 'a's followed by an x.

prime works for all natural numbers, but it returns True for 0, and I'm not really sure what to do about it besides hard-coding it in somewhere.

• My honest opinion is that this is both a poor way to learn about parsing and an incredibly baroque way to write a primality test, why don't you try writing a CSV parser or something instead? I can't for the life of me understand what you're trying to do here or why it would involve Parsec. This is taking me some serious effort to read because it is just so weird. Commented Feb 4, 2015 at 10:35
• @bisserlis yeah, some of it is kind of strange. The fibParser "a" "" might look wrong. (Like it should be fibParser "" "a") but since the offsets between fibs are fibs shifted right by 1.5, you have to extend the sequence a bit to the left and use 1,0 as your starting values. And the reason why I drop the first character of the value in prime is that I need to start by dividing into 2's, but my primeParser only consumes one 'a' at a time. Commented Feb 4, 2015 at 11:07
• @bisserlis If you think it's bad enough that it couldn't attract useful answers I'll delete it. Commented Feb 4, 2015 at 11:11
• You seem to have missed @bisserlis 's main point, genisage. You have conflated two unconnected things in both your premise and your code. The notion of mixing parsing into arithmetic is just bizarre. And we can't work out why you have chosen to do this because how you are doing it seems to make no sense at all. Commented Feb 4, 2015 at 12:59
• prime 0 = false isn't naughty "hard coding", by the way. It's using pattern matching to deal with an edge condition. Although you need to deal with negative numbers as well, so it should really be prime x | x < 1 = false | otherwise = your stuff here Commented Feb 4, 2015 at 13:54

# Parsers are for parsing

This is probably the strangest primality test I've ever seen. So for those that want to write their own primality test, please don't use this approach.

Almost all your functions can be written without a Parser. toXTerminatedAs is probably the best example:

toXTerminatedAs :: Int -> String
toXTerminatedAs n = replicate n 'a' ++ "x"


That's easy to read, and more likely to be correct. Either way, I assume you know that, so let's get started with the actual review.

# Try not to shadow existing names

We return to toXTerminatedAs:

toXTerminatedAs :: Int -> String
toXTerminatedAs = end . parse (manyAccum acc digit) "" . show
where acc digit cur = concat (replicate 10 cur) ++ toAs digit
toAs digit    = replicate (fromEnum digit - 48) 'a'
end (Left _)  = error "I can't deal with negative numbers, sorry"
end (Right x) = x ++ "x"


We have three digits here. Two of them are function arguments, but the first one is Parsec's digit function. That's misleading. Use d or another name that's not already in use. Alternatively, import Parsec qualified or as P to show the difference more clearly.

# Use the standard library

We stay at toXTerminatedAs. fromEnum digit - 48 isn't that clear to someone who doesn't know Enum instances or 48 well. But digitToInt shows its intend very well. It's provided by Data.Char:

import Data.Char

-- ....

toXTerminatedAs :: Int -> String
toXTerminatedAs = end . parse (manyAccum acc digit) "" . show
where acc d cur     = concat (replicate 10 cur) ++ toAs d
toAs d        = replicate (digitToInt d) 'a'
end (Left _)  = error "I can't deal with negative numbers, sorry"
end (Right x) = x ++ "x"


isLeft is provided by Data.Either, so no reason to implement it yourself.

Also, try to avoid ++ in recursive functions or accumulators, as it turns $\mathcal O(n)$ algorithms into $\mathcal O(n^2)$ ones.

# Encapsulate often used functionality in a function

You often use parse parser "". That's somewhat error prone as you can accidentally forget the file name.

Instead write a small function that takes care of the SourceName for you:

parse' :: Stream s Identity t => Parsec s () a -> s -> Either ParseError a
parse' p = parse p ""


While we're at it, we add a

parseViaX p = isLeft . parse' p . toXTerminatedAs


parseViaX is missing its type signatures because I don't know the ones of fibParser and primeParser. Always add type signatures to top-level bindings. Not only will it serve as minimal documentation, but it will also make sure that the compiler does not infer too general types or types you didn't expect.
fibParser and primeParser should get some documentation.
Don't mix parsing and arithmetic, at least for arithmetic tests. It's messy and hard to read. Both fib and prime are easy to write without any parsing at all.