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

Question

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

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

Моей следующей попыткой было составить список от конца к началу (справа налево), начав с нуля, присоединив 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

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

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

Решение имеет базовый вариант и этап индукции:

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

• Если n <= м, решение состоит в том , чтобы написать n за этим следует решение проблемы n+1 <= я <= м.

Такое представление быстро приводит к созданию четкого и сжатого 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)))))