Questions on SML type ckecking and inference

Question

First of all, since the question is somehow related to a school project I don't think that posting my code is appropriate. Plus, as I explain later on I only have a modified version of the code in question.

And I explain myself. I should implement a version of Dijkstra's algorithm using a priority queue. I thought that a simple functional way to do so is define a dijkstra function with inputs the queue and the targeted node and a helper function to enqueue the nodes that are neighbors to the element of the list that was just dequeued. Unfortunately, the helper function did't typecheck - Unresolved Flex Record.

So far it may seem that the code is important but allow me to add one more detail. Since the graph was 4-canonical(meaning each node has exactly four neighbors) I represented it as a matrix using modulus arithmetic. In order to simplify my algorithm I used this fact to rewrite it and use 4 extra helper functions - one for each move possible - instead of four ifs inside the first helper function. Each of the four-move function returns true if we should visit this node (meaning the cost we will need this way is smaller than the current cost needed) and false if not. And the first helper simply returns a tuple of four booleans variables. Finally, I copied the enqueue code that wasn't working in my first try into the body of the dijkstra code and suddenly it did typecheck.

I understand that it may still be unclear and perhaps you can only speculated about what was going on. But I am truly very puzzled.I searched this site and SML basis as well and found that this kind of error occurs in the following case:

f (x,y,z) = ...

where z isn't used so the checker can't deduct what it is. I am sure this is not the case in my problem since I just copy-paste the code(not a very good technique I know but ok). Hence, I concluded that the problem was the typechecker not working with functions calls. I searched again and found a Hindley Miller algorithm explanation. And from what I understood every time it encounters and a function will assume is a->b as the first step and later on will go to the definition of the function and complete the task. So I was back to square one and decided to ask this question here looking for a better understanding of type inference or for a hint of what has going on.

P.S. 1) Even though I tried my best to explain the question I it is still unclear or too broad let me know and I will delete,no problem. P.S. 2) A smaller and simpler question: I read that #1 is not adviceable to take the 1st element of a tuple and sometimes it doesn't even typecheck and instead it should be used pattern matching. Could you explain that? P.S. 3) Someone may wonder why I asked this question since I solved the problem with my second try. Personally, I don't consider solved but hidden.

Thanks in advance and sorry for the size of the question.

Links:

SML/NJ Errors

P.S. 2)

Hindley-Miller

UPDATED: After some extra searching I have a guess about what was wrong. I was implementing a priority queue not customized for my problem but more general. So, the inference of the priority queue type was taking place when I first enqueued an element. But after enqueueing my source node and calling dijkstra the queue would be empty once more (my dijsktra was dequeueing the first element checking if it is the target node) and the first call of the helper function that add nodes would have an empty queue as one of its arguments. Perhaps the empty queue has no type and that was causing the error?

Answer 1

I'm taking a guess at what you're asking.

I have a function enqueue that does not work in one context, but it does work in another. Why? It uses the #1 macro, and I read that #1 is not adviceable to take the 1st element of a tuple and sometimes it doesn't even typecheck and instead it should be used pattern matching.

In Standard ML, #1 is a macro. It behaves like a function, but unlike functions, it is overloaded for any tuple/record with a 1 field in it. If you do not specify what kind of tuple you're passing to a function, using #1 will not disambiguate this. For example,

- fun f pair = #1 pair;
! Toplevel input:
! fun f pair = #1 pair;
!              ^^
! Unresolved record pattern

But giving it the type (either through explicit type annotation, or in a context where the type can be inferred by other means) works well.

- fun f (pair : int * int) = #1 pair;
> val f = fn : int * int -> int

I don't know if I'd label #1 as a definite no-go and pattern matching as the only option, [edit: ... but this Stack Overflow answer that Ionuț G. Stan linked to has some arguments.]

There are advantages and disadvantages with both. Alternatively you can make unambiguous getters that only work on the type of tuple you're working with. For example,

fun fst (x, _) = x
fun snd (_, y) = y