Homework-New/Hasklet1.md

145 lines
8.3 KiB
Markdown

# Ben
I was surprised to see how different our solutions were! Usually for "day 1" exercises,
most answers come out pretty similar, especially for people who feel pretty comfortable
with Haskell. But hey, more things to talk about!
* In your `sumTree`, you used a `foldr`. To me, this is kind of weird -
I see your "or ..." comment, and I much prefer the version there which
uses a simple summation. Setting aside whatever magic optimiztions
GHC has in store for us, the version you have uncommneted
will create an intermediate list, and possibly also
an unevaluated "thunk" of the `foldr` application
(instead of just adding numbers). It seems like a lot of work,
and is, in my opinion, _less_ expresive than the "simple" version.
* In your `containsTree`, you have the following: `| x == y = True`.
This is reminiscent of a C-style `x ? true : false`. I would say this
is an antipattern - returning true of something is the case, and
trying another condition of it's not, is exactly the way that a short-circuiting
`(||)` operator behaves. I think a simple `||` would suffice.
* You defined a function `cx` for `contains x`. This is quite cool: it helps
save on a lot of repetition! In this case, I think it's less valuable:
there's a maxim that I heard, "if you need to write something twice,
cringe and write it twice. If you need to write something more than that,
abstract it". In this case, I think the `cx` abstraction is not worth the effort.
Haskell's effortless creation of closures is pretty cool, though: suppose
that it was the _leaves_ that contained data (such an example would be more convincing):
```Haskell
data Tree a = Leaf a | Node (Tree a) (Tree a)
```
You could then define a `containsTree` function like this:
```Haskell
containsTree :: Eq a => a -> Tree a -> Bool
containsTree a = ct
where
ct (Leaf x) = a == x
ct (Node l r) = ct l || ct r
```
Note that here we no longer need to pass around the `a` in recursive calls.
This would become especially good if `Tree` had more cases (which would all have recursive
calls). We used this in `Xtra` to implement the evaluation function for expressions -
instead of passing around the environment `env`, we captured it like we captured `a` in the above example.
* You defined your `foldTree` differently from the way I did it. As Eric said, there are multiple
approaches to doing this, so I wouldn't say either of us is wrong. Tradeoff wise, your solution
imposes an order on the elements of the tree: in effect, it converts them to a flat list:
you can _really_ see this if you do `foldTree (flip (:)) []`. This makes it easy to express
sequential computations, like for instance those for `sum` and `contains`. In fact, you can
even re-use list-based functions like so:
```Haskell
toList = foldTree (flip (:)) []
sumTree = sum . toList
containsTree a = contains a . toList
```
In short, your approach makes it really easy to express some computations. However, unlike
`fold` for lists, you cannot use `foldTree` to define any function on trees. Consider
the simple example of `depth`, and two trees:
* `Node 1 (Node 2 (Node 3 Leaf Leaf) Leaf) Leaf`
* `Node 1 (Node 2 Leaf Leaf) (Node 3 Leaf Leaf)`
If you run them through `toList`, you'll notice that they produce the same result. Your
`b -> a -> b` function is seeing the exact same order of inputs. However, the trees obviously
have different depth: the first one has depth 2, and the second has depth 3.
My approach is different: I aimed to define the most general function on trees. I think that
this is called a catamorphism. Were you there on the day we read the _Bananes, Lenses and Barbed
Wire_ paper in reading group? It's like that. This ends up with a different signature than
the `fold` for lists, but it makes it possible to define _any_ function for lists. For example,
here's that depth function I mentioned earlier:
```Haskell
depth = foldTree (\_ l r -> 1 + max l r) 1
```
And, of course, my `levels` function is also implemented using `foldTree`, though
I did need to define an auxillary function for zipping lists. This has the downside
of making some "linear" code (like summations and "contains") look a little
uglier. My function parameters were `(\a b c -> a + b + c)` and `(\a b c -> a == n || b || c)`
for sum and contains respectively, and that's a little less pretty than, say, `(+)`.
Don't mind that I wrote my `a + b + c` function as `((.(+)).(.).(+))`: I was
just playing around with point-free style.
Interestingly, if you recall Church encoding from CS 581, you will notice that
the "type" of a Church encoded list is `(a -> b -> b) -> b -> b`, and
the type of a Church encoded tree as ours is `(a -> b -> b -> b) -> b -> b`.
There's a connection between the representation of our data structure and
the most general function on that data structure.
* I didn't think of your approach to `levels`! I have a question about it,
though: For a complete tree of depth `n`, doesn't your approach perform
`n` traversals of the tree, once for each depth? This would mean you
check `1 + (1 + 2) + (1 + 2 + 4) + ...` nodes while running this function,
doesn't it?
# Ashish
Hey there! I've got some case-by-case thoughts about your submission.
* In your `containsTree`, you write `if (n == m) then True else ...`. As I mentioned
to Ben, this is very similar to writing `n == m ? true : false` in C/C++: I'd
say it's a bit of an antipattern. Specifically, the short-circuiting `||` operator
will do exactly that; you can write `n == n || ...`, instead.
* There's a slight issue with your `foldTree` function, which is what caused
to have trouble with `containsFold`. Take a look at your signature:
```Haskell
foldTree :: (a -> a -> a) -> a -> Tree a -> a
```
Note the very last part: `Tree a -> a`. This means that you can only
use your `treeFold` function to produce _the same type of values that
are in the tree_! This works for `sumTreeFold`, because numbers are closed
under addition; it doesn't, however, work for `containsTreeFold`, since
even if your tree contains numbers, you'd need to produce a boolean,
which is a different type! The simple solution is to introduce a type variable `b`
alongside `a`. This is strictly more general than using only `a` everywhere:
`b` can be equal to `a` (much like `x` and `y` can be equal in an equation),
but it can also be different. Thus, your `sumTreeFold` would still work,
but you'd be able to write `containsTreeFold` as well. I think Ben's
solution is exactly what you were going for, so it doesn't make sense for
me to re-derive it here.
* I'm really having trouble understanding your attempted solution for `levels`.
If you're strill trying to figure it out, here's how I'd do it.
* For a leaf, there are no levels, so your solution would just be `[]`.
* For a node in the form `Node n lt rt`, your solution would
have the form `[n] : lowerLevels`. But how do you get `lowerLevels`?
Suppose that `lt` has the levels `[1,2], [3,4,5,6]` and `rt` has the levels
`[7, 8], [9, 10, 11, 12]`. You want to combine each corresponding level:
`[1,2]` with `[7,8]`, and `[3,4,5,6]` with `[9,10,11,12]`. This is
_almost_ like the function `zipWith` from the standard library in Haskell;
However, the problem is that `zipWith` stops recursing when the shorter list
runs out. We don't want that: even if the left side of the tree has no more levels,
if the right side does, we want to keep them. Thus, we define the following function:
```Haskell
myZipWith :: [[a]] -> [[a]] -> [[a]]
myZipWith [] [] = [] -- two empty lists means we've run out of levels on both ends, so we're done.
myZipWith (l:ls) (m:ms) = (l ++ m) : myZipWith ls ms -- Combine the first levels from both lists, and recurse.
myZipWith [] ls = ls -- We ran out of levels on the left, so only the right levels occur from here on.
myZipWith ls [] = ls -- We ran out of levels on the right, so only the left levels occur from here on.
```
Our final function implementation is then:
```Haskell
levels Leaf = []
levels (Node m lt rt) = [m] : lowerLevels
where lowerLevels = myZipWith lt rt
```
I implemented mine using my custom `fold`, but in essense it works the same way. My `myZipWith` is
called `padded`, but the implementation is identical to what I showed here.