Timeline for What are the functional equivalents of imperative break statements and other loop checks?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 4, 2018 at 0:40 | comment | added | leftaroundabout | @8bittree I didn't really intend to single out tail recursion. As J_mie6 argued, general recursion might be what should be considered analogous to GOTO. However, and that's where I'm coming from here, well-written non-tail- recursive code tends to not be such ”pathologically recursive”. On the contrary, functional programmers like to lay out their code in such a way that the defining equations almost spell out the invariants. But this is not enforced by the recursion mechanism per se (unlike with loops, which do constrain the amount of nonsense the programmer can commit). | |
| Jan 3, 2018 at 23:08 | comment | added | 8bittree |
@leftaroundabout That raises some questions, such as: Why do you think GOTO is bad? (To be clear, I'm not making any claim here on whether it's good or bad. I just want to know your reasoning.) Why do you single out tail recursion, and not include recursion in general, tail calls in general, or function calls in general (or do you include some or all of those, if so, why?)?
|
|
| Jan 3, 2018 at 17:27 | comment | added | Doval | @J_mie6 The recursive equivalent of your "traditional for loop" also has a start, an end, and a deterministic step, and it's easy to show through induction that it'll stop. | |
| Jan 3, 2018 at 12:19 | comment | added | leftaroundabout | ... As for folds: you're right, a traditional fold (catamorphism) is a very specific kind of loop, but these recursion schemes can be generalised (ana- / apo- / hylomorphisms); collectively these are IMO the proper replacement for imperative loops. | |
| Jan 3, 2018 at 12:19 | comment | added | leftaroundabout |
@J_mie6 the reason I consider tail recursion more as a GOTO is that you need to do fiddly bookkeeping of what arguments in what state are passed to the recursive call, to ensure it actually behaves as intended. That is not necessary to the same degree in decently written imperative loops (where it's pretty clear what the stateful variables are and how they change in each iteration), nor in naïve recursion (where usually not much is done with the arguments, and instead the result is assembled in a quite intuitive way). ...
|
|
| Jan 3, 2018 at 11:05 | comment | added | J_mie6 |
cont: By that I mean that a fold has a deterministic number of iterations. For any given list, you know exactly how many iterations that "loop" takes. So a fold is like a traditional for loop (in the sense that it has a start, an end and a deterministic step), and a tail recursive function is like a while loop, where it is undecidable now long it takes to compute. In terms of raw power then, the unrestricted recursion is the real GOTO
|
|
| Jan 3, 2018 at 11:02 | comment | added | J_mie6 |
@leftaroundabout I'd disagree actually. I'd say tail recursion is more constrained than a goto, given the need to jump to itself and only in tail position. It is fundamentally equivalent to a looping construct. I'd say recursion in general is equivalent to GOTO. In any case, when you compile tail recursion it mostly just boils down to a while (true) loop with the function body in where early return is just a break statement. A fold, whilst you are correct about it being a loop, is actually more constrained than a general looping construct; it is more like a for-each loop
|
|
| Jan 3, 2018 at 10:28 | comment | added | leftaroundabout |
@JörgWMittag I'd rather say tail recursion is the functional equivalent to GOTO. (Not quite as bad, but still pretty awkward.) The equivalent to a loop, as Jules says, is a suitable fold.
|
|
| Jan 3, 2018 at 8:15 | comment | added | Jörg W Mittag | Yep. The functional equivalent to a loop is tail-recursion, and the functional equivalent to a conditional is still a conditional. | |
| Jan 3, 2018 at 7:41 | history | answered | Euphoric | CC BY-SA 3.0 |