functional-programming - 功能 : construct a list of integers 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;

我的下一次尝试是通过从 ni​​l 开始，将 n 附加到前面，然后向后递归到 1 来构建一个从尾到前(从右到左)的列表。但它根本不起作用。

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

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

Answer 1

使用 Basis Library ,

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

这将从尾端开始构建一个列表。如果你想到 Markdown ，

   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]

或者，

Something makes me think I need a helper function that builds un-terminated lists to be used in the recursion, but I'm stumped.

未终止列表的表示是一个函数，它接受一个列表并返回一个列表:例如，表示 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]

在这种情况下，算法可以被构造成一个普通的数据结构就足以作为累加器，但是使用延续作为累加器是一种非常强大和有用的技术，不容忽视。