Homework-New/Hasklet2.md

# 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:

  ```Haskell
  do
      (_, s1) <- char '(' s
      (i, s2) <- nat s1
      ...
  ```
  Perhaps this reminds you of the [implementation of the State monad](https://wiki.haskell.org/State_Monad#Implementation)?
  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:

  ```Haskell
  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:

  ```Haskell
  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):

  ```Haskell
  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:

  ```Haskell
  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`:

  ```Haskell
  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.

  ```Haskell
  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 :-)