8.3 KiB
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 afoldr
. 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 thefoldr
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 Cstylex ? 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 shortcircuiting()
operator behaves. I think a simple
would suffice. 
You defined a function
cx
forcontains 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 thecx
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 ifTree
had more cases (which would all have recursive calls). We used this inXtra
to implement the evaluation function for expressions  instead of passing around the environmentenv
, we captured it like we captureda
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 dofoldTree (flip (:)) []
. This makes it easy to express sequential computations, like for instance those forsum
andcontains
. In fact, you can even reuse listbased 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 usefoldTree
to define any function on trees. Consider the simple example ofdepth
, 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. Yourb > 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 usingfoldTree
, 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 mya + b + c
function as((.(+)).(.).(+))
: I was just playing around with pointfree 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 depthn
, doesn't your approach performn
traversals of the tree, once for each depth? This would mean you check1 + (1 + 2) + (1 + 2 + 4) + ...
nodes while running this function, doesn't it?
Ashish
Hey there! I've got some casebycase thoughts about your submission.

In your
containsTree
, you writeif (n == m) then True else ...
. As I mentioned to Ben, this is very similar to writingn == m ? true : false
in C/C++: I'd say it's a bit of an antipattern. Specifically, the shortcircuiting
operator will do exactly that; you can writen == n  ...
, instead. 
There's a slight issue with your
foldTree
function, which is what caused to have trouble withcontainsFold
. 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 yourtreeFold
function to produce the same type of values that are in the tree! This works forsumTreeFold
, because numbers are closed under addition; it doesn't, however, work forcontainsTreeFold
, 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 variableb
alongsidea
. This is strictly more general than using onlya
everywhere:b
can be equal toa
(much likex
andy
can be equal in an equation), but it can also be different. Thus, yoursumTreeFold
would still work, but you'd be able to writecontainsTreeFold
as well. I think Ben's solution is exactly what you were going for, so it doesn't make sense for me to rederive 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 getlowerLevels
? Suppose thatlt
has the levels[1,2], [3,4,5,6]
andrt
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 functionzipWith
from the standard library in Haskell; However, the problem is thatzipWith
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:
Our final function implementation is then: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.
I implemented mine using my customlevels Leaf = [] levels (Node m lt rt) = [m] : lowerLevels where lowerLevels = myZipWith lt rt
fold
, but in essense it works the same way. MymyZipWith
is calledpadded
, but the implementation is identical to what I showed here.
 For a leaf, there are no levels, so your solution would just be