Сравняване на списъци в 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").
  • Трябва да разбиете списъка с помощта на конструктор :: (против), вместо да използвате функции като 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