Рекурсивный SML с симметричными отношениями
Определите в ML рекурсивный предикат isRelationSymmetric, который принимает отношение r (представленное в виде списка кортежей) и возвращает true, если r симметрично, и false в противном случае.
Вот что у меня есть до сих пор.
fun isRelationSymmetric([]) = false
| isRelationSymmetric((a,b)::rest) =
val x = [(1,2),(2,1),(2,3),(3,2)]; //suppose to come out true
val y = [(1,1),(1,3)]; //suppose to come out false
val z = [(1,2),(2,1),(1,3)]; //suppose to come out false
isRelationSymmetric(x);
isRelationSymmetric(y);
isRelationSymmetric(z);
Я смог проверить симметрию только для первых двух элементов, но мне нужно проверить остальные.
Подсказка: вам нужно больше, чем прямая рекурсия по списку отношений — вам нужно пройти по списку и, чтобы сохранить весь список. Не попадайтесь в ловушку, предполагая, что «определить функцию» означает «определить функцию ровно один».
![Учебная записка [Medium] Leetcode#22 Generate Parentheses](https://i.imgur.com/Hl2feR7b.png)
Ответы 2
fun isRelationSymmetric(relation) =
let
fun testOne((a, b), []) = false
| testOne((a, b), (c, d)::rest) =
(b = c) andalso (a = d) orelse testOne((a, b), rest);
fun test([]) = true
| test((a,b)::rest) = testOne((a, b), relation) andalso test(rest);
in
test(relation)
end;
(* Test cases *)
val x = [(1, 2), (2, 1), (2, 3), (3, 2)]; (* true *)
isRelationSymmetric(x);
val y = [(1, 1), (2, 3)]; (* false *)
isRelationSymmetric(y);
val z = [(1, 2), (2, 1)]; (* true *)
isRelationSymmetric(z);
Поскольку @jwolf, похоже, решил эту проблему, появился альтернативный подход, использующий преимущества List.exists.
fun sym(relation) =
let
fun sym'([]) = true
| sym'((a, b)::rest) =
List.exists (fn (c, d) => a = d andalso b = c) relation
andalso sym'(rest)
in
sym'(relation)
end;
Однако, для уточнения, должен ли [(1, 2), (2, 1), (2, 3), (3, 2), (3, 2)] тестироваться как симметричный или нет, поскольку есть два экземпляра (3, 2) и только 1 из (2, 3)?
Если мы хотим поймать это, мы можем использовать List.filter, чтобы найти любые реверсы пары, которую мы рассматриваем, а затем вычислить длину этого списка. Длина этого списка должна быть равна длине списка пар, соответствующих текущему.
fun sym(relation) =
let
fun sym'([]) = true
| sym'((a, b)::rest) =
let
val len = List.length(List.filter (fn (c, d) => a = d andalso b = c) relation)
val len' = List.length(List.filter (fn (c, d) => a = c andalso b = d) relation)
in
len = len' andalso sym'(rest)
end
in
sym'(relation)
end;
1) Ваш базовый случай неверен; пустое отношение симметрично. 2) Пожалуйста, укажите вашу попытку.