sml - 在列表中显示多次出现的项目，sml

Question

我正在尝试显示列表中某个元素的所有多次出现的索引。

以标准毫升计。

但我的代码显示空列表:(

这是我的代码：

    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],[]);

你能帮助我吗？

标签： smlsmlnjml

Answer 1

第一件事：

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)

which first creates the list ys @ [m], immediately throws it away, and then produces as its result index'(m + 1, xr , ys), which is exactly what the else branch does.

That is, the conditional is equivalent to

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

and thus, index' is equivalent to

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

Since you always pass the original ys along, and it is [] to start with, the result is always [].

What you need to do is to pass the extended list to the recursion, so it can become the result when the recursion terminates.
Renaming the accumulator ys to make its purpose clearer:

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;

This is inefficient, due to the repeated appending of an element to the back of a list.
It is very common to accumulate in reverse, and correct it when you're done.
(This "feels" inefficient, but it isn't.)

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;