Funzionale: costruisci un elenco di numeri interi 1..n

Question

Non si tratta di compiti a casa. Sto imparando Standard ML da solo. Conosco anche un po 'di Schema, quindi questa domanda dovrebbe essere rispondente in entrambe le lingue.

Il mio compito autoimposto è scrivere una funzione che costruisce un elenco di numeri interi da 1 a n. Ad esempio, l'elenco (7) dovrebbe restituire [1,2,3,4,5,6,7]. Una soluzione O (n) sarebbe l'ideale.

È facile costruire un elenco al contrario (ovvero, [n, n-1, .., 1]) in tempo lineare:

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

Il mio tentativo di costruire un elenco in futuro è O (n ^ 2) perché l'operazione di aggiunta è lineare.

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

Il mio prossimo tentativo è stato quello di creare un elenco dall'estremità in avanti (da destra a sinistra) iniziando con lo zero, attaccando n in avanti e ricorrendo all'indietro su 1. Ma non ha funzionato affatto.

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

Qualcosa mi fa pensare che ho bisogno di una funzione di supporto che costruisce elenchi non terminati da utilizzare nella ricorsione, ma sono sconcertato.

Answer 1

Utilizzo della Libreria di base ,

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

Con un semplice accumulatore,

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

Questo crea un elenco a partire dalla fine della coda. Se pensi alle riduzioni,

   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]

In alternativa,

  

Qualcosa mi fa pensare che ho bisogno di una funzione di supporto che costruisce elenchi non terminati da utilizzare nella ricorsione, ma sono sconcertato.

Una rappresentazione di un elenco non terminato è una funzione che accetta un elenco e restituisce un elenco: ad esempio, per rappresentare 10::_, è possibile utilizzare 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

Ancora una volta, se si pensa alle riduzioni,

   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]

In questo caso, l'algoritmo può essere strutturato in modo tale che una struttura di dati ordinaria sia sufficiente per l'accumulatore, ma l'utilizzo di una continuazione come accumulatore è una tecnica molto potente e utile da non trascurare.

Answer 2

Un approccio classico è costruirlo in ordine inverso, quindi invertirlo. Questo è due volte O (n), che è ovviamente proprio come O (n).

Answer 3

Ecco una soluzione:

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

Ecco una versione che utilizza una funzione di supporto e un accumulatore che abilita la ricorsione della coda:

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 problemi di elenco come questi, è spesso più facile risolvere un problema più generale.

  

Come posso creare un elenco contenente gli interi i in modo tale che n < = i < = m , in ordine?

La soluzione ha un caso base e una fase di introduzione:

• Se n > m , l'elenco è vuoto.

• Se n < = m , la soluzione è scrivere n seguito dalla soluzione al problema n + 1 < !> lt; = i < = m .

Questa visualizzazione porta rapidamente a un codice ML chiaro e conciso (testato):

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