Homework-New/Hasklet1.md

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

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:

  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.