SML ('список * int) - ›(' список, логическое значение)

Итак, это мой вопрос: я хочу создать функцию, которая принимает список и int, затем она рекурсивно перемещается по списку, и если она находит в списке элемент, равный int, он должен вернуть весь список с элемент удален, и логическое значение, указывающее, что что-то было удалено. вот что я получил до сих пор:

fun foo ([], n) = ([],false)
  | foo ((x::xs), n) = if x = n 
                       then (xs,true)
                       else ([x] @ foo(xs,n),false);

my idea was to make the function cons the needed elements inside the tuple like this:

([x0] @ [x1] @ [x2] @ [xs], true)

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


list tuples sml
person Gnurgen    schedule 21.09.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Ваш текущий код логически близок к правильному, но, как вы знаете, он не проверяет типы из-за [x] @ foo (xs, n). foo возвращает кортеж, который нельзя добавить напрямую. Вот как это исправить:

fun foo ([], n) = ([], false)
  | foo (x::xs, n) = if x = n
                     then (xs, true)
                     else let val (xs', tf) = foo (xs, n) in (x::xs', tf) end

let необходим для извлечения списка из кортежа и выяснения, был ли n найден в конце списка. Затем мы просто вставляем кортеж обратно вместе с x, возвращаемым на передний план.

person Matt S    schedule 21.09.2012
comment
Ошибка какого типа вы получаете? Этот код компилируется и правильно работает на моей машине, хотя выдает предупреждение об использовании polyEqual. Это вызвано x = n в if. Поскольку вы сказали, что вас интересуют только целые числа, самый простой способ избежать этого - задать n и явный тип, изменив начало функции на fun foo ([], n:int) = .... Если причина вашей ошибки не в этом, скопируйте сюда все сообщение об ошибке. - person Matt S; 24.09.2012
comment
Логика: if x = n проверяет, совпадает ли заголовок списка с числом, которое вы хотите удалить. Если это так, то он просто возвращает остальную часть списка (который, естественно, является списком с удаленной головой) и true, поскольку он удалил элемент. Если заголовок не равен n, он пытается удалить n из оставшейся части списка с рекурсивным вызовом foo, сохраняя возвращаемое значение в паре (xs', tf). Наконец, мы возвращаем новую пару (x::xs, tf), которая просто помещает x обратно в начало возвращенного списка, потому что она не равна n и должна остаться. - person Matt S; 24.09.2012