Сравнение списков в Standard ML

Я новичок в SML, и мы только что получили первое задание по программированию для класса, и мне нужно немного разобраться.

Вопрос в следующем: напишите функцию ML с именем minus: int list * int list -> int list, которая принимает два списка неубывающих целых чисел и создает список неубывающих целых чисел, полученный путем удаления элементов из первого входного списка, которые также находятся во втором входном списке.

Например,

minus( [1,1,1,2,2], [1,1,2,3] ) = [1,2]

minus( [1,1,2,3],[1,1,1,2,2] ) = [3]

Вот моя попытка ответить на вопрос. Может ли кто-нибудь сказать мне, что я делаю неправильно? Я не совсем понимаю синтаксический анализ списков.

fun minus(xs,nil) = []
| minus(nil,ys) = []
| minus(x::xs,y::ys) = if x=y then minus(xs,ys) else x :: minus(x,ys);

Вот исправление, которое я только что сделал, я думаю, это прямо сейчас?

fun minus(L1,nil) = L1
| minus(nil,L2) = []
| minus(L1,L2) = if hd(L1) > hd(L2) then minus(L1,tl(L2))
    else if hd(L1) = hd(L2) then minus(tl(L1),tl(L2))
    else hd(L1) :: minus(tl(L1), L2);

list sml
person Trance339    schedule 16.11.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Я думаю, что ваше исправление правильное. Используя тот факт, что два списка xs и ys отсортированы, мы имеем:

  • Если голова xs больше, чем голова ys, голова xs может оказаться в хвосте ys.
  • Если голова xs такая же, как голова ys, мы удаляем обе головы.
  • Если голова xs меньше, чем голова ys, голова xs не может появиться в ys, и мы помещаем ее в список результатов.

Однако у меня есть некоторые незначительные комментарии к вашей функции:

  • [] и nil одинаковы. Я думаю, что более понятно использовать только [].
  • Переменные, обозначающие списки, обычно имеют форму xs, ys,... (строчные буквы заканчиваются на «s»).
  • Вы должны разбить список с помощью конструктора :: (cons), а не использовать такие функции, как hd и tl.

Вот улучшенная версия:

fun minus(xs, []) = xs
  | minus([], ys) = []
  | minus(x::xs, y::ys) = if x > y then minus(x::xs, ys)
                          else if x = y then minus(xs, ys)
                          else x::minus(xs, y::ys)
person pad    schedule 17.11.2011

arrow_upward
1
arrow_downward

У вас есть тип в вашем предложении else:

x :: minus(x,ys)

Второй x должен быть xs.

person sepp2k    schedule 16.11.2011
comment
Это работает лучше, но теперь, как вы можете видеть на примерах, которые я разместил, ответ для второго просто [3], и я получаю [2,3]. Я не понимаю, как я мог сравнить каждое число в первом списке с каждым числом во втором списке. - person Trance339; 17.11.2011
comment
@user: вам не нужно сравнивать каждое число из одного списка с каждым числом в другом списке. Вы можете сделать это (и, вероятно, должны), просматривая каждый список только один раз. В частности, неправильно тот факт, что вы забываете и x, и y, если они не равны. Вам нужно использовать свойство сортировки списков. - person sepp2k; 17.11.2011