1

我们想在给定的非空整数列表中找到最大值。然后我们必须比较列表中的元素。由于数据值是作为序列给出的，我们可以从列表的开头或结尾进行比较。以两种方式定义。a) 从头比较 b) 从尾比较（当数据值在列表中时，我们怎么做？）没有辅助功能。

我一直在使用递归函数，但似乎无法弄清楚如何比较列表中的两个值。

fun listCompare [] = 0
  | listCompare [x] = x
  | listCompare (x::xs) = listCompare(xs)

这会将列表分解为最后一个元素，但是我如何开始比较和组合列表呢？

4

2 回答 2

2

您可以比较给定列表的前两个元素，并将较大的元素保留在列表中并删除另一个。一旦列表只有一个元素，那么你就有了最大值。在 a) 的功能伪代码中，它大致如下所示：

lmax []  = error "empty list"
lmax [x] = x
lmax (x::y::xs) = 
  if x > y then lmax (x::xs)
  else          lmax (y::xs)

对于 b)，您可以先反转列表。

于 2013-09-17T22:52:57.073 回答
0

这就是SML 列表库foldl中的(or foldr) 函数的用途：

foldl : ((`a * `b) -> `b) -> `b -> `a list -> `b

您可以简单地添加一个匿名函数来将当前元素与累加器进行比较：

fun lMax l =
    foldl (fn (x,y) => if x > y then x else y) (nth l 0) l

该nth函数只需使用int list : landint : 0来返回列表中的第一个元素。由于 SML 中的列表以递归方式编写为 : h :: t，因此检索第一个元素是一个O(1)操作，使用该foldl函数大大增加了代码的优雅性。拥有函数式语言的全部意义在于定义抽象以将匿名函数作为高阶函数传递，并将抽象类型定义与具体函数重用。

于 2017-08-16T05:18:38.210 回答