Сравнение списков в Standard ML - PullRequest
Новая
       13

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

1 голос
/ 17 ноября 2011

Я чрезвычайно новичок в 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);

Ответы [ 2 ]

2 голосов
/ 17 ноября 2011

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

  • Если голова хз больше головы у, может появиться голова хз у тебя в хвосте.
  • Если голова xs совпадает с головой ys, мы удалить обе две головы.
  • Если голова хз меньше головы х, голова хз не может быть в 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)
1 голос
/ 17 ноября 2011

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

x :: minus(x,ys)

Эта секунда x должна быть xs.

...