Oskar Hahn (Dec 24 2024 at 22:55): Oskar Hahn (Dec 24 2024 at 22:55):I am trying to build a generic dijkstra-shortest-path algorithm in Roc. Here is my current version:
Node a : a where a implements Eq
NodeDistance a : { distance : U64, node : Node a }
GetNeighbors a : Node a -> List (NodeDistance a)
IsGoal a : Node a -> Bool
shortestPath : Node a, IsGoal a, GetNeighbors a -> Result U64 [NotFound]
shortestPath = \start, goal, getNeighbors ->
shortestPathHelper [{ distance: 0, node: start }] [] goal getNeighbors
# shortestPathHelper : List (NodeDistance a), List (Node a), IsGoal a, GetNeighbors a -> Result U64 [NotFound]
shortestPathHelper = \list, seen, isGoal, getNeighbors ->
when list is
[] -> Err NotFound
[{ distance, node }, .. as rest] ->
if isGoal node then
Ok distance
else
newSeen = seen |> List.append node
node
|> getNeighbors
|> List.dropIf \neighbor -> List.contains newSeen neighbor.node
|> List.map \nodeDistance -> { nodeDistance & distance: nodeDistance.distance + distance }
|> List.walk rest \acc, neighbor -> updateNodeDistance acc neighbor 0
|> List.sortWith \{ distance: a }, { distance: b } -> Num.compare a b
|> shortestPathHelper newSeen isGoal getNeighbors
updateNodeDistance = \list, newNodeDistance, index ->
when List.get list index is
Err OutOfBounds ->
List.append list newNodeDistance
Ok existingNodeDistance if existingNodeDistance.node == newNodeDistance.node ->
if newNodeDistance.distance < existingNodeDistance.distance then
List.set list index newNodeDistance
else
list
_ ->
updateNodeDistance list newNodeDistance (index + 1)
I can not set the type for shortestPathHelper.
When I do, I get the following error:
This 2nd argument to |> has an unexpected type:
124│ node
125│ |> getNeighbors
126│ |> List.dropIf \neighbor -> List.contains newSeen neighbor.node
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The argument is an anonymous function of type:
{ … } -> Bool
But |> needs its 2nd argument to be:
{ … } -> Bool
I don't understand the error message.
The inferred type is List { distance : Num a, node : a1 }b, List a1, (a1 -> Bool), (a1 -> List { distance : Num a, node : a1 }b) -> [Err [NotFound], Ok (Num a)] where a1 implements Eq
Also, the code is quite slow. It is used here and takes around 30 seconds. I tried to use a Set for seen, which made it even slower. I used List.withCapacity for seen and the list of found elements, which also did not help. Do you know, what I could do to improve it?
Brendan Hansknecht (Dec 24 2024 at 23:18):With types, I bet this doesn't work right: Node a : a where a implements Eq
Brendan Hansknecht (Dec 24 2024 at 23:18):You probably need an explicit where annotation in each function definition
Brendan Hansknecht (Dec 24 2024 at 23:18):but that is just a guess
Oskar Hahn (Dec 24 2024 at 23:32):This does not help. When I add where a implements Eq to shortestPath and shortestPathHelper, I get the same error.
Oskar Hahn (Dec 24 2024 at 23:41):It seems, that Roc guesses the type of the anonymous function in the List.dropIf line "wrong".
When I define the function as:
fn : NodeDistance a -> Bool
fn = \{ node: n } ->
List.contains newSeen n
and change the line to:
|> List.dropIf fn
then it works (without setting where a implements Eq anywhere except on the Node a definition).
(An inline type definition would have made this easier).
Oskar Hahn (Dec 24 2024 at 23:42):Could it be, that Roc has a problem, that the function only uses {node} but it has to work on a list of {node, distance}?
Oskar Hahn (Dec 24 2024 at 23:53):Here is a smaller example:
Node a : a where a implements Eq
fn : List { node : Node a }, a -> Bool
fn = \list, someNode ->
List.contains list \{ node } -> node == someNode
You can test this by coping this lines to any Roc file and calling roc check on it.
Brendan Hansknecht (Dec 25 2024 at 00:38):I'll check later if no one else does, but does this type signature work?
fn : List { node: Node a }, Node a -> Bool
And I guess to be thorough, this one:
fn : List { node: a }, a -> Bool where a implements Eq
Also, I'll definitely take a look at the perf too when I have time. Can you share a full source that I can run for testing perf?
Oskar Hahn (Dec 25 2024 at 00:44):Here is a full example: https://github.com/ostcar/aoc2024/blob/4a932c45827ab5dc4f9a9efe51b79c77f6fe24e1/day16.roc
I reused it here. Here it only takes 19ms on a optimized build. Maybe the other code in the first example made it slow.
Oskar Hahn (Dec 25 2024 at 00:49):Brendan Hansknecht said:
fn : List { node: a }, a -> Bool where a implements Eq
No. both of them do not work. The one without where a impelements Eq complains, that a has to implement Eq.
The second one gives an interesting error message:
This 2nd argument to contains has an unexpected type:
74│ List.contains list \{ node } -> node == someNode
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The argument is an anonymous function of type:
{ node : a }a -> Bool where a implements Eq
But contains needs its 2nd argument to be:
{ node : a } where a implements Eq
Here is the code, that throws the error:
fn : List { node : a }, a -> Bool where a implements Eq
fn = \list, someNode ->
List.contains list \{ node } -> node == someNode
I am not seeing the perf issues you mentioned at least not at the same scale. Need to double check on a different machine. Could you send me your exact puzzle input? I'm wondering if your exact input might have a harder solution or something.
Oskar Hahn (Dec 25 2024 at 01:46):Sure
day16.input
Oskar Hahn (Dec 25 2024 at 01:49):It seems, I forgot to build it with --optimize :face_with_peeking_eye:
Without optimize, each part takes around 40 seconds. With optimize it is below 2 seconds. Sorry.
Oskar Hahn (Dec 25 2024 at 01:51):I have no computer science degree. All my knowledge is self taught. If you would have implemented Dijkstra in Roc, would you have done it similar?
Brendan Hansknecht (Dec 25 2024 at 01:54):I think you should get a solid gain switching back to a Set, but overall, I think the implementation is good.
Also, in roc we don't have any sort of priority queue, which would be more standard than sorting the list all the time. Theoretically inserting in sorted order should be more performant that what you have, but our sorting algorithm is really smart and will notice when chunks of data are mostly sorted.
Brendan Hansknecht (Dec 25 2024 at 01:57):Also, spends more time in allocations and data movement than I would expect, but that may just be due to growing the list and set.
Oskar Hahn (Dec 25 2024 at 08:58):You are right, with an optimized build, the Set gets much faster. To add an capacity to seen and the list, does not help. Maybe I am doing something wrong and in one place, the list gets copied instead of in place mutated.
It would be nice to have some sort of debug output to see, when a big value has a refcount higher then one.
Here are the numbers:
List, no capacity: 635 ms
Set, no capacity: 59 ms
Set, with capacity: 49 ms
List with capacity: 956 ms
Here is the version with Set and capacity:
Dijkstra
Anthony Bullard (Dec 25 2024 at 12:00):Having list with capacity be so much slower is strange
Oskar Hahn (Dec 25 2024 at 14:30):That's why i guess, that there is a refcount higher than 1. This would lead to coping. And a copy of a list with a bigger capacity takes longer
Last updated: Jul 05 2025 at 12:14 UTC