Как исправить этот код SML для работы по назначению?

Question

Прямо сейчас у меня есть функция SML:

method([1,1,1,1,2,2,2,3,3,3]); 

возвращается:

val it = [[2,2,2],[3,3,3]] : int list list 

, но мне нужно его вернуть:

val it = [[1,1,1,1],[2,2,2],[3,3,3]] : int list list 

Это мой текущий код:

- fun method2(L: int list) = 
= if tl(L) = [] then [hd(L)] else 
= if hd(tl(L)) = hd(L) then hd(L)::method(tl(L)) else [hd(L)]; 

- fun method(L: int list) = 
= if tl(L) = [] then [] else 
= if hd(tl(L)) = hd(L) then method(tl(L)) else 
= method2(tl(L))::method(tl(L)); 

Как вы видите, это пропускает первый вызов метода2. Любые идеи о том, как я могу это исправить? Я полностью в тупике.

Answer 1

Ваша проблема здесь if hd(tl(L)) = hd(L) then method(tl(L)) else. Это говорит, что голова хвоста равна голове, а затем продолжите обработку, но не добавьте ее в список результатов. это пропустит первый смежный кусок равных значений. Я бы предложил отделить обязанности этих функций немного больше. Способ сделать это состоит в том, чтобы удалить method2 из следующего смежного фрагмента значений и вернуть пару, в которой первый элемент будет удален смежным фрагментом, а второй элемент будет иметь оставшийся список. Например, method2([1, 1, 1, 2, 2, 3, 3]) = ([1, 1, 1], [2, 2, 3, 3]) и method2([2, 2, 3, 3]) = ([2, 2], [3, 3]). Теперь вы можете просто позвонить method2, пока вторая часть пары не будет nil.

Answer 2

Я не совсем уверен, что вы пытаетесь сделать с вашим кодом. Я бы рекомендовал создать хвост рекурсивной вспомогательную функцию, которая передается три аргумента:

1) The list of lists you are trying to build up 
2) The current list you are building up 
3) The list you are processing 

В вашем примере, типичный вызов где-то в середине расчета будет выглядеть так:

helper([[1,1,1,1]], [2,2],[2,3,3,3]) 

рекурсия будет работая, посмотрев на заголовок последнего аргумента ([2,3,3,3]), а также возглавляющий список, который в настоящее время строится ([2,2]), и, поскольку они одинаковы - 2 в конце последнего аргумента шунтируются к списку:

helper([[1,1,1,1]], [2,2,2],[3,3,3]) 

в следующем шаге рекурсии головки затем сравниваются и оказываются разными (2 = 3!), Поэтому функция помощника будет поставить средний список в начале списка списков:

helper([[2,2,2], [1,1,1,1]], [3],[3,3]) 

средний список повторно инициализируется [3], поэтому она начнет расти

в конце концов вы достигнете что-то вроде этого:

помощник ([[2,2,2], [1,1 , 1,1]], [3,3,3], [])

[3,3,3] затем прикрепляется к списку списков, и возвращается обратный этого списка.

Как только такая вспомогательная функция определена, основной метод проверяет пустой список и, если не пуст, инициализирует первый вызов вспомогательной функции. Следующий код выводит эти идеи - используя стиль сопоставления шаблонов, а не hd и tl (я не очень люблю использовать эти функции явно - это делает код слишком похожим на Lisp).Если это домашнее задание, вы должны, вероятно, основательно понять, как это работает, а затем перевести его на код с участием hd и tl, так как ваш профессор будет рассматривать его как плагиат, если вы используете вещи, которые еще не изучили, и не сделали это своей собственной работой :

fun helper (xs, ys, []) = rev (ys::xs) 
| helper (xs, y::ys, z::zs) = 
     if y = z 
      then helper(xs, z :: y :: ys, zs) 
      else helper((y::ys)::xs,[z],zs); 

fun method [] = [] 
| method (x::xs) = helper([],[x],xs);