3 ms·

I don't understand "no explicit recursion". How do you do any kind of binary tree search without recursion?

abecedarius 9y ago
This is in contrast with structural recursion. When you define a binary tree datatype you should get for free a generic fold operation on these trees, analogous to the map and reduce functions on lists. I don't know if Clojure gives you that.
MiyamotoAkira 9y ago
The people that talked about the rules at Codurance was none of the people that defined the original rules. We had to "reverse engineer" the thinking, find reasons and then discard, change or let as they were (one of the objectives of the write up was to put down those reasons). Explicit recursion did take a while. The reasoning we came with is to learn to use map/reduce functions (do take into account that our group has an ecletic knowdledge of FP and hybrid languages: Clojure, Haskel, Elixir, Scala, F#, ...). Can that binary search tree be converted into a linear search if you rearrange the tree into a list? Yes. Now you can use map /reduce. Is it performant? Most probably not. Are there other ways? Time to discover. Interestingly, most of the katas/exercises on which we are practicing these rules are not heavily algorithmic in nature. Maybe we do need to add some to understand better and modify the "rules" with the new knowledge.
- CJefferson 9y ago
  If you want an example, consider writing a simple recursive sudoku solver, where at each location you fill in one empty square with the values 1-9, and reject early if you ever have a repeated value in a row, column or box. This is easy to write in C, and I always imagined would be something functional programming would excel at, but it doesn't seem to fit with your rules.
  - MiyamotoAkira 9y ago
    SOLD!!!!! I will have to add this to my kata collection. That also reminds me of the 8-queen problem. The last solution that I created (C#) years ago did use recursion.
danidiaz 9y ago
Here is an answer in the CS Theory Stack Exchange that explains how: https://cstheory.stackexchange.com/a/18399/13730 https://cstheory.stackexchange.com/a/18399/13730 (I'm not endorsing it as a practical way of doing it, mind you.) The idea is that the only explicit recursion is contained in generic combinators "fold_result" and "unfold_result" that are "boring" in the sense that they can be derived mechanically from the "resultF" data type and do not actually know about the binary search; they just do recursion. In practice, folds and unfolds tend to be more useful for other things.
- MiyamotoAkira 9y ago
  In fact, a colleague that is reading SICP at the moment is the one that basically put the idea forward, as he was going through the whole idea of fold/map/unfold on the book exercises

This is in contrast with structural recursion. When you define a binary tree datatype you should get for free a generic fold operation on these trees, analogous to the map and reduce functions on lists. I don't know if Clojure gives you that.

MiyamotoAkira 9y ago

The people that talked about the rules at Codurance was none of the people that defined the original rules. We had to "reverse engineer" the thinking, find reasons and then discard, change or let as they were (one of the objectives of the write up was to put down those reasons). Explicit recursion did take a while. The reasoning we came with is to learn to use map/reduce functions (do take into account that our group has an ecletic knowdledge of FP and hybrid languages: Clojure, Haskel, Elixir, Scala, F#, ...). Can that binary search tree be converted into a linear search if you rearrange the tree into a list? Yes. Now you can use map /reduce. Is it performant? Most probably not. Are there other ways? Time to discover. Interestingly, most of the katas/exercises on which we are practicing these rules are not heavily algorithmic in nature. Maybe we do need to add some to understand better and modify the "rules" with the new knowledge.

CJefferson 9y ago
If you want an example, consider writing a simple recursive sudoku solver, where at each location you fill in one empty square with the values 1-9, and reject early if you ever have a repeated value in a row, column or box. This is easy to write in C, and I always imagined would be something functional programming would excel at, but it doesn't seem to fit with your rules.
- MiyamotoAkira 9y ago
  SOLD!!!!! I will have to add this to my kata collection. That also reminds me of the 8-queen problem. The last solution that I created (C#) years ago did use recursion.

danidiaz 9y ago

Here is an answer in the CS Theory Stack Exchange that explains how: https://cstheory.stackexchange.com/a/18399/13730 https://cstheory.stackexchange.com/a/18399/13730 (I'm not endorsing it as a practical way of doing it, mind you.) The idea is that the only explicit recursion is contained in generic combinators "fold_result" and "unfold_result" that are "boring" in the sense that they can be derived mechanically from the "resultF" data type and do not actually know about the binary search; they just do recursion. In practice, folds and unfolds tend to be more useful for other things.

MiyamotoAkira 9y ago
In fact, a colleague that is reading SICP at the moment is the one that basically put the idea forward, as he was going through the whole idea of fold/map/unfold on the book exercises