如何在SML中不使用递归按间隔步长截取列表指定区间的元素

实现思路 #

你可以用foldl携带双状态完成需求，全程不需要递归，也不需要调用list.nth：

• 给foldl设置初始状态为(当前下标: int, 结果列表: 'a list)，初始值是(0, [])
• 每遍历到一个列表元素，先做三层条件判断：
  1. 当前下标 >= 起始值start
  2. 当前下标 <= 结束值end
  3. (当前下标 - start) mod interval == 0
• 满足条件就把当前元素追加到结果列表，不满足就跳过，每次遍历结束把下标+1更新状态
• 遍历完成后取出状态中的结果列表即可，如果你是用头插法存元素，最后反转一次结果就和预期顺序一致

示例代码（Standard ML） #

注意end是SML关键字，所以参数名用end'规避冲突：

fun cutt lst (start, end', interval) =
  let
    val (_, res) = foldl (fn (elem, (idx, acc)) =>
      if idx >= start andalso idx <= end' andalso (idx - start) mod interval = 0
      then (idx + 1, acc @ [elem]) (* 尾插法不需要反转，小列表性能可接受 *)
      else (idx + 1, acc)
    ) (0, []) lst
  in
    res
  end;

测试效果和你给出的示例完全一致：

cutt [1,2,3,4,77,8,7] (1,5,2);
(* 输出: val it = [2,4,8] : int list *)

如果担心列表拼接的性能，可以改用头插最后反转的写法，性能更高：

fun cutt lst (start, end', interval) =
  let
    val (_, res) = foldl (fn (elem, (idx, acc)) =>
      if idx >= start andalso idx <= end' andalso (idx - start) mod interval = 0
      then (idx + 1, elem :: acc)
      else (idx + 1, acc)
    ) (0, []) lst
  in
    rev res
  end;

内容的提问来源于stack exchange，提问作者memeeol