Функциональный: составить список целых чисел 1..n

Question

Это не домашняя работа. Я изучаю Стандарт ML самостоятельно. Я тоже немного знаю Схему, поэтому этот вопрос должен отвечать на любом языке.

Мое добровольное назначение - написать функцию, которая создает список целых чисел от 1 до n. Например, список (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;

Моя следующая попытка состояла в том, чтобы построить список с конца на фронт (справа налево), начав с нуля, прикрепив n к фронту и вернувшись назад к 1. Но это не сработало совсем. 1011 *

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

Вот версия, использующая вспомогательную функцию и аккумулятор, поддерживающий хвостовую рекурсию:

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

Один из классических подходов - построить его в обратном порядке, а затем наоборот. Это в два раза больше O (n), что, конечно, так же, как O (n).

Answer 5

При таких проблемах со списком часто бывает проще решить более общую проблему.

Как мне создать список, содержащий целые числа i , такие что n <= i <= m </em>, по порядку?

Решение имеет базовый случай и шаг индукции:

• Если n> m , список пуст.

• Если n <= m </em>, решение состоит в том, чтобы написать n с последующим решением проблемы n + 1 <= i <= m </em>.

Это представление быстро приводит к ясному и лаконичному коду 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)))))