SML 将两个函数（最小值、最大值）合并为一个（范围）

Question

无论如何，将这两个函数组合起来，它接受一个列表并返回最高和最低的元素。想要同时输出两者。干杯

fun max[] = raise Empty 
    max[x] = x
    max(x::xs) =
  let 
    val y = max xs
  in
    if x > y then x else y
  end;

fun min[] = raise Empty 
  min[x] = x
  min(x::xs) =
     let 
       val y = min xs
     in
       if x < y then x else y
  end;

Answer 1

这里有一个提示。使用相同的基本逻辑。编写一个函数

minmax

返回一对

(min,max)

形式的值，然后在递归步骤中，使用模式匹配来提取这两个值。模板是：

fun minmax [] = raise Empty
|   minmax [x] = (x,x)
|   minmax (x::xs) =
  let 
    val (a, b) = minmax xs
  in
    <fill in the code>
  end;

在上面，

a

是最小值，

b

是最大值。给定

a

和

b

以及第三个值

x

，返回

(x,b)

或

(a,x)

或

(a,b)

，具体取决于不等式的表现。您将需要多个

if

。

Answer 2

这里有一个不同的提示：使用一个辅助函数来存储当前（最小值，最大值）并在完成迭代时返回这些值。一个模板是：

fun minmax [] = raise Empty
  | minmax (y::ys) =
    let fun helper [] (min, max) = ...
          | helper (x::xs) (min, max) = ...
    in helper ys (y, y) end

Answer 3

sshine 所建议的方法本质上是折叠。我们的状态可以是一个

(int * int) option

值。空列表没有最小值或最大值，我们可以将其表示为

NONE

。如果当前状态是

NONE

，显然任何值都是最小值 和 最大值。我们可以根据当前值是小于最小值还是大于最大值来更新该值。

首先了解如何实施

foldl

可能会有所帮助。

fun foldl _ init [] = init
  | foldl f init (x::xs) = 
    let
      val init' = f (x, init)
    in
      foldl f init' xs
    end;

fun minmax lst =
  let
    fun f(x, NONE) = SOME (x, x)
      | f(x, (acc as SOME (min, max))) =
        if x < min then SOME (x, max)
        else if x > max then SOME (min, x)
        else acc
  in
    foldl f NONE lst
  end;

如果我们评估

minmax [1, 2, 6, 3, 9, 0]

，现在看起来像：

minmax [1, 2, 6, 3, 9, 0]
foldl f NONE [1, 2, 6, 3, 9, 0]
foldl f (SOME (1, 1)) [2, 6, 3, 9, 0]
foldl f (SOME (1, 2)) [6, 3, 9, 0]
foldl f (SOME (1, 6)) [3, 9, 0]
foldl f (SOME (1, 6)) [9, 0]
foldl f (SOME (1, 9)) [0]
foldl f (SOME (0, 9)) []
SOME (0, 9)