Comments for 2018-10-20

[BartoszMilewski]

It was a very different meeting. We started by putting a Haskell beginner on the spot, asking him to implement a binary tree on the whiteboard. It was a lot of fun, as everybody was trying to help, finding the best way to explain recursion. We managed to implement a recursive evaluator. Then a question was asked about implementation: In a multi-leaf tree, is there only one leaf or are leaves duplicated? That lead to the discussion about argument passing. We discussed pass-by-value, pass-by-name, and pass-by-need. There was an interesting digression about how pass-by-need interacts with concurrency. Finally, we talked about how a seasoned Haskell programmer would approach the same problem, possibly using recursion schemes. So we talked about Foldable and went step-by-step through the implementation of foldr (again, with a volunteering beginner). I liked the fact that everybody seemed to be engaged, independent on their level of expertise. I'd like to see this kind of directed exploration interspersed with prepared talks as the way to proceed in the future. What do you think?

[dc25]

At some point in the discussion we had written down on the whiteboard an O(n) implementation of toList for a tree structure. If anyone wrote down, or remembers, or just knows that algorithm would you please post it here? Thank you.

[bascarsija]

RE: the O(n) solution, i think the key was to ensure that each of the O(n) append operations takes O(1) time, which, assuming a cons cell implementation of a list (i.e. fixed tail), would be specifically be appending at the the head rather than at the tail, as the latter would itself require O(n) work to copy each cell into a new list (due to the newly changed tail) for each of the O(n) append operations.