文章/答案/技术大牛

发布

社区首页 >问答首页 >编写一个函数`smallest_absent t`，它返回`l`中不存在的最小自然整数

问编写一个函数`smallest_absent t`，它返回`l`中不存在的最小自然整数
EN

Stack Overflow用户

提问于 2017-12-25 18:42:59

回答 2查看 99关注 0票数 0

编写签名函数smallest_absent : int_list -> int，例如调用smaller_absent l返回l中不存在的最小自然整数

let smallest_absent l =
match l with
|[] -> 0
|_ -> let m = ref (0,false) in
        while !m.(1) = false do
        if (mem l m.(0)) then !m.(1) := true ;
        else incr(m.(0));
        done;
    !m.(0);;

错误：

> while !m.(1) = false do
this expression is of type int * bool, but is used with the type 'a vect>`

我想知道我的代码出了什么问题。如果它在概念上是正确的。谢谢。

compiler-errors

ocaml

回答 2

Stack Overflow用户

回答已采纳

发布于 2017-12-25 19:24:21

类型错误说明了一切:您正在尝试对由int和bool组成的元组的对象使用向量查找_.(1)。

您要查找的函数是snd : 'a * 'b -> 'b。

同样，您应该使用fst : 'a * 'b -> 'a编写fst !m，而不是编写m.(0)

票数 2

Stack Overflow用户

发布于 2017-12-25 20:29:11

你已经有了答案，所以它更像是评论或建议。

也许在概念上它是正确的，但它具有可怕的复杂性，而且在ocaml程序中看到循环总是一件痛苦的事情(特别是在这样简单的程序中)。我建议您在递归方面考虑更多。

使用排序列表(并且没有重复项)要简单得多，在这种情况下，您只需要找到第一个i，即l[i] != i

let smallest_absent l =
  let l = List.sort_uniq compare l in
  let rec f i = function
    | [] -> i
    | h::t -> if h = i then f (i + 1) t
              else i in
  f 0 l

你可以想象进一步的优化。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/47967866

复制

相似问题

问编写一个函数`smallest_absent t`，它返回`l`中不存在的最小自然整数
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问编写一个函数`smallest_absent t`，它返回`l`中不存在的最小自然整数EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问编写一个函数`smallest_absent t`，它返回`l`中不存在的最小自然整数
EN