功能性：构造一个整数列表 1..n

Question

这不是家庭作业。我正在自学标准机器学习。我也了解一点Scheme，所以这个问题应该可以用任何一种语言来回答。

我给自己布置的作业是编写一个函数，构造一个从 1 到 n 的整数列表。例如，list(7) 应返回 [1,2,3,4,5,6,7]。O(n) 的解决方案是理想的。

在线性时间内反向构造一个列表（即 [n,n-1,..,1]）很容易：

fun list 1 = 1::nil
|   list n = n::list(n-1);

我尝试构建一个列表的时间复杂度为 O(n^2)，因为追加操作是线性的。

fun list 1 = 1::nil
|   list n = list(n-1) @ n::nil;

我的下一个尝试是从 nil 开始，将 n 附加到前面，然后向后递归到 1，从尾到前（从右到左）构建一个列表。但它根本不起作用。

fun list n = (if n = 1
              then 1
              else list(n-1) :: n) :: nil;

有些事情让我觉得我需要一个辅助函数来构建要在递归中使用的未终止列表，但我被难住了。

Answer 1

使用基础库，

fun list n = List.tabulate (n, fn x => x + 1)

使用简单的累加器，

val list =
    let fun list' k 0 = k
          | list' k n = list' (n::k) (n-1)
    in list' nil end

这构建了一个从尾端开始的列表。如果你想到减少，

   list 5
=> list' nil 5
=> list' (5::nil) 4
=> list' (4::5::nil) 3
=> list' (3::4::5::nil) 2
=> list' (2::3::4::5::nil) 1
=> list' (1::2::3::4::5::nil) 0
=> [1, 2, 3, 4, 5]

可替换地，

  

有些东西让我觉得我需要一个帮助函数来构建在递归中使用的未终止列表，但我很难过。

未终止列表的表示是一个获取列表并返回列表的函数：例如，为了表示10::_，您可以使用fn x => 10::x。

fun list n =
    let fun list' m k = if m > n then k nil else
                        list' (m+1) (fn x => k (m::x))
    in list' 1 (fn x => x) end

再一次，如果你想到减少，

   list 5
=> list' 1 (fn x => x)
=> list' 2 (fn x => (fn x => x) (1::x))
=> list' 3 (fn x => (fn x => (fn x => x) (1::x)) (2::x))
=> list' 4 (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x))
=> list' 5 (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x))
=> list' 6 (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x))
=> (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x)) nil
=> (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::nil)
=> (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::5::nil)
=> (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::4::5::nil)
=> (fn x => (fn x => x) (1::x)) (2::3::4::5::nil)
=> (fn x => x) (1::2::3::4::5::nil)
=> [1, 2, 3, 4, 5]

在这种情况下，算法的结构可以使普通数据结构足以满足累加器的要求，但使用延续作为累加器是一种非常强大且有用的技术，不应该被忽视。

Answer 2

一种经典的方法是以相反的顺序构建它，然后反转它。那是O（n）的两倍，当然就像O（n）一样。

Answer 3

这是一个解决方案：

fun list n =
  let
    fun f 1 m = m::nil
    |   f n m = m::f (n-1) (m+1)
  in
    f n 1
  end;

Answer 4

这是一个使用辅助函数和尾递归启用累加器的版本：

fun list n =
  let
    fun aux i acc = 
      if i > 0
      then aux (i-1) (i::acc)
      else acc
  in
    aux n nil
  end;

Answer 5

对于此类列表问题，解决更一般的问题通常更容易。

如何构建包含整数的列表 我 这样 n <= i <= m, ， 为了？

该解决方案有一个基本案例和一个归纳步骤：

• 如果 n > m, ，列表为空。

• 如果 n <= m, ，解决方案是写 n 接下来是问题的解决方案 n+1 <= i <= m.

这种观点可以快速生成清晰、简洁的 ML 代码（经过测试）：

fun range n m = if n > m then [] else n :: range (n+1) m
fun list n = range 1 n

Answer 6

(define (iota n)
  (let f ((i n)(a '())
    (if (zero? i)
        (reverse a)
        (f (- i 1) (cons i a)))))