Funcional: construir uma lista de inteiros 1..n

Question

Este não é lição de casa. Estou aprendendo ML padrão em meu próprio. Eu sei um pouco de Scheme, também, para que esta questão deve ser responsável em qualquer idioma.

Minha tarefa auto-imposta é escrever uma função que constrói uma lista de números inteiros de 1 a n. Por exemplo, a lista (7) deve retornar [1,2,3,4,5,6,7]. Uma solução de (n) ó seria ideal.

É fácil de construir uma lista em sentido inverso (i.e., [N, N-1, .., 1]) em vez linear:

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

A minha tentativa de construir uma lista daqui para frente é O (n ^ 2) porque a operação de acréscimo é linear.

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

A minha próxima tentativa foi a de construir uma lista do fim para a frente (direita para a esquerda), iniciando com o nulo, anexando n para a frente, e recursão para trás para 1. Mas não deu certo em tudo.

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

Algo me faz pensar que eu preciso de uma função auxiliar que constrói listas terminadas pela ONU para ser usado na recursão, mas estou perplexo.

Answer 1

Usando o Base Biblioteca ,

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

Com um acumulador simples,

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

Isso cria uma lista a partir da extremidade da cauda. Se você acha das reduções,

   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]

Como alternativa,

Algo me faz pensar que eu preciso de uma função auxiliar que constrói listas terminadas pela ONU para ser usado na recursão, mas estou perplexo.

Uma representação de uma lista unterminated é uma função que recebe uma lista e retorna uma lista:. Por exemplo, para representar 10::_, você poderia usar 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

Mais uma vez, se você acha das reduções,

   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]

Neste caso, o algoritmo pode ser estruturado de tal forma que um simples sufixos estrutura de dados para o acumulador, mas usando uma continuação como um acumulador é uma técnica muito poderosa e útil que não deve ser menosprezada.

Answer 2

Uma abordagem clássica é construí-lo em ordem inversa, em seguida, revertê-la. Isso é duas vezes O (n), que é, naturalmente, assim como O (n).

Answer 3

Aqui está uma solução:

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

Aqui está uma versão com uma função auxiliar e um acumulador de tail-permitindo-recursão:

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

Com problemas lista como estes, muitas vezes é mais fácil de resolver um problema mais geral.

Como faço para construir uma lista contendo os inteiros i tal que n <= i <= m , em ordem?

A solução tem um caso de base e um passo de indução:

• Se n> m , a lista está vazia.

• Se n <= m , a solução é a gravação n seguida pela solução para o problema n + 1 <= i <= m .

A visão leva rapidamente à clara, concisa código ML (testado):

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