5.5 KiB
Phillip
Hey man, long time no... read? Having seen your comment, I don't have anything exceptionally eyeopening to contribute, but here goes:

At first glance, it seemed like it should be easy to simplify all those 4deep case statements into a single line, but I don't think that's quite the case. I think that if you were to just rewrite the
Maybe
code using Haskell's standard functions, you would need to useMaybe
'sMonad
instance, even though I didn't need it for myApplicative
parser data type. The difference is in the types. The result of a parser application isMaybe (a, String)
, and thatString
argument is used by the next parser.Applicative
, on the other hand, does not support making decisions based on the data inside the functor. The signatures forfmap
and<*>
are(a > b) > f a > f b
andm (a > b) > m a > mb
: you have to have both the function and its arguments before you combine them.On the other hand, when turning Parser into its own data type, the
String
statepassing can be hidden away, so instead ofMaybe (a, String)
you'll just haveParser a
. At the type signature level, you no longer rely on the "state" (leftover string) in your combinators, so you only needApplicative
.In short, with
Maybe
, I think the best you can do is something like the following:do (_, s1) < char '(' s (i, s2) < nat s1 ...
Perhaps this reminds you of the implementation of the State monad? My intuition is that a Parser is just a combination of the
State
andError
monads. 
I think that your implementation of
natPair
andnatTree
could be refactored a little bit. In particular, you can abstract the code for parsing "two things in parentheses separated by a comma", perhaps into a function likepair :: Parser a > Parser b > Parser (a, b)
. If you did that, your 4deep chain of case analysis would only occur in one place (inpair
), and your other two functions would just call out to it. Applying just this refactoring step, you'd get:natPair = pair nat nat natTree s = case pair natTree natTree s of Just ((t1, t2), s') > Just $ (Node t1 t2, s') Nothing > case nat s of Just (n, s') > Just $ (Leaf n, s') Nothing > Nothing
This has all the usual benefits of abstraction which I won't bore you with :)
Jack
Hey, sorry to see you didn't have time to finish up natTree
. I've got a few comments:

Your
(<>)
implementation is actually nearly identical toMaybe
's implementation ofAlternative
's(<>)
. In particular, you're effectively (lazily) combining twoMaybe
values, one fromp1
and one fromp2
. Thus, you can actually write that whole function asp1 (<>) p2 = \s > p1 s (<>) p2 s
. Well, except that then you have an ambiguous reference to(<>)
, so you have to qualify it, likeControl.Applicative.(<>)
. 
You probably know this, but your helper functions
parseMap
,ifTranP
, andaddP
are specializations of the standard functionsfmap
,(>>=)
, andliftA2
. In particular,addP
is pretty muchliftA2 (:)
. This does, of course, rely on theFunctor
,Monad
, andApplicative
instances being defined for theParser
data type, which requires a bit of handywork given the starter code. The advantage, though, is getting access to all these fancy combinators from the standard library (like*>
and<*
). Similarly, your\s > Just ([], s)
could be written asreturn []
. 
Our
nat
functions are practically identical! I went with pointfree style again (I have a bit of a problem, pointfree is not very readable at all), but other than that, it's scary how close our answers are! 
The whole "early return" pattern (check for
Just
, compute nextMaybe
, check forJust
again) can at the very least be simplified as:natPair s1 = do (_, s2) < char '(' s1 (first, s3) < nat s2 (_, s4) < char ',' s3 (second, s5) > case nat s4 (_, s6) < char ')' s5 return $ ((first, second), s6)
But wait a moment... we didn't actually do anything with the values of
first
andsecond
! This means that we can generalize this function just a little bit (replacenat
but an arbitrary input parser):pair p1 p2 s1 = do (_, s2) < char '(' s1 (first, s3) < p1 s2 (_, s4) < char ',' s3 (second, s5) > case p2 s4 (_, s6) < char ')' s5 return $ ((first, second), s6)
Now,
natPair
can be written aspair nat nat
(you can even verify this by some straightforward equational reasoning). And now that you have that, you can also definenatTree
. The first version:natTree = pair natTree natTree
Alas, this is of type
Parser (Tree, Tree)
, notParser Tree
. To combine the two trees into one, we can use yourparseMap
:natTree = parseMap (uncurry Node) (pair natTree natTree)
Oh, but we're missing a base case! We can use the
(<>)
operator we defined earlier to define a "fallback" if we can't parse another level of the tree.natTree = parseMap (uncurry Node) (pair natTree natTree) <> parseMap Leaf nat
Two birds with one stone, right? Both
natPair
andnatTree
knocked out by a singlepair
function. It's true that definingnatPair
is quite messy, and hard to expand intonatTree
, but stuffing all that complexity into a helper function helps keep that messiness at bay :)