Elias Mulhall (Jun 23 2023 at 23:35): Elias Mulhall (Jun 23 2023 at 23:35):Hey Y'all, I'm just getting started with Roc and thought that implementing some classic sorting algorithms would be an interesting exercise.
Here's my code: https://gist.github.com/mulias/c8920302f5bb63dbc922e8914420dfc8
slowQuicksort is working fine, it partitions the list into sublists then joins them back up recursively.
fastQuicksort (quickersort?) passing around the full list and operates on sublists by index, under the theory that the compiler will optimize theList.swaps and get similar performance to an imperative solution.
In practice I can't get the code to compile on my machine. It seems to hang and eats up a bunch of memory. If I comment out the fastQuicksort code it works again.
How do I start debugging this kind of issue?
Brendan Hansknecht (Jun 24 2023 at 00:15):I think you hit a compiler bug, not sure how exactly, but it seems related to the List.walkFromUntil in partition.
Brendan Hansknecht (Jun 24 2023 at 00:16):At least that gives us a relatively small repro
Brendan Hansknecht (Jun 24 2023 at 00:28):So definitely a roc bug that we don't give you an error and just hang, but the root cause of the issue is the function passed to List.walkFromUntil.
Brendan Hansknecht (Jun 24 2023 at 00:29):The value returned from Break needs to match the value used in Continue
Brendan Hansknecht (Jun 24 2023 at 00:29):they both have the same type variable, namely state
Brendan Hansknecht (Jun 24 2023 at 00:30):This is because Break is not guaranteed to get hit. If you use of the entire list and never hit a Break, the last state from Continue will be returned.
Brendan Hansknecht (Jun 24 2023 at 00:31):So, not saying this is correct at all, but it compiles:
(outI, _, outList) =
List.walkFromUntil list start (firstPivotIndex, firstIndex, list) \(pivotIndex, index, listAcc), elem ->
if index >= end then
finalPivotIndex = pivotIndex - 1
Break (firstPivotIndex, index, List.swap listAcc start firstPivotIndex)
else if compare elem pivot == LT then
Continue (pivotIndex, index, listAcc)
else
Continue (pivotIndex + 1, index + 1, List.swap listAcc pivotIndex index)
(outI, outList)
Hopefully that unblocks you.
Brendan Hansknecht (Jun 24 2023 at 00:31):I'll file an issue for the hang since it is easy to repro.
Brendan Hansknecht (Jun 24 2023 at 00:35):filed #5595
Elias Mulhall (Jun 24 2023 at 00:56):That makes sense, thank you! I'm also not confident it's correct, but being able to compile will definitely help.
Last updated: Jul 06 2025 at 12:14 UTC