Funcional: construya una lista de enteros 1..n

Question

Esto no es tarea. Estoy aprendiendo Standard ML por mi cuenta. También conozco un poco de Scheme, por lo que esta pregunta debería responder en cualquier idioma.

Mi tarea autoimpuesta es escribir una función que construya una lista de enteros de 1 a n. Por ejemplo, la lista (7) debería devolver [1,2,3,4,5,6,7]. Una solución O (n) sería ideal.

Es fácil construir una lista a la inversa (es decir, [n, n-1, .., 1]) en tiempo lineal:

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

Mi intento de construir una lista en el futuro es O (n ^ 2) porque la operación de agregar es lineal.

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

Mi siguiente intento fue construir una lista desde el final hacia el frente (de derecha a izquierda) comenzando con el cero, adjuntando n al frente y recurriendo hacia atrás a 1. Pero no funcionó en absoluto.

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

Algo me hace pensar que necesito una función auxiliar que construya listas sin terminar para usar en la recursión, pero estoy perplejo.

Answer 1

Uso de la Biblioteca de bases ,

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

Con un acumulador simple,

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

Esto crea una lista que comienza desde el final de la cola. Si piensa en las reducciones,

   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]

Alternativamente,

  

Algo me hace pensar que necesito una función auxiliar que construya listas sin terminar para usar en la recursión, pero estoy perplejo.

Una representación de una lista sin terminar es una función que toma una lista y devuelve una lista: por ejemplo, para representar 10::_, podría 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

Una vez más, si piensa en las reducciones,

   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]

En este caso, el algoritmo puede estructurarse de manera tal que una estructura de datos ordinaria sea suficiente para el acumulador, pero usar una continuación como acumulador es una técnica muy poderosa y útil que no debe pasarse por alto.

Answer 2

Un enfoque clásico es construirlo en orden inverso y luego invertirlo. Eso es dos veces O (n), que por supuesto es igual que O (n).

Answer 3

Aquí hay una solución:

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

Aquí hay una versión que utiliza una función auxiliar y un acumulador que permite la recursión de cola:

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

Con problemas de lista como estos, a menudo es más fácil resolver un problema más general.

  

¿Cómo construyo una lista que contenga los enteros i de modo que n < = i < = m , en orden?

La solución tiene un caso base y un paso de inducción:

• Si n > m , la lista está vacía.

• Si n < = m , la solución es escribir n seguido de la solución al problema n + 1 < !> lt; = i < = m .

Esta vista lleva rápidamente a un código ML claro y conciso (probado):

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