Что именно делает этот стандартный код ML?

Question

Я читаю чисто функциональные структуры данных Криса Окасаки, и есть один пример, с которым у меня проблемы. Он расположен здесь . В частности, я не понимаю, как работают функции rotate и exec:

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

Может ли кто-нибудь выразить это глупо? Я все еще изучаю свои языки на основе ML. : -)

Answer 1

Это не объясняет всего, но обратите внимание, что в fun rotate($Nil, y::_, a) y::_ - это шаблон, который соответствует списку, в котором вы помечаете заголовок списка (первый элемент) как y и хвост списка (каждый элемент после первого элемента) как _. _ действует как шаблон подстановки.

Проверьте SML в Википедии , в частности реализацию Mergesort, для более широкого использования шаблонов :: и _.

Answer 2

Это не похоже на стандартную ML, которую я изучил (с символами $ перед конструкторами данных), но, возможно, все изменилось. В любом случае:

Прежде всего, есть небольшая опечатка в строке 2 поворота, вы добавили запятую после $Cons

В основном rotate принимает кортеж из трех списков и собирает их в следующем порядке: первый ++ (обратный второй) ++ третий. Но он делает это линейно, вытягивая элементы из списка 1 и списка 2 одновременно. Глава списка 1 доведена до конечного результата (операция o (1)). Но хвост списка 2 передается в качестве аргумента для рекурсивного вызова, и его голова сводится к третьему аргументу, что равносильно его обращению.

Этот третий аргумент в основном действует как аккумулятор. В функциональном программировании использование аккумулятора в качестве аргумента, подобного этому, может быть хитростью для избежания более дорогих вычислений.

Я признаю, что не понимал цели exec. Каков контекст?