Moving elements in a priority queue to a lower level

Question

I have a multi-level priority queue which is implemented as a list of (level:int, priority:int, 'a). The datatype looks like this:

datatype 'a queue = NONE | Q of (int * int * 'a) list;

Elements at lower level are at the front of the queue. Elements at same level are sorted on basis of priority. I have an enqueue function

So, if existing queue is: val a = Q [(3,2,"c"),(3,2,"d"),(5,2,"b"),(5,3,"a")], then, enqueue a 1 5 "e" gives

val a = Q [(1,5,"e"),(3,2,"c"),(3,2,"d"),(5,2,"b"),(5,3,"a")]

I have to write a function move which operates on a predicate p which moves all elements that satisfy the predicate p to a lower level queue within q. That is : val move : ('a -> bool) -> 'a queue -> 'a queue Definition as below won't work.

fun move pred (Q((l,p,v)::xs)) =  if (pred (v)) then enqueue (Q xs) (l-1) p v else (move pred (Q xs))
  | move pred (Q[]) = raise Empty

I have just started learning sml. Please help.

Answer 1

First off, having a constructor named NONE is bad, since it overwrites the built-in option-type value of the same name. Secondly, you say that elements for which the predicate satisfies should be moved to a lower level - is that level always one less than its previous level?

Your move will not work because you apparently do not call it recursively when pred v is true, only when it isn't. If you instead enqueue (l,p,v) into a queue on which move pred is called recursively (i.e. move pred (Q xs) rather than Q xs), perhaps it will work better.

Note also that this problem is ideal for solving through folding:

fun move pred (Q elems) =
    let fun enq ((l,p,v), q) = enqueue q (if pred v then l-1 else l) p v
    in foldl enq (Q []) elems end

Answer 2

fun move pred (Q((l,p,v)::xs)) = if (pred (v)) then enqueue (Q xs) (l-1) p v else enqueue (move pred (Q xs)) l p v | move pred (Q[]) = raise Empty This also works !