What exactly does this Standard ML code do?

Question

I'm reading Chris Okasaki's purely functional data structures, and there's one example I am having trouble with. It is located here. In particular, I don't understand how the rotate and exec functions work:

fun rotate($Nil, y::_, a) = $Cons (y, a)
    | rotate ($Cons (x, xs), y :: ys, a) = 
        $Cons(x, rotate (xs, ys, $Cons (y, a)))

fun exec (f, r, $Cons (X, s)) = (f, r, s)
    | exec (f, r, $Nil) = let val f' = rotate (f, r, $Nil) in (f', [], f') end

Could someone put this in stupid-people terms? I'm still learning my ML-based languages. :-)

Answer 1

That doesn't look like the Standard ML I learned (with $ characters in front of data constructors) but perhaps things have changed. Anyhow:

First of all there's a small typo on line 2 of rotate, you added a comma after $Cons

Basically rotate takes a tuple of three lists and assembles them in the order: first one ++ (reverse of second one) ++ third one. But it does this linearly by pulling elements from both list 1 and list 2 at the same time. The head of List 1 is cons'd to the final result (a o(1) operation). But the tail of list 2 is passed as an argument to the recursive call, and its head is cons'd onto the third argument, which amounts to reversing it.

That third argument is basically acting as an accumulator. In functional programming using an accumulator as an argument like that can be a trick for avoiding more expensive computations.

I admit to not understanding the purpose of exec. What's the context?

Answer 2

This doesn't explain the whole thing, but note that in fun rotate($Nil, y::_, a), the y::_ is a pattern that matches a list wherein you label the head of the list (first element) as y and the tail of the list (every item after the first element) as _. _ acts as a wildcard pattern.

Check out SML on Wikipedia, specifically the Mergesort implementation, for more use of :: patterns and _.