Ошибка, которую вы получаете, вызвана тем, что компилятор SML не может определить тип вашего кортежа.#1 и #2 - это не функции, а макросы, которые работают с кортежами произвольного типа, если они имеют два элемента.Поэтому быстрый способ преодолеть эту проблему - добавить аннотацию типа
fun getDirectNodes(startNode, Tuples : (int * int) list, list) = ...
. Но поскольку вы опубликовали большую часть своего решения, я хотел бы дать некоторые общие отзывы о нем:
reverse
Ваша реализация reverse делает несколько вещей неправильно:
Когда вы пишете if L = [] ..., вы заставляете L быть тип равенства, ''a.Это может показаться странным, поскольку вы просто проверяете, что L пусто, но прежде чем L = [] может быть допустимым выражением, его элементы также должны быть сопоставимы для равенства.Это можно решить с помощью сопоставления с образцом или с помощью функции List.null (которая использует сопоставление с образцом), чтобы избежать ограничения типа равенства.
Вместо него используются hd и tlсопоставления с образцом;Эти функции частичные , что означает, что они могут произойти сбой во время выполнения, если не используются должным образом.Вы можете избежать их, используя сопоставление с образцом в пустом и непустом списке.
Используется рекурсивно @, что очень неэффективно: ваш алгоритм O (n²) , поскольку для левой части @ требуется линейное время для разрешения каждого рекурсивного вызова, то есть геометрическая сложность:
reverse [1,2,3,4]
~> reverse [2,3,4] @ [1]
~> reverse [3,4] @ [2] @ [1]
~> reverse [4] @ [3] @ [2] @ [1]
~> reverse [] @ [4] @ [3] @ [2] @ [1]
В этот момент reverse имеетиспользуется O (n) пространство стека.
~> [] @ [4] @ [3] @ [2] @ [1]
~> [4] @ [3] @ [2] @ [1] (* 1 recursive call in @ *)
~> [4,3] @ [2] @ [1] (* 2 recursive calls in @ *)
~> [4,3,2] @ [1] (* 3 recursive calls in @ *)
~> [4,3,2,1] (* 4 recursive calls in @ *)
И в этот момент reverse использовало O (n + (n-1) + ... + 1) = O (n²) рекурсивные вызовы.
На самом деле есть встроенная функция с именем rev.
Она реализована следующим образом:
fun rev xs =
let fun rev_helper [] xs_bw = xs_bw
| rev_helper (x::xs) xs_bw = rev_helper xs (x::xs_bw)
in rev_helper xs [] end
и его вызов выглядит следующим образом:
rev [1,2,3,4]
~> rev_helper [1,2,3,4] []
~> rev_helper [2,3,4] [1] (* 1 recursive call *)
~> rev_helper [3,4] [2,1] (* 1 recursive call *)
~> rev_helper [4] [3,2,1] (* 1 recursive call *)
~> rev_helper [] [4,3,2,1] (* 1 recursive call *)
~> [4,3,2,1]
, который использует heap память вместо stack memory и O (n) рекурсивные вызовы.
getDirectNodes
Вот неполный список комментариев:
То же самоевещь в отношенииздесь применяется равенство типовTuples = [].
Имея list в качестве накопленного результата - это аккуратно!Я мог бы назвать это чем-то более описательным, точно так же, как я бы назвал Tuples что-то вроде edges, чтобы описать его содержимое , а не type .
Хотя использование накопленного результата, например list, является аккуратным, это означает, что ваша функция принимает в качестве входных данных пустой список.Что делать, если вызывающий абонент передает ему непустой список?Предоставление этого дополнительного аргумента оставляет место для ошибок, поэтому спрячьте его во внутренней функции, как я сделал с rev_helper.
Используйте сопоставление с образцом вместо hd и tl.
Использование reverse кажется значимым: вы испытали, что list заканчивается наоборот.Но вместо вызова reverse на list для каждого рекурсивного вызова, сделайте это один раз в самом конце (когда Tuples пусто).
Учитывая этот совет, вот вариант вашего кода:
fun getDirectNodes (startNode, []) = []
| getDirectNodes (startNode, (x, endNode) :: edges) =
if x = startNode
then endNode :: getDirectNodes (startNode, edges)
else getDirectNodes (startNode, edges)
И вариант, который использует внутреннюю хвостовую рекурсивную функцию и один rev в конце:
fun getDirectNodes (startNode, edges) =
let fun helper ([], endNodes) = endNodes
| helper ((x, endNode) :: edges, endNodes) =
if x = startNode
then helper (edges, endNode :: endNodes)
else helper (edges, endNodes)
in rev (helper (edges, [])) end
Вот как я мог бы сделать это, используя функции более высокого порядка:
fun getDirectNodes (startNode, edges) =
List.map #2 (List.filter (fn (x, _) => x = startNode) edges)
Причина, по которой я не получаю предупреждение относительно.Я использую #2 здесь, несмотря на отсутствие каких-либо аннотаций типов, потому что я сопоставляю шаблоны с элементами edges в коде fn (x, _) => ....Это ограничивает edges списком из двух кортежей.
Выполнение этого:
- getDirectNodes (1, [(1,2),(1,3),(2,3),(2,4)]);
> val it = [2, 3] : int list