SML программа для удаления символа из строки - PullRequest
Новая
       16

SML программа для удаления символа из строки

0 голосов
/ 17 февраля 2019

Я новичок в SML, пытаюсь написать рекурсивную программу для удаления символов из строки: 

remCharR: char * string -> string

До сих пор написал эту нерекурсивную прогу.Нужна помощь в написании рекурсивного. 

- fun stripchars(string,chars) = let
=    fun aux c =
=       if String.isSubstring(str c) chars then
=          ""
=       else
=          str c
= in
=     String.translate aux string
= end
= ;

1 Ответ

0 голосов
/ 18 февраля 2019

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

Вот один из способов использования явной рекурсии путем преобразования в список: 

fun remCharR (c, s) =
    let fun rem [] = []
          | rem (c'::cs) =
              if c = c'
              then rem cs
              else c'::rem cs
    in implode (rem (explode s)) end

Преобразование в список (с использованием explode) неэффективно, поскольку вы можете перебирать элементы строки без созданиясписок одинаковых элементов.Генерирование списка не удаленных символов не обязательно является плохим выбором, так как с неизменяемыми строками вы не знаете точно, как долго будет длиться ваш конечный результат без предварительного прохождения строки.Функция String.translate создает список строк, которые затем объединяет.Вы можете сделать что-то похожее.

Так что, если вы замените первоначальное преобразование в список обходом строки ( fold ), 

fun fold_string f e0 s =
    let val max = String.size s
        fun aux i e =
          if i < max
          then let val c = String.sub (s, i)
               in aux (i+1) (f (c, e))
               end
          else e
    in aux 0 e0 end

, вы можете создать строку функция фильтра (очень похожая на функцию String.translate, которую вы уже нашли, но менее общую): 

fun string_filter p s =
    implode (fold_string (fn (c, res) => if p c then c::res else res) [] s)

fun remCharR (c, s) =
    string_filter (fn c' => c <> c') s

Кроме того, вы заметите, что она случайно переворачивает строку, потому что онаскладки слева;Вы можете свернуть справа (эффективная, но другая семантика) или перевернуть список (неэффективный).Я оставлю это в качестве упражнения для выбора и улучшения.

Как вы можете видеть, во избежание String.translate я построил другие универсальные вспомогательные функции, чтобы функция remCharR не содержалаявная рекурсия, но скорее зависит от более читаемых высокоуровневых функций.

Обновление: String.translate на самом деле делает некоторые довольно умные вещи в отношении.использование памяти.

Вот Moscow ML версия String.translate: 

fun translate f s =
    Strbase.translate f (s, 0, size s);

с Strbase.translate, похожая на: 

fun translate f (s,i,n) =
    let val stop = i+n
    fun h j res = if j>=stop then res
              else h (j+1) (f(sub_ s j) :: res)
    in revconcat(h i []) end;

и с помощью вспомогательной функции revconcat: 

fun revconcat strs =
    let fun acc [] len       = len
          | acc (v1::vr) len = acc vr (size v1 + len)
        val len = acc strs 0
        val newstr = if len > maxlen then raise Size else mkstring_ len
        fun copyall to []       = () (* Now: to = 0. *)
          | copyall to (v1::vr) =
        let val len1 = size v1
            val to   = to - len1
        in blit_ v1 0 newstr to len1; copyall to vr end
    in copyall len strs; newstr end;

Таким образом, сначала вычисляется общая длина итоговой строки путем суммирования длины каждой подстроки, генерируемой String.translate, а затем используетсяИзменяемые внутренние функции компилятора (mkstring_, blit_) для копирования переведенных строк в итоговую строку результата.

Вы можете добиться аналогичной оптимизации, если знаете, что каждый символ во входной строке приведет кв 0 или 1 символов в выходной строке.Функция String.translate не может, поскольку результатом перевода может быть несколько символов.Таким образом, альтернативная реализация использует CharArray.Например:

  1. Найдите количество элементов в новой строке, 

    fun countP p s =
    fold_string (fn (c, total) => if p c
                                  then total + 1
                                  else total) 0 s

  2. Создайте временное, изменяемое CharArray, обновитеи конвертируем его в строку: 

    fun string_filter p s =
    let val newSize = countP p s
        val charArr = CharArray.array (newSize, #"x")
        fun update (c, (newPos, oldPos)) =
            if p c
            then ( CharArray.update (charArr, newPos, c) ; (newPos+1, oldPos+1) )
            else (newPos, oldPos+1)
    in fold_string update (0,0) s
     ; CharArray.vector charArr
    end

fun remCharR (c, s) =
    string_filter (fn c' => c <> c') s

Вы заметите, что remCharR - то же самое, только реализация string_filter варьировалась, благодаря некоторой степени абстракции.Эта реализация использует рекурсию через fold_string, но в остальном она сопоставима с для цикла , который обновляет индекс массива.Так что, хотя это и рекурсивно, но и не очень абстрактно.

Учитывая, что вы получаете сравнимые с оптимизацией оптимизации, использующие String.translate без сложностей с изменяемыми массивами низкого уровня, я не думаю, что это стоитначать испытывать проблемы с производительностью.

...