查找列表中 k 个不同元素的最小子序列

Question

我是 sml 的超级新手。我正在尝试编写一个简单的代码，该代码采用具有特定数字的 5 个位置的数组和 returns 包含所有数字的最小子数组的长度。但是，我收到许多无法在 Google 中找到的错误消息。谁能帮我？代码如下

 fun Min x y = if x>y then return y else return x
    local
        val a = Array.array (3,0)
        val cordela = Array.array(5,0)
        val k=0
        val front=0
        val tail=0
        val min=5
        update(cordela,0,1)
        update(cordela,1,3)
        update(cordela,2,3)
        update(cordela,3,2)
        update(cordela,4,1)
    in   
        fun loop front = 
            case k>3 of
                if sub(a,sub(cordela,front)-1) = 0 then k=k+1 else()
                update(a,sub(cordela,front)-1),sub(a,sub(cordela,front)-1)+1)
                front = front +1
            | 
                min= Min (front-tail) min
                if sub(a,sub(cordela,front)-1) = 0 then k=k-1 else()
                update(a,sub(cordela,front)-1),sub(a,sub(cordela,front)-1)-1)
                tail=tail+1

            if 5>front then loop front+1 else min
    end

我收到的错误消息是：

pl2.sml:16.13-16.15 Error: syntax error: replacing  OF with  LBRACKET
pl2.sml:18.36 Error: syntax error: inserting  LPAREN
pl2.sml:20.4 Error: syntax error: replacing  BAR with  EQUALOP
pl2.sml:22.5 Error: syntax error: inserting  LPAREN
pl2.sml:26.4 Error: syntax error: inserting  LPAREN
pl2.sml:27.2 Error: syntax error found at END

编辑：我正在尝试用 sml 编写这段代码。它是用c++写的

while(front < N){
        if( k < K ){
            if ( e[cordela[front]-1] == 0 ) k += 1;
            e[cordela[front]-1] +=1;
            front++ ;
        }
        else{
            min = MIN(front - tail ,min);
            if ( e[cordela[tail]-1] ==1 ) k -= 1;
            e[cordela[tail]-1] -= 1;
            tail++;
        }
    }

Answer 1

正如 John Coleman 所说，SML/NJ 不会给出非常有用的错误信息。您可以尝试使用 install Moscow ML，因为它会提供更好的错误消息。不幸的是，这段代码在句法层面存在一些问题，使得编译器很难给出有意义的错误。以下是一些正确语法的提示，以便您可以专注于算法问题：

.
将每个 ( 与 ) 匹配；你的 ) 太多了。
在 let 和 in 中声明 fun loop ... = ...。

完成后，解决问题的函数模板可能如下所示：

fun smallest_subarray (needles : Array.array, haystack : Array.array) =
    let
      val ... = ...
      fun loop ... = ...
    in
      if Array.length needles > Array.length haystack
      then ...
      else loop ...
    end

如果问题无解，函数return会怎样？ ~1？ NONE?

如果您正在尝试将 C++ 程序转换为 SML，请尝试以这样一种方式包含函数部分，以便很明显哪些标识符是函数的参数，并尝试以逻辑方式命名它们；我不知道 cordela、e 和 k 是什么，或者 N 是输入数组大小的函数还是常数。

由于 SML 中的惯用解决方案使用递归（函数调用自身）而不是迭代（while），您正在处理一个非平凡的算法问题和另一种范式。尝试解决一个类似但更简单的问题，其中算法更简单并应用递归范例。

例如，尝试编写一个函数，使用二进制搜索查找排序数组中元素的位置：

fun find x arr =
    let
      fun loop ... = ...
    in
      loop ...
    end

loop 函数将搜索边界（例如 i 和 j）作为参数，并且 return 或者 SOME i 如果 x 位于 i 或 NONE 位置。您可以在原始问题的方向上扩展此问题，然后尝试编写一个函数来确定输入数组 needles 是否按照 haystack 中给出的顺序出现在另一个输入数组 haystack 中=34=]。您可以首先假设 needles 和 haystack 已排序，然后假设它们未排序。

查找列表中 k 个不同元素的最小子序列

Find the smallest subsequence of k distinct elements in a list

arrays

sml

smlnj