Показать несколько вхождений элементов в списке, sml - PullRequest
Новая
       106

Показать несколько вхождений элементов в списке, sml

0 голосов
/ 09 июля 2020

Я пытаюсь показать индексы всех множественных вхождений элемента в списке.

в стандартном ml.

, но мой код показывает пустой список: (

это мой код: 

    fun index(item, xs,ys) =
let
fun index'(m, nil , ys) = (
  SOME (ys) )
| index'(m, x::xr , ys) = if x = item then(
  (ys @ [m]);
  index'(m + 1, xr , ys)
  )
  else index'(m + 1, xr,ys)
in
index'(0, xs , ys)
end;


index(1,[1,2,1,4,5,1],[]);

вы можете мне помочь?

1 Ответ

2 голосов
/ 10 июля 2020

Вначале обо всем:

  1. index должен принимать два аргумента; элемент, который нужно искать, и список, в котором его нужно искать. Параметр накопления принадлежит вспомогательной функции.
  2. Бессмысленно всегда производить SOME чего-то и никогда NONE.

Давайте сначала исправим это. 

fun index (item, xs) =
    let
        fun index'(m, nil , ys) = ys
          | index'(m, x::xr, ys) = if x = item then(
                                       (ys @ [m]);
                                       index'(m + 1, xr , ys)
                                   )
                                   else index'(m + 1, xr,ys)
    in
        index'(0, xs, [])
end;

Теперь вам не нужно передавать дополнительный параметр аккумулятора при использовании index. Также невозможно начать с чего-то другого, кроме [].

Ваша следующая и основная проблема - 

(ys @ [m]);
index'(m + 1, xr , ys)

, который сначала создает список ys @ [m], сразу его отбрасывает, а затем выдает в качестве результата index'(m + 1, xr , ys), что и делает ветвь else.

То есть условное выражение эквивалентно 

if x = item
then index'(m + 1, xr, ys)
else index'(m + 1, xr, ys)

и, следовательно, index' эквивалентно 

fun index'(m, nil, ys) = ys
  | index'(m, x::xr, ys) = index'(m + 1, xr, ys)

Поскольку вы всегда передаете исходный ys, а для начала это [], результат всегда будет [].

То, что вам нужно нужно передать расширенный список в рекурсию, чтобы он мог стать результатом, когда рекурсия завершится. Переименование аккумулятора ys, чтобы прояснить его назначение: 

fun index (item, xs) =
    let
        fun index'(i, nil, accumulator) = accumulator
          | index'(i, x::xr, accumulator) = if x = item
                                            then index' (i + 1, xr, accumulator @ [i])
                                            else index' (i + 1, xr, accumulator)
    in
        index'(0, xs, [])
end;

Это неэффективно из-за многократного добавления элемента в конец списка. Очень часто происходит накопление в обратном порядке и исправление, когда вы закончите. (Это "кажется" неэффективным, но это не так.) 

fun index (item, xs) =
    let
        fun index'(i, nil, accumulator) = List.reverse accumulator
          | index'(i, x::xr, accumulator) = if x = item
                                            then index' (i + 1, xr, i::accumulator)
                                            else index' (i + 1, xr, accumulator)
    in
        index'(0, xs, [])
end;
...