Phillip

Hey man, long time no... read? Having seen your comment, I don't have anything exceptionally eye-opening to contribute, but here goes:

At first glance, it seemed like it should be easy to simplify all those 4-deep 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 use Maybe's Monad instance, even though I didn't need it for my Applicative parser data type. The difference is in the types. The result of a parser application is Maybe (a, String), and that String 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 for fmap and <*> are (a -> b) -> f a -> f b and m (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 state-passing can be hidden away, so instead of Maybe (a, String) you'll just have Parser a. At the type signature level, you no longer rely on the "state" (leftover string) in your combinators, so you only need Applicative.

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 and Error monads.
I think that your implementation of natPair and natTree 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 like pair :: Parser a -> Parser b -> Parser (a, b). If you did that, your 4-deep chain of case analysis would only occur in one place (in pair), 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 to Maybe's implementation of Alternative's (<|>). In particular, you're effectively (lazily) combining two Maybe values, one from p1 and one from p2. Thus, you can actually write that whole function as p1 (<|>) p2 = \s -> p1 s (<|>) p2 s. Well, except that then you have an ambiguous reference to (<|>), so you have to qualify it, like Control.Applicative.(<|>).
You probably know this, but your helper functions parseMap, ifTranP, and addP are specializations of the standard functions fmap, (>>=), and liftA2. In particular, addP is pretty much liftA2 (:). This does, of course, rely on the Functor, Monad, and Applicative instances being defined for the Parser 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 as return [].
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 next Maybe, check for Just 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 and second! This means that we can generalize this function just a little bit (replace nat 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 as pair nat nat (you can even verify this by some straightforward equational reasoning). And now that you have that, you can also define natTree. The first version:
```
natTree = pair natTree natTree
```
Alas, this is of type Parser (Tree, Tree), not Parser Tree. To combine the two trees into one, we can use your parseMap:
```
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 and natTree knocked out by a single pair function. It's true that defining natPair is quite messy, and hard to expand into natTree, but stuffing all that complexity into a helper function helps keep that messiness at bay :-)

5.5 KiB Raw Permalink Blame History

Phillip

Jack

5.5 KiB

Raw Permalink Blame History