Functional: build a list of integers 1..n

Question

This is not homework. I learn standard ML myself. I know a little Schema, so this question should answer in any language.

My self-imposed purpose is to write a function that builds a list of integers from 1 to n. For example, list (7) should return [1,2,3,4,5,6,7]. A solution to O (n) would be ideal.

It is easy to build the list in reverse order (ie [n, n-1, .., 1]) in linear time:

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

My attempt to build the list forward is O (n ^ 2), because the add operation is linear.

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

My next attempt was to create a list from the end to the front (from right to left), starting from zero, tying n to the front and going back to 1. But that didn't work at all.

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

.

, i, , n <= <= m, ?

:

• n > m, .

• If n <= m, then the solution should write n, followed by the solution to the problem n + 1 <= i <= m.

This view quickly leads to a clear, concise ML code (tested):

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)))))