0

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?

cgss
  • 233
  • 2
  • 10
  • What is your question? – sshine Jun 12 '17 at 07:25
  • @Simon Shine My question is why enqueue didn't type resolve when taking place in the second function but did when it was moved inside Dijkstra; Does the inferencing works differently with functions? Or I understood it correctly and could be something else? – cgss Jun 12 '17 at 08:44
  • @cgss it would help us tremendously to see some working/failing code, even if the question is more general than that. – Ionuț G. Stan Jun 12 '17 at 09:53
  • Also, have you seen this question? https://stackoverflow.com/questions/13497125/unresolved-flex-record-need-to-know-the-names-of-all-the-fields-in-this-context – Ionuț G. Stan Jun 12 '17 at 09:55
  • @ Ionut G. Stan I apologize again for the non existence but I think I explain mysef. Perhaps I should try write a pseudocode or something like that? Do you think this could help? Also I did see the question: is the P.S.2) link . I did help me to make my second try work but as you may have noticed it didn't explain why and that led me to P.S.2) – cgss Jun 12 '17 at 10:28
  • It is always a good idea to include code, preferably enough to make it a [mcve]. Frankly, "since the question is somehow related to a school project I don't think that posting my code is appropriate" makes little sense. It is hard to answer questions regarding code that you can't see. You can almost always give sample code which illustrates the problem, even if your original code is too large to post or can't be posted for some other reason. – John Coleman Jun 12 '17 at 14:21
  • @John Coleman By sample code you mean part of the original code or something like pseudocode? – cgss Jun 12 '17 at 14:30
  • Actual code. Ideally, someone should be able to take your code and reproduce whatever problem you are asking about. Please read [mcve] carefully. The only alternatives are not pseudocode or your original code. If need be, you can write code (based on your original code) for the question itself. – John Coleman Jun 12 '17 at 14:53

1 Answers1

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
sshine
  • 15,635
  • 1
  • 41
  • 66
  • That actually answers my P.S.2) little question so thanks!(I upvoted but it didn't count).Although I will ask to clarify a point you made. Let's assume we have the fun f as you defined it at the beginning(without type declaration) If the checker says ok I will know what it is once you called then there's no limitation if you want to call it firstly with a 2-element tuple and later on with a 3-element or even if you call it with an integer tuple and later with a string tuple. Now, because ML doesn't want to allow the programmer to make such mistakes it will say pattern error from the beginning? – cgss Jun 12 '17 at 10:40
  • (I run out of chars) Is this want you mean by not disambiguate because it is overloaded? I should also mention that this didn't happened with enqueue and also every argument was used either inside the function that was adding nodes or the basic dijkstra function. – cgss Jun 12 '17 at 10:44
  • @cgss: I'm sorry, you're going to have to be more concise. I have no idea what you're asking. The comments on Stack Overflow are not ideal for follow-up conversation. Ideally you should ask a concise question and receive a concise answer and, if necessary, update your question if there's something you could concretize. It sounds like you want to understand how type inference works at a fundamental level. You may like to read the articles linked in [this answer](https://stackoverflow.com/a/34249657/235908). And you may want to understand what it means for a function/operator to be overloaded. – sshine Jun 12 '17 at 13:00
  • Once again I am sorry but allow me one more comment. I read the links you provided and although I think I do have a fundamental understanding of type inference they helped me to go one step further. Therefore, I will update my question to add some new information. ( I have seen overloading before in C++ and Java but never in a functional language besides the common occasions). – cgss Jun 12 '17 at 14:03