Functional: construct a list of integers 1..n

Question

This is not homework. I'm learning Standard ML on my own. I know a bit of Scheme, too, so this question ought to be answerable in either language.

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

It's easy to construct a list in reverse (i.e., [n,n-1,..,1]) in linear time:

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

My attempt to construct a list going forward is O(n^2) because the append operation is linear.

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

My next attempt was to build a list from the end to the front (right to left) by starting with the nil, attaching n to the front, and recursing backwards to 1. But it didn't work at all.

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

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

Answer 1

One classic approach is to build it in reverse order, then reverse it. That's two times O(n), which is of course just as O(n).

Answer 2

Here's a solution:

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 3

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

Answer 4

Here's a version using a helper function and a tail-recursion-enabling accumulator:

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

Using the Basis Library,

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

With a simple accumulator,

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

This builds a list starting from the tail end. If you think of the reductions,

   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]

Alternatively,

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

A representation of an unterminated list is a function which takes a list and returns a list: for example, to represent 10::_, you could use 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

Once again, if you think of the reductions,

   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]

In this case, the algorithm can be structured such that an ordinary data structure suffices for the accumulator, but using a continuation as an accumulator is a very powerful and useful technique that should not be overlooked.

Answer 6

With list problems like these, it is often easier to solve a more general problem.

How do I build a list containing the integers i such that n <= i <= m, in order?

The solution has a base case and an induction step:

• If n > m, the list is empty.

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

This view leads quickly to 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