sml - 计算排序列表中有多少元素大于给定谓词

Question

我正在尝试创建一个函数，用于查找在给定的排序列表中有多少元素大于第一个元素除以 2 的结果。例如给定一个列表 [3,3,4,5,6,7,8,9,11]，第一个元素是 3，较大的数字除以 2 是 7,8,9,11 因此函数返回 4。

到目前为止我已经这样做了，但它不起作用。 a 元素是列表的第一个，给出它是为了更容易。

fun findlarger a [] =
  | findlarger [] = 0
  | findlarger [x] = 0
  | findlarger (x::xs) =
    let
      val a = ref a;
    in
      if !a < x/2 then length (xs) + 1 else findlarger (a, xs)
    end

Answer 1

我什至不知道从哪里开始指出您代码的问题。看来您误解了函数式编程的基础知识。

• 首先你不应该使用引用(除非你知道你在做什么，否则它可能仍然是错误的)，你应该使用递归。
• 您还没有声明您的函数采用相同数量的参数。在第一个子句中，您使用 2 个柯里化(Currying)参数定义了它，在其余子句中您只有一个参数，而在代码的倒数第二行中，您使用一对作为参数调用函数。
• 您的第一个函数子句没有主体。
• "<"不是 sml 中的严格小于运算符。正如您在那里写的那样，它是一个字符串。

修复您的原始代码将导致类似这样的结果。请注意，第一个元素总是放回列表中，这样我们就知道要与什么进行比较。

fun findlarger [] = 0
  | findlarger [x] = 0
  | findlarger (x::y::xs) =
    if y > x*2 then
      1 + findlarger(x :: xs)
    else
      findlarger(x :: xs)

然而，您也可以使用内部辅助函数来完成 x*2 的计算，这样就不会每次都计算

fun findlarger [] = 0
  | findlarger (x::xs) =
    let
      val xx = 2*x
      fun f [] = 0
        | f (y::ys) =
          (if y > xx then 1 else 0) + f ys
    in
      f xs
    end

如果使用其他答案中建议的高阶函数，则应避免遍历列表两次(首先过滤掉元素，然后计算剩余元素)。您应该只浏览一次列表，然后计算与给定谓词匹配的元素。
要完成此功能，您可以使用其中一个折叠功能。在大多数情况下，使用 foldl 是有意义的，因为它将以尾递归的方式从左到右遍历列表。

fun p (x, y) = if y > 2*x then 1 else 0

fun f [] = 0
  | f (x::xs) = foldl (fn (a,b) => b + p(x, a)) 0 xs