Is this Haskell Tower of Hanoi solution more efficient or simply redundant?
up vote
1
down vote
favorite
This Haskell solution has been described as recursive, but not quite efficient according to a few claims, so I have tried to rewrite it with that in mind. The problem is described in a course that is available online and whose homework was the Tower of Hanoi.
A new solution of mine:
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ l = l
-- hanoiToList 1 a b _ l = (a, b) : l
hanoiToList n a b c l = hanoiToList (n-1) a c b ((a, b) : hanoiToList (n-1) c b a l)
Let me explain the reasoning: if the function is going to end up as a list, then you had better compare it to another that takes an empty one as an argument, otherwise append it after it has been solved, which I believe to be the cause of inefficiency, thus leading to the same function being called in its place. The result has been checked and it's correct, but I wanted to know whether this is more efficient or simply redundant, considering the previous solution that I linked to.
EDIT: I commented a line that was unnecessary.
performance haskell recursion towers-of-hanoi
asked Nov 8 at 0:46
Marco_O
185
|
show 3 more comments
up vote
1
down vote
favorite
This Haskell solution has been described as recursive, but not quite efficient according to a few claims, so I have tried to rewrite it with that in mind. The problem is described in a course that is available online and whose homework was the Tower of Hanoi.
A new solution of mine:
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ l = l
-- hanoiToList 1 a b _ l = (a, b) : l
hanoiToList n a b c l = hanoiToList (n-1) a c b ((a, b) : hanoiToList (n-1) c b a l)
Let me explain the reasoning: if the function is going to end up as a list, then you had better compare it to another that takes an empty one as an argument, otherwise append it after it has been solved, which I believe to be the cause of inefficiency, thus leading to the same function being called in its place. The result has been checked and it's correct, but I wanted to know whether this is more efficient or simply redundant, considering the previous solution that I linked to.
EDIT: I commented a line that was unnecessary.
performance haskell recursion towers-of-hanoi
asked Nov 8 at 0:46
Marco_O
185
2
This version is tail-recursive, which might make it more efficient, yeah. To know for sure, you could try benchmarking it with criterion or examining the optimised GHC Core output with-O2 -ddump-simpl(with-dsuppress-uniques -dsuppress-module-prefixesto make it more readable).
– Jon Purdy
Nov 8 at 1:11
1
The solution you posted is, essentially, the standard recursive solution except that it uses difference lists instead of regular ones. Difference lists admit a faster concatenation, which you exploit to gain performance.
– chi
Nov 8 at 10:07
Funny that you mention that, because it's the next homework assignment in the Haskell tutorial that I'm following, which you may be familiar with. Perhaps it's meant to tell me that, when I learn something new, I should apply it to the previous exercise to improve it. Thank you Jon Purdy for criterion too.
– Marco_O
Nov 8 at 11:19
@JonPurdy No, this is not tail-recursive. There is one recursive call in tail position (good), but there's also another one which is not in tail position. Perhaps you missed the second call.
– chi
Nov 8 at 12:28
@chi yes, syntactically it is a nested recursion, but really because of Haskell's laziness it's not a double recursion like e.g. Fibonacci (where the nested call is forced by the strict+) but a guarded recursion (for the 2nd argument) -- the call is delayed (and not because of the:, but just because of the laziness). so it is very much like tail recursive tree traversal with explicit stack of "do-next" notes (either functions, or just the previously visited tree nodes themselves). when the leaf is reached the next action is called in tail position too.
– Will Ness
Nov 8 at 14:48
|
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This Haskell solution has been described as recursive, but not quite efficient according to a few claims, so I have tried to rewrite it with that in mind. The problem is described in a course that is available online and whose homework was the Tower of Hanoi.
A new solution of mine:
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ l = l
-- hanoiToList 1 a b _ l = (a, b) : l
hanoiToList n a b c l = hanoiToList (n-1) a c b ((a, b) : hanoiToList (n-1) c b a l)
Let me explain the reasoning: if the function is going to end up as a list, then you had better compare it to another that takes an empty one as an argument, otherwise append it after it has been solved, which I believe to be the cause of inefficiency, thus leading to the same function being called in its place. The result has been checked and it's correct, but I wanted to know whether this is more efficient or simply redundant, considering the previous solution that I linked to.
EDIT: I commented a line that was unnecessary.
performance haskell recursion towers-of-hanoi
asked Nov 8 at 0:46
Marco_O
185
This Haskell solution has been described as recursive, but not quite efficient according to a few claims, so I have tried to rewrite it with that in mind. The problem is described in a course that is available online and whose homework was the Tower of Hanoi.
A new solution of mine:
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ l = l
-- hanoiToList 1 a b _ l = (a, b) : l
hanoiToList n a b c l = hanoiToList (n-1) a c b ((a, b) : hanoiToList (n-1) c b a l)
Let me explain the reasoning: if the function is going to end up as a list, then you had better compare it to another that takes an empty one as an argument, otherwise append it after it has been solved, which I believe to be the cause of inefficiency, thus leading to the same function being called in its place. The result has been checked and it's correct, but I wanted to know whether this is more efficient or simply redundant, considering the previous solution that I linked to.
EDIT: I commented a line that was unnecessary.
performance haskell recursion towers-of-hanoi
performance haskell recursion towers-of-hanoi
asked Nov 8 at 0:46
Marco_O
185
asked Nov 8 at 0:46
Marco_O
185
edited Nov 8 at 9:17
asked Nov 8 at 0:46
Marco_O
185
asked Nov 8 at 0:46
Marco_O
185
asked Nov 8 at 0:46
Marco_O
185
185
2
This version is tail-recursive, which might make it more efficient, yeah. To know for sure, you could try benchmarking it with criterion or examining the optimised GHC Core output with-O2 -ddump-simpl(with-dsuppress-uniques -dsuppress-module-prefixesto make it more readable).
– Jon Purdy
Nov 8 at 1:11
1
The solution you posted is, essentially, the standard recursive solution except that it uses difference lists instead of regular ones. Difference lists admit a faster concatenation, which you exploit to gain performance.
– chi
Nov 8 at 10:07
Funny that you mention that, because it's the next homework assignment in the Haskell tutorial that I'm following, which you may be familiar with. Perhaps it's meant to tell me that, when I learn something new, I should apply it to the previous exercise to improve it. Thank you Jon Purdy for criterion too.
– Marco_O
Nov 8 at 11:19
@JonPurdy No, this is not tail-recursive. There is one recursive call in tail position (good), but there's also another one which is not in tail position. Perhaps you missed the second call.
– chi
Nov 8 at 12:28
@chi yes, syntactically it is a nested recursion, but really because of Haskell's laziness it's not a double recursion like e.g. Fibonacci (where the nested call is forced by the strict+) but a guarded recursion (for the 2nd argument) -- the call is delayed (and not because of the:, but just because of the laziness). so it is very much like tail recursive tree traversal with explicit stack of "do-next" notes (either functions, or just the previously visited tree nodes themselves). when the leaf is reached the next action is called in tail position too.
– Will Ness
Nov 8 at 14:48
|
show 3 more comments
2
This version is tail-recursive, which might make it more efficient, yeah. To know for sure, you could try benchmarking it with criterion or examining the optimised GHC Core output with-O2 -ddump-simpl(with-dsuppress-uniques -dsuppress-module-prefixesto make it more readable).
– Jon Purdy
Nov 8 at 1:11
1
The solution you posted is, essentially, the standard recursive solution except that it uses difference lists instead of regular ones. Difference lists admit a faster concatenation, which you exploit to gain performance.
– chi
Nov 8 at 10:07
Funny that you mention that, because it's the next homework assignment in the Haskell tutorial that I'm following, which you may be familiar with. Perhaps it's meant to tell me that, when I learn something new, I should apply it to the previous exercise to improve it. Thank you Jon Purdy for criterion too.
– Marco_O
Nov 8 at 11:19
@JonPurdy No, this is not tail-recursive. There is one recursive call in tail position (good), but there's also another one which is not in tail position. Perhaps you missed the second call.
– chi
Nov 8 at 12:28
@chi yes, syntactically it is a nested recursion, but really because of Haskell's laziness it's not a double recursion like e.g. Fibonacci (where the nested call is forced by the strict+) but a guarded recursion (for the 2nd argument) -- the call is delayed (and not because of the:, but just because of the laziness). so it is very much like tail recursive tree traversal with explicit stack of "do-next" notes (either functions, or just the previously visited tree nodes themselves). when the leaf is reached the next action is called in tail position too.
– Will Ness
Nov 8 at 14:48
2
2
This version is tail-recursive, which might make it more efficient, yeah. To know for sure, you could try benchmarking it with criterion or examining the optimised GHC Core output with
-O2 -ddump-simpl (with -dsuppress-uniques -dsuppress-module-prefixes to make it more readable).– Jon Purdy
Nov 8 at 1:11
This version is tail-recursive, which might make it more efficient, yeah. To know for sure, you could try benchmarking it with criterion or examining the optimised GHC Core output with
-O2 -ddump-simpl (with -dsuppress-uniques -dsuppress-module-prefixes to make it more readable).– Jon Purdy
Nov 8 at 1:11
1
1
The solution you posted is, essentially, the standard recursive solution except that it uses difference lists instead of regular ones. Difference lists admit a faster concatenation, which you exploit to gain performance.
– chi
Nov 8 at 10:07
The solution you posted is, essentially, the standard recursive solution except that it uses difference lists instead of regular ones. Difference lists admit a faster concatenation, which you exploit to gain performance.
– chi
Nov 8 at 10:07
Funny that you mention that, because it's the next homework assignment in the Haskell tutorial that I'm following, which you may be familiar with. Perhaps it's meant to tell me that, when I learn something new, I should apply it to the previous exercise to improve it. Thank you Jon Purdy for criterion too.
– Marco_O
Nov 8 at 11:19
Funny that you mention that, because it's the next homework assignment in the Haskell tutorial that I'm following, which you may be familiar with. Perhaps it's meant to tell me that, when I learn something new, I should apply it to the previous exercise to improve it. Thank you Jon Purdy for criterion too.
– Marco_O
Nov 8 at 11:19
@JonPurdy No, this is not tail-recursive. There is one recursive call in tail position (good), but there's also another one which is not in tail position. Perhaps you missed the second call.
– chi
Nov 8 at 12:28
@JonPurdy No, this is not tail-recursive. There is one recursive call in tail position (good), but there's also another one which is not in tail position. Perhaps you missed the second call.
– chi
Nov 8 at 12:28
@chi yes, syntactically it is a nested recursion, but really because of Haskell's laziness it's not a double recursion like e.g. Fibonacci (where the nested call is forced by the strict
+) but a guarded recursion (for the 2nd argument) -- the call is delayed (and not because of the :, but just because of the laziness). so it is very much like tail recursive tree traversal with explicit stack of "do-next" notes (either functions, or just the previously visited tree nodes themselves). when the leaf is reached the next action is called in tail position too.– Will Ness
Nov 8 at 14:48
@chi yes, syntactically it is a nested recursion, but really because of Haskell's laziness it's not a double recursion like e.g. Fibonacci (where the nested call is forced by the strict
+) but a guarded recursion (for the 2nd argument) -- the call is delayed (and not because of the :, but just because of the laziness). so it is very much like tail recursive tree traversal with explicit stack of "do-next" notes (either functions, or just the previously visited tree nodes themselves). when the leaf is reached the next action is called in tail position too.– Will Ness
Nov 8 at 14:48
|
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
3
down vote
Yep, that gets rid of the inefficient copying of (:) constructors. It's a slightly non-idiomatic way to write it, but the more idiomatic way should have identical performance when compiled with optimizations.
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ = id
hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a
That's the slightly more idiomatic approach. It's all about emphasizing the viewpoint that you're building up a transformation of a value. In practice it's identical as long as function composition is being inlined and simplified as expected.
answered Nov 8 at 1:16
Carl
19.6k34768
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
1
@Marco_OhanoiToList 0 _ _ _ l = l===hanoiToList 0 _ _ _ = l -> l===hanoiToList 0 _ _ _ = id. it's the same thing. So even if you havehanoiToList n a b cas your top call, what's being matched in the definition ishanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to. looks different, but is the same.
– Will Ness
Nov 8 at 15:21
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Yep, that gets rid of the inefficient copying of (:) constructors. It's a slightly non-idiomatic way to write it, but the more idiomatic way should have identical performance when compiled with optimizations.
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ = id
hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a
That's the slightly more idiomatic approach. It's all about emphasizing the viewpoint that you're building up a transformation of a value. In practice it's identical as long as function composition is being inlined and simplified as expected.
answered Nov 8 at 1:16
Carl
19.6k34768
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
1
@Marco_OhanoiToList 0 _ _ _ l = l===hanoiToList 0 _ _ _ = l -> l===hanoiToList 0 _ _ _ = id. it's the same thing. So even if you havehanoiToList n a b cas your top call, what's being matched in the definition ishanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to. looks different, but is the same.
– Will Ness
Nov 8 at 15:21
add a comment |
up vote
3
down vote
Yep, that gets rid of the inefficient copying of (:) constructors. It's a slightly non-idiomatic way to write it, but the more idiomatic way should have identical performance when compiled with optimizations.
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ = id
hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a
That's the slightly more idiomatic approach. It's all about emphasizing the viewpoint that you're building up a transformation of a value. In practice it's identical as long as function composition is being inlined and simplified as expected.
answered Nov 8 at 1:16
Carl
19.6k34768
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
1
@Marco_OhanoiToList 0 _ _ _ l = l===hanoiToList 0 _ _ _ = l -> l===hanoiToList 0 _ _ _ = id. it's the same thing. So even if you havehanoiToList n a b cas your top call, what's being matched in the definition ishanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to. looks different, but is the same.
– Will Ness
Nov 8 at 15:21
add a comment |
up vote
3
down vote
up vote
3
down vote
Yep, that gets rid of the inefficient copying of (:) constructors. It's a slightly non-idiomatic way to write it, but the more idiomatic way should have identical performance when compiled with optimizations.
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ = id
hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a
That's the slightly more idiomatic approach. It's all about emphasizing the viewpoint that you're building up a transformation of a value. In practice it's identical as long as function composition is being inlined and simplified as expected.
answered Nov 8 at 1:16
Carl
19.6k34768
Yep, that gets rid of the inefficient copying of (:) constructors. It's a slightly non-idiomatic way to write it, but the more idiomatic way should have identical performance when compiled with optimizations.
hanoi n a b c = hanoiToList n a b c
where
hanoiToList 0 _ _ _ = id
hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a
That's the slightly more idiomatic approach. It's all about emphasizing the viewpoint that you're building up a transformation of a value. In practice it's identical as long as function composition is being inlined and simplified as expected.
answered Nov 8 at 1:16
Carl
19.6k34768
edited Nov 8 at 12:51
answered Nov 8 at 1:16
Carl
19.6k34768
answered Nov 8 at 1:16
Carl
19.6k34768
answered Nov 8 at 1:16
Carl
19.6k34768
19.6k34768
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
1
@Marco_OhanoiToList 0 _ _ _ l = l===hanoiToList 0 _ _ _ = l -> l===hanoiToList 0 _ _ _ = id. it's the same thing. So even if you havehanoiToList n a b cas your top call, what's being matched in the definition ishanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to. looks different, but is the same.
– Will Ness
Nov 8 at 15:21
add a comment |
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
1
@Marco_OhanoiToList 0 _ _ _ l = l===hanoiToList 0 _ _ _ = l -> l===hanoiToList 0 _ _ _ = id. it's the same thing. So even if you havehanoiToList n a b cas your top call, what's being matched in the definition ishanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to. looks different, but is the same.
– Will Ness
Nov 8 at 15:21
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
Strange, I thought that, since you had an empty list as an argument of "hanoiToList", you had to put something in its place ('l' in my case), so that it matched. Is this correct?
– Marco_O
Nov 8 at 1:26
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
@Marco_O nah. Functions are values that can be returned from other functions. If you never inspect an argument, it's often possible to never even name it.
– Carl
Nov 8 at 2:33
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
Thank you! I noticed something that was off about my code. I'm going to edit it to show you the changes.
– Marco_O
Nov 8 at 9:16
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
@Marco_O Ah, yes. Made the same edit to my answer.
– Carl
Nov 8 at 12:51
1
1
@Marco_O
hanoiToList 0 _ _ _ l = l === hanoiToList 0 _ _ _ = l -> l === hanoiToList 0 _ _ _ = id. it's the same thing. So even if you have hanoiToList n a b c as your top call, what's being matched in the definition is hanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to – Will Ness
Nov 8 at 15:21
@Marco_O
hanoiToList 0 _ _ _ l = l === hanoiToList 0 _ _ _ = l -> l === hanoiToList 0 _ _ _ = id. it's the same thing. So even if you have hanoiToList n a b c as your top call, what's being matched in the definition is hanoiToList n a b c, which is evaluated, returns a function, and that function gets applied to – Will Ness
Nov 8 at 15:21
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53200042%2fis-this-haskell-tower-of-hanoi-solution-more-efficient-or-simply-redundant%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
This version is tail-recursive, which might make it more efficient, yeah. To know for sure, you could try benchmarking it with criterion or examining the optimised GHC Core output with
-O2 -ddump-simpl(with-dsuppress-uniques -dsuppress-module-prefixesto make it more readable).– Jon Purdy
Nov 8 at 1:11
1
The solution you posted is, essentially, the standard recursive solution except that it uses difference lists instead of regular ones. Difference lists admit a faster concatenation, which you exploit to gain performance.
– chi
Nov 8 at 10:07
Funny that you mention that, because it's the next homework assignment in the Haskell tutorial that I'm following, which you may be familiar with. Perhaps it's meant to tell me that, when I learn something new, I should apply it to the previous exercise to improve it. Thank you Jon Purdy for criterion too.
– Marco_O
Nov 8 at 11:19
@JonPurdy No, this is not tail-recursive. There is one recursive call in tail position (good), but there's also another one which is not in tail position. Perhaps you missed the second call.
– chi
Nov 8 at 12:28
@chi yes, syntactically it is a nested recursion, but really because of Haskell's laziness it's not a double recursion like e.g. Fibonacci (where the nested call is forced by the strict
+) but a guarded recursion (for the 2nd argument) -- the call is delayed (and not because of the:, but just because of the laziness). so it is very much like tail recursive tree traversal with explicit stack of "do-next" notes (either functions, or just the previously visited tree nodes themselves). when the leaf is reached the next action is called in tail position too.– Will Ness
Nov 8 at 14:48