2021-04-17 02:40:32 -07:00

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

``````data Tree a = Leaf a | Node (Tree a) (Tree a)
``````

You could then define a `containsTree` function like this:

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

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

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

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

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