Functionally idiomatic FFT
I've written the this radix-2 FFT with the goal of making it functionally idiomatic without sacrificing too much performance:
let reverse x bits =
let rec reverse' x bits y =
match bits with
| 0 -> y
| _ -> ((y <<< 1) ||| (x &&& 1))
|> reverse' (x >>> 1) (bits - 1)
reverse' x bits 0
let radix2 (vector: Complex) (direction: int) =
let z = vector.Length
let depth = floor(Math.Log(double z, 2.0)) |> int
if (1 <<< depth) <> z then failwith "Vector length is not a power of 2"
// Complex roots of unity; "twiddle factors"
let unity: Complex =
let xpn = float direction * Math.PI / double z
Array.Parallel.init<Complex> (z/2) (fun i ->
Complex.FromPolarCoordinates(1.0, (float i) * xpn))
// Permutes elements of input vector via bit-reversal permutation
let pvec = Array.Parallel.init z (fun i -> vector.[reverse i depth])
let outerLoop (vec: Complex) =
let rec recLoop size =
if size <= z then
let mid, step = size / 2, z / size
let rec inrecLoop i =
if i < z then
let rec bottomLoop idx k =
if idx < i + mid then
let temp = vec.[idx + mid] * unity.[k]
vec.[idx + mid] <- (vec.[idx] - temp)
vec.[idx] <- (vec.[idx] + temp)
bottomLoop (idx + 1) (k + step)
bottomLoop i 0
inrecLoop (i + size)
inrecLoop 0
recLoop (size * 2)
recLoop 2
vec
outerLoop pvec
The outerLoop
segment is the biggest nested tail-recursive mess I have ever written. I replicated the algorithm in the Wikipedia article for the Cooley-Tukey algorithm, but the only functional constructs I could think to implement using higher-order functions result in massive hits to both performance and memory efficiency. Are there other solutions that would yield the same results without resulting in massive slow-downs, while still being idiomatic?
functional-programming f# fft
add a comment |
I've written the this radix-2 FFT with the goal of making it functionally idiomatic without sacrificing too much performance:
let reverse x bits =
let rec reverse' x bits y =
match bits with
| 0 -> y
| _ -> ((y <<< 1) ||| (x &&& 1))
|> reverse' (x >>> 1) (bits - 1)
reverse' x bits 0
let radix2 (vector: Complex) (direction: int) =
let z = vector.Length
let depth = floor(Math.Log(double z, 2.0)) |> int
if (1 <<< depth) <> z then failwith "Vector length is not a power of 2"
// Complex roots of unity; "twiddle factors"
let unity: Complex =
let xpn = float direction * Math.PI / double z
Array.Parallel.init<Complex> (z/2) (fun i ->
Complex.FromPolarCoordinates(1.0, (float i) * xpn))
// Permutes elements of input vector via bit-reversal permutation
let pvec = Array.Parallel.init z (fun i -> vector.[reverse i depth])
let outerLoop (vec: Complex) =
let rec recLoop size =
if size <= z then
let mid, step = size / 2, z / size
let rec inrecLoop i =
if i < z then
let rec bottomLoop idx k =
if idx < i + mid then
let temp = vec.[idx + mid] * unity.[k]
vec.[idx + mid] <- (vec.[idx] - temp)
vec.[idx] <- (vec.[idx] + temp)
bottomLoop (idx + 1) (k + step)
bottomLoop i 0
inrecLoop (i + size)
inrecLoop 0
recLoop (size * 2)
recLoop 2
vec
outerLoop pvec
The outerLoop
segment is the biggest nested tail-recursive mess I have ever written. I replicated the algorithm in the Wikipedia article for the Cooley-Tukey algorithm, but the only functional constructs I could think to implement using higher-order functions result in massive hits to both performance and memory efficiency. Are there other solutions that would yield the same results without resulting in massive slow-downs, while still being idiomatic?
functional-programming f# fft
I have no knowledge of F# and I'm asking this only out of curiosity: is this idiomatic F#?
– chb
Nov 19 '18 at 8:25
3
Is the indentation correct? From looking at the code I have a feeling yourbottomLoop
is never called…
– dumetrulo
Nov 19 '18 at 9:00
@dumetrulo should be fixed now. Probably got mangled in the copy.
– mribrainguy
Nov 19 '18 at 17:51
@chb my understanding is that functional languages prefer immutability and higher-order functions. So no, hence my asking what a more idiomatic solution might look like.
– mribrainguy
Nov 19 '18 at 17:52
@mribrainguy Have a look at this question on Software Engineering. It touches upon tail recursion, local, mutable variables, and the notion of a pure function.
– chb
Nov 20 '18 at 0:04
add a comment |
I've written the this radix-2 FFT with the goal of making it functionally idiomatic without sacrificing too much performance:
let reverse x bits =
let rec reverse' x bits y =
match bits with
| 0 -> y
| _ -> ((y <<< 1) ||| (x &&& 1))
|> reverse' (x >>> 1) (bits - 1)
reverse' x bits 0
let radix2 (vector: Complex) (direction: int) =
let z = vector.Length
let depth = floor(Math.Log(double z, 2.0)) |> int
if (1 <<< depth) <> z then failwith "Vector length is not a power of 2"
// Complex roots of unity; "twiddle factors"
let unity: Complex =
let xpn = float direction * Math.PI / double z
Array.Parallel.init<Complex> (z/2) (fun i ->
Complex.FromPolarCoordinates(1.0, (float i) * xpn))
// Permutes elements of input vector via bit-reversal permutation
let pvec = Array.Parallel.init z (fun i -> vector.[reverse i depth])
let outerLoop (vec: Complex) =
let rec recLoop size =
if size <= z then
let mid, step = size / 2, z / size
let rec inrecLoop i =
if i < z then
let rec bottomLoop idx k =
if idx < i + mid then
let temp = vec.[idx + mid] * unity.[k]
vec.[idx + mid] <- (vec.[idx] - temp)
vec.[idx] <- (vec.[idx] + temp)
bottomLoop (idx + 1) (k + step)
bottomLoop i 0
inrecLoop (i + size)
inrecLoop 0
recLoop (size * 2)
recLoop 2
vec
outerLoop pvec
The outerLoop
segment is the biggest nested tail-recursive mess I have ever written. I replicated the algorithm in the Wikipedia article for the Cooley-Tukey algorithm, but the only functional constructs I could think to implement using higher-order functions result in massive hits to both performance and memory efficiency. Are there other solutions that would yield the same results without resulting in massive slow-downs, while still being idiomatic?
functional-programming f# fft
I've written the this radix-2 FFT with the goal of making it functionally idiomatic without sacrificing too much performance:
let reverse x bits =
let rec reverse' x bits y =
match bits with
| 0 -> y
| _ -> ((y <<< 1) ||| (x &&& 1))
|> reverse' (x >>> 1) (bits - 1)
reverse' x bits 0
let radix2 (vector: Complex) (direction: int) =
let z = vector.Length
let depth = floor(Math.Log(double z, 2.0)) |> int
if (1 <<< depth) <> z then failwith "Vector length is not a power of 2"
// Complex roots of unity; "twiddle factors"
let unity: Complex =
let xpn = float direction * Math.PI / double z
Array.Parallel.init<Complex> (z/2) (fun i ->
Complex.FromPolarCoordinates(1.0, (float i) * xpn))
// Permutes elements of input vector via bit-reversal permutation
let pvec = Array.Parallel.init z (fun i -> vector.[reverse i depth])
let outerLoop (vec: Complex) =
let rec recLoop size =
if size <= z then
let mid, step = size / 2, z / size
let rec inrecLoop i =
if i < z then
let rec bottomLoop idx k =
if idx < i + mid then
let temp = vec.[idx + mid] * unity.[k]
vec.[idx + mid] <- (vec.[idx] - temp)
vec.[idx] <- (vec.[idx] + temp)
bottomLoop (idx + 1) (k + step)
bottomLoop i 0
inrecLoop (i + size)
inrecLoop 0
recLoop (size * 2)
recLoop 2
vec
outerLoop pvec
The outerLoop
segment is the biggest nested tail-recursive mess I have ever written. I replicated the algorithm in the Wikipedia article for the Cooley-Tukey algorithm, but the only functional constructs I could think to implement using higher-order functions result in massive hits to both performance and memory efficiency. Are there other solutions that would yield the same results without resulting in massive slow-downs, while still being idiomatic?
functional-programming f# fft
functional-programming f# fft
edited Nov 19 '18 at 17:50
mribrainguy
asked Nov 19 '18 at 7:49
mribrainguymribrainguy
183
183
I have no knowledge of F# and I'm asking this only out of curiosity: is this idiomatic F#?
– chb
Nov 19 '18 at 8:25
3
Is the indentation correct? From looking at the code I have a feeling yourbottomLoop
is never called…
– dumetrulo
Nov 19 '18 at 9:00
@dumetrulo should be fixed now. Probably got mangled in the copy.
– mribrainguy
Nov 19 '18 at 17:51
@chb my understanding is that functional languages prefer immutability and higher-order functions. So no, hence my asking what a more idiomatic solution might look like.
– mribrainguy
Nov 19 '18 at 17:52
@mribrainguy Have a look at this question on Software Engineering. It touches upon tail recursion, local, mutable variables, and the notion of a pure function.
– chb
Nov 20 '18 at 0:04
add a comment |
I have no knowledge of F# and I'm asking this only out of curiosity: is this idiomatic F#?
– chb
Nov 19 '18 at 8:25
3
Is the indentation correct? From looking at the code I have a feeling yourbottomLoop
is never called…
– dumetrulo
Nov 19 '18 at 9:00
@dumetrulo should be fixed now. Probably got mangled in the copy.
– mribrainguy
Nov 19 '18 at 17:51
@chb my understanding is that functional languages prefer immutability and higher-order functions. So no, hence my asking what a more idiomatic solution might look like.
– mribrainguy
Nov 19 '18 at 17:52
@mribrainguy Have a look at this question on Software Engineering. It touches upon tail recursion, local, mutable variables, and the notion of a pure function.
– chb
Nov 20 '18 at 0:04
I have no knowledge of F# and I'm asking this only out of curiosity: is this idiomatic F#?
– chb
Nov 19 '18 at 8:25
I have no knowledge of F# and I'm asking this only out of curiosity: is this idiomatic F#?
– chb
Nov 19 '18 at 8:25
3
3
Is the indentation correct? From looking at the code I have a feeling your
bottomLoop
is never called…– dumetrulo
Nov 19 '18 at 9:00
Is the indentation correct? From looking at the code I have a feeling your
bottomLoop
is never called…– dumetrulo
Nov 19 '18 at 9:00
@dumetrulo should be fixed now. Probably got mangled in the copy.
– mribrainguy
Nov 19 '18 at 17:51
@dumetrulo should be fixed now. Probably got mangled in the copy.
– mribrainguy
Nov 19 '18 at 17:51
@chb my understanding is that functional languages prefer immutability and higher-order functions. So no, hence my asking what a more idiomatic solution might look like.
– mribrainguy
Nov 19 '18 at 17:52
@chb my understanding is that functional languages prefer immutability and higher-order functions. So no, hence my asking what a more idiomatic solution might look like.
– mribrainguy
Nov 19 '18 at 17:52
@mribrainguy Have a look at this question on Software Engineering. It touches upon tail recursion, local, mutable variables, and the notion of a pure function.
– chb
Nov 20 '18 at 0:04
@mribrainguy Have a look at this question on Software Engineering. It touches upon tail recursion, local, mutable variables, and the notion of a pure function.
– chb
Nov 20 '18 at 0:04
add a comment |
1 Answer
1
active
oldest
votes
I'm not an expert on how the algorithm works, so there might be a nice functional implementation, but it is worth noting that using a localised mutation is perfectly idiomatic in F#.
Your radix2
function is functional from the outside - it takes vector
array as an input, never mutates it, creates a new array pvec
which it then initializes (using some mutation along the way) and then returns it. This is a similar pattern to what built-in functions like Array.map
use (which initializes a new array, mutates it and then returns it). This is often a sensible way of doing things, because some algorithms are better written using mutation.
In this case, it's perfectly reasonable to also use local mutable variables and loops. Doing that will make your code more readable compared to the tail-recursive version. I have not tested this, but my naive translation of your outerLoop
function would just be to use three nested loops - something like this:
let mutable size = 2
while size <= z do
let mid, step = size / 2, z / size
let mutable i = 0
while i < z do
for j in 0 .. mid - 1 do
let idx, k = i + j, step * j
let temp = pvec.[idx + mid] * unity.[k]
pvec.[idx + mid] <- (pvec.[idx] - temp)
pvec.[idx] <- (pvec.[idx] + temp)
i <- i + size
size <- size * 2
This might not be exactly right (I did this just be refactoring your code), but I think it's actually more idiomatic than using complex nested tail-recursive functions in this case.
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53370357%2ffunctionally-idiomatic-fft%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I'm not an expert on how the algorithm works, so there might be a nice functional implementation, but it is worth noting that using a localised mutation is perfectly idiomatic in F#.
Your radix2
function is functional from the outside - it takes vector
array as an input, never mutates it, creates a new array pvec
which it then initializes (using some mutation along the way) and then returns it. This is a similar pattern to what built-in functions like Array.map
use (which initializes a new array, mutates it and then returns it). This is often a sensible way of doing things, because some algorithms are better written using mutation.
In this case, it's perfectly reasonable to also use local mutable variables and loops. Doing that will make your code more readable compared to the tail-recursive version. I have not tested this, but my naive translation of your outerLoop
function would just be to use three nested loops - something like this:
let mutable size = 2
while size <= z do
let mid, step = size / 2, z / size
let mutable i = 0
while i < z do
for j in 0 .. mid - 1 do
let idx, k = i + j, step * j
let temp = pvec.[idx + mid] * unity.[k]
pvec.[idx + mid] <- (pvec.[idx] - temp)
pvec.[idx] <- (pvec.[idx] + temp)
i <- i + size
size <- size * 2
This might not be exactly right (I did this just be refactoring your code), but I think it's actually more idiomatic than using complex nested tail-recursive functions in this case.
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
add a comment |
I'm not an expert on how the algorithm works, so there might be a nice functional implementation, but it is worth noting that using a localised mutation is perfectly idiomatic in F#.
Your radix2
function is functional from the outside - it takes vector
array as an input, never mutates it, creates a new array pvec
which it then initializes (using some mutation along the way) and then returns it. This is a similar pattern to what built-in functions like Array.map
use (which initializes a new array, mutates it and then returns it). This is often a sensible way of doing things, because some algorithms are better written using mutation.
In this case, it's perfectly reasonable to also use local mutable variables and loops. Doing that will make your code more readable compared to the tail-recursive version. I have not tested this, but my naive translation of your outerLoop
function would just be to use three nested loops - something like this:
let mutable size = 2
while size <= z do
let mid, step = size / 2, z / size
let mutable i = 0
while i < z do
for j in 0 .. mid - 1 do
let idx, k = i + j, step * j
let temp = pvec.[idx + mid] * unity.[k]
pvec.[idx + mid] <- (pvec.[idx] - temp)
pvec.[idx] <- (pvec.[idx] + temp)
i <- i + size
size <- size * 2
This might not be exactly right (I did this just be refactoring your code), but I think it's actually more idiomatic than using complex nested tail-recursive functions in this case.
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
add a comment |
I'm not an expert on how the algorithm works, so there might be a nice functional implementation, but it is worth noting that using a localised mutation is perfectly idiomatic in F#.
Your radix2
function is functional from the outside - it takes vector
array as an input, never mutates it, creates a new array pvec
which it then initializes (using some mutation along the way) and then returns it. This is a similar pattern to what built-in functions like Array.map
use (which initializes a new array, mutates it and then returns it). This is often a sensible way of doing things, because some algorithms are better written using mutation.
In this case, it's perfectly reasonable to also use local mutable variables and loops. Doing that will make your code more readable compared to the tail-recursive version. I have not tested this, but my naive translation of your outerLoop
function would just be to use three nested loops - something like this:
let mutable size = 2
while size <= z do
let mid, step = size / 2, z / size
let mutable i = 0
while i < z do
for j in 0 .. mid - 1 do
let idx, k = i + j, step * j
let temp = pvec.[idx + mid] * unity.[k]
pvec.[idx + mid] <- (pvec.[idx] - temp)
pvec.[idx] <- (pvec.[idx] + temp)
i <- i + size
size <- size * 2
This might not be exactly right (I did this just be refactoring your code), but I think it's actually more idiomatic than using complex nested tail-recursive functions in this case.
I'm not an expert on how the algorithm works, so there might be a nice functional implementation, but it is worth noting that using a localised mutation is perfectly idiomatic in F#.
Your radix2
function is functional from the outside - it takes vector
array as an input, never mutates it, creates a new array pvec
which it then initializes (using some mutation along the way) and then returns it. This is a similar pattern to what built-in functions like Array.map
use (which initializes a new array, mutates it and then returns it). This is often a sensible way of doing things, because some algorithms are better written using mutation.
In this case, it's perfectly reasonable to also use local mutable variables and loops. Doing that will make your code more readable compared to the tail-recursive version. I have not tested this, but my naive translation of your outerLoop
function would just be to use three nested loops - something like this:
let mutable size = 2
while size <= z do
let mid, step = size / 2, z / size
let mutable i = 0
while i < z do
for j in 0 .. mid - 1 do
let idx, k = i + j, step * j
let temp = pvec.[idx + mid] * unity.[k]
pvec.[idx + mid] <- (pvec.[idx] - temp)
pvec.[idx] <- (pvec.[idx] + temp)
i <- i + size
size <- size * 2
This might not be exactly right (I did this just be refactoring your code), but I think it's actually more idiomatic than using complex nested tail-recursive functions in this case.
answered Nov 19 '18 at 21:09
Tomas PetricekTomas Petricek
199k13290463
199k13290463
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
add a comment |
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
I think this is the answer I didn't know I needed. I had been assuming that mutation was a code smell that should be avoided where possible, but local mutation definitely seems like a reasonable compromise and is probably going to help me with performance critical parts of my code.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
You may have seen this F# FFT but the performance is horrible. I wondered if there was a way to achieve something similar without the performance issues but with your advice I think I have a good direction in which to proceed.
– mribrainguy
Nov 20 '18 at 4:25
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53370357%2ffunctionally-idiomatic-fft%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I have no knowledge of F# and I'm asking this only out of curiosity: is this idiomatic F#?
– chb
Nov 19 '18 at 8:25
3
Is the indentation correct? From looking at the code I have a feeling your
bottomLoop
is never called…– dumetrulo
Nov 19 '18 at 9:00
@dumetrulo should be fixed now. Probably got mangled in the copy.
– mribrainguy
Nov 19 '18 at 17:51
@chb my understanding is that functional languages prefer immutability and higher-order functions. So no, hence my asking what a more idiomatic solution might look like.
– mribrainguy
Nov 19 '18 at 17:52
@mribrainguy Have a look at this question on Software Engineering. It touches upon tail recursion, local, mutable variables, and the notion of a pure function.
– chb
Nov 20 '18 at 0:04