SML: функция с несколькими выходами - PullRequest
Новая
       13

SML: функция с несколькими выходами

3 голосов
/ 19 декабря 2011

Я новичок в SML, и я хотел бы обновить свою функцию, чтобы она имела два выхода: список И 1 или 0. Функция была предложена здесь: SML: Удалить запись из списка . Возвращает обновленный список без строки, содержащей «elem». 

fun removeElem elem myList = filter (fn x => x <> elem) myList

Функция должна возвращать новый список И 1, если сырье было удалено. В противном случае он должен вернуть старый список И 0.

Любой намек или пример высоко ценится. Спасибо.

Ответы [ 2 ]

4 голосов
/ 19 декабря 2011

Как было сказано в некоторых из ваших предыдущих вопросов; Возвращение 0 или 1 в качестве индикатора того, что произошло, является действительно плохим дизайном, так как вы не получаете никаких гарантий от типов, независимо от того, получите ли вы -42 в результате. Поскольку вы работаете со строго типизированным языком, вы можете использовать это в своих интересах:

  1. Самое очевидное, что нужно сделать вместо этого, это вернуть логическое значение, поскольку на самом деле это то, что вы эмулируете с 0 и 1. В этом случае вы можете вернуть пару (true, modified_list) или (false, original_list).
  2. Поскольку вы хотите связать некоторые данные с результатом, есть еще одна, возможно, для некоторых, менее очевидная вещь; Вернуть результат в качестве опции, указав изменение в списке как SOME modified_list, а указание без изменений как NONE.

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

Один путь был бы таким: 

fun removeElem _ [] = (false, [])
  | removeElem elem (x::xs) =
    let
      val (b, xs') = removeElem elem xs
    in
      if elem = x then
        (true, xs')
      else
        (b, x::xs')
    end

Другой способ - использовать параметр аккумулятора для хранения результирующего списка. 

fun removeElem elem xs =
    let
      fun removeElem' [] true res = SOME (rev res)
        | removeElem' [] false _ = NONE
        | removeElem' (x::xs) b res =
          if elem = x then
            removeElem' xs true res
          else
            removeElem' xs b (x::res)
    in
      removeElem' xs false []
    end

Поскольку решение строится в обратном порядке, мы возвращаем результат непосредственно перед его возвратом. Это гарантирует, что мы не должны использовать дорогостоящую операцию добавления при добавлении элементов в список результатов: res @ [x]

4 голосов
/ 19 декабря 2011

Обратите внимание, что все функции SML принимают один вход и возвращают один выход. Вместо этого подумайте о возврате кортежа, содержащего новый список и флаг, указывающий, были ли удалены какие-либо элементы. Одна возможность состоит в том, чтобы использовать пару функций из стандартной базы, чтобы проверить, находится ли elem в myList, и создать кортеж, состоящий из этого и результатов из filter, показанных в вопросе. Тест может выглядеть так: 

Option.isSome (List.find (fn x => x = elem) myList)

Есть более краткие способы написать это, но это показывает идею. Обратите внимание, что он возвращает bool вместо int; это более точно, поэтому я не буду преобразовывать в целые числа, запрошенные в вопросе.

Недостаток вышесказанного заключается в том, что он требует обхода списка дважды. Чтобы избежать этого, рассмотрим тип , который должна возвращать функция: кортеж списка без elem и флаг, показывающий, были ли удалены какие-либо elem. Затем мы можем написать функцию, которая принимает новое значение и (действительный) кортеж и возвращает действительный кортеж. Одна возможность: 

fun update(x, (acc, flag)) = if x = elem then (acc, true) else (x :: acc, flag)

Затем мы можем применить update к каждому элементу myList один за другим. Поскольку мы хотим, чтобы порядок в списке оставался неизменным, кроме удаленных элементов, мы должны пройти через myList справа налево, накапливая результаты в первоначально пустой список. Функция foldr сделает это напрямую: 

foldr update ([], false) myList

Однако в функции высшего порядка foldr скрыто много логики.

Чтобы использовать это как учебное упражнение, я бы предложил использовать эту задачу для реализации функции несколькими способами:

  • как рекурсивная функция
  • как хвостовая рекурсивная функция
  • с использованием функций высшего порядка foldl и foldr

Понимание различий между этими версиями поможет понять, как работает SML. Для каждой версии позволяют типам ориентироваться.

...