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

Это не домашнее задание. Я изучаю Standard ML самостоятельно. Я тоже немного знаю 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;

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

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

Что-то заставляет меня думать, что мне нужна вспомогательная функция, которая создает незавершенные списки для использования в рекурсии, но я в тупике.


recursion functional-programming scheme sml
person Barry Brown    schedule 06.05.2009    source источник

Ответы (6)


arrow_upward
4
arrow_downward

Используя 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

Это создает список, начиная с конца. Если подумать о сокращениях,

   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]

В этом случае алгоритм может быть структурирован так, что для аккумулятора достаточно обычной структуры данных, но использование продолжения в качестве аккумулятора является очень мощным и полезным приемом, который не следует упускать из виду.

person ephemient    schedule 06.05.2009
comment
Вы заметите, что оба метода являются хвостовыми рекурсивными. Это еще одна вещь, для которой полезны аккумуляторы. Подумайте о том, как оптимизирующий компилятор может использовать аккумулятор для преобразования функций без хвостовой рекурсии в функции с хвостовой рекурсией, и посмотрите, сможете ли вы структурировать свои алгоритмы так, чтобы они соответствовали этой цели. - person ephemient; 06.05.2009

arrow_upward
3
arrow_downward

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

person unwind    schedule 06.05.2009
comment
Пришлось искать, как сделать реверс линейного времени. Как только я получил это, чтобы работать, остальное было легко. - person Barry Brown; 06.05.2009

arrow_upward
3
arrow_downward

Вот решение:

fun list n =
  let
    fun f 1 m = m::nil
    |   f n m = m::f (n-1) (m+1)
  in
    f n 1
  end;
person TrayMan    schedule 06.05.2009
comment
Я думаю, вы имели в виду m::f (n-1) (m+1) вместо m::list (n-1) (m+1) - person Chris Conway; 06.05.2009
comment
Может быть, это только я, но я съеживаюсь всякий раз, когда вижу функцию без хвостовой рекурсии, которую можно легко переписать так, чтобы она была хвостовой рекурсией. - person ephemient; 06.05.2009
comment
Я просто хотел показать наиболее очевидное решение, основанное на том, что уже было у Барри. Полагаю, я должен был отметить, что решение с хвостовой рекурсией возможно, но Крис Конвей уже сделал это. - person TrayMan; 07.05.2009
comment
Это всего лишь крошечное передергивание ;) Если бы это не было в образовательных целях, я бы предложил fun list n = List.tabulate (n, fn x => x + 1) как лучшую реализацию. На самом деле, может быть, я все еще сделаю это... - person ephemient; 07.05.2009

arrow_upward
3
arrow_downward

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

fun list n =
  let
    fun aux i acc = 
      if i > 0
      then aux (i-1) (i::acc)
      else acc
  in
    aux n nil
  end;
person Chris Conway    schedule 06.05.2009
comment
Не будет ли это обратным результатом? - person leppie; 06.05.2009
comment
Это почти идентично моему первому ответу, хотя я перевернул порядок аргументов помощника, чтобы частичная оценка работала хорошо. Если бы я понял это раньше, я бы, наверное, не написал свой :) - person ephemient; 06.05.2009

arrow_upward
2
arrow_downward

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

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

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

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

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

Это представление быстро приводит к ясному и лаконичному коду ML (проверено):

fun range n m = if n > m then [] else n :: range (n+1) m
fun list n = range 1 n
person Norman Ramsey    schedule 07.05.2009
comment
Именно туда я и шел с этой проблемой. Я подумал, что если я смогу заставить его работать для 1..n, то в конечном итоге я смогу заставить его работать и для m..n. Как бы то ни было, с помощью ephemient я создал функцию, которая создает список из первого, второго и последнего элемента, подобно тому, как Haskell позволяет пользователям создавать списки. - person Barry Brown; 07.05.2009
comment
Вы даже можете воспользоваться частичной оценкой и написать val list = range 1 :) - person ephemient; 07.05.2009
comment
@ephemient: мило. (Но я думаю, вы имеете в виду частичное применение.) - person Norman Ramsey; 08.05.2009

arrow_upward

arrow_downward

person    schedule
comment
Используя разворачивание вправо SRFI-1: (define (iota n) (развернуть вправо ноль? 1- 1- n)) (где 1- определяется обычным способом: (define (1- x) (- x 1)) ) - person Chris Jester-Young; 07.05.2009
comment
Построить в обратном порядке, затем в обратном порядке: (определить (iota n) (обратить (развернуть ноль? 1- 1- n))) - person Chris Jester-Young; 07.05.2009