Fonctionnel: construit une liste d'entiers 1..n

Question

Ce n’est pas un devoir. J'apprends le Standard ML seul. Je connais un peu Scheme aussi, alors cette question devrait être posée dans l'une ou l'autre langue.

Mon devoir personnel est d'écrire une fonction qui construit une liste d'entiers de 1 à n. Par exemple, list (7) devrait renvoyer [1,2,3,4,5,6,7]. Une solution O (n) serait idéale.

Il est facile de construire une liste à l'envers (c'est-à-dire, [n, n-1, .., 1]) en temps linéaire:

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

Ma tentative de construction d'une liste à l'avenir est O (n ^ 2) car l'opération d'ajout est linéaire.

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

Ma tentative suivante consistait à construire une liste de bout en bout (de droite à gauche) en commençant par le nil, en attachant n au début et en revenant à 1. Cependant, cela ne fonctionnait pas du tout.

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

Quelque chose me fait penser que j'ai besoin d'une fonction d'assistance qui crée des listes non terminées à utiliser dans la récursion, mais je suis perplexe.

Answer 1

Utilisation de la bibliothèque de base ,

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

Avec un simple accumulateur,

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

Ceci construit une liste à partir de la fin. Si vous pensez aux réductions,

   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]

Sinon,

  

Quelque chose me fait penser que j'ai besoin d'une fonction d'assistance qui crée des listes non terminées à utiliser dans la récursion, mais je suis perplexe.

Une représentation d'une liste non terminée est une fonction qui prend une liste et renvoie une liste: par exemple, pour représenter 10::_, vous pouvez utiliser 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

Encore une fois, si vous songez aux réductions,

   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]

Dans ce cas, l’algorithme peut être structuré de telle sorte qu’une structure de données ordinaire suffise pour l’accumulateur, mais l’utilisation d’une continuation comme accumulateur est une technique très puissante et utile qu’il ne faut pas négliger.

Answer 2

Une approche classique consiste à le construire dans l’ordre inverse, puis à l’inverser. C'est deux fois O (n), ce qui est bien sûr exactement comme O (n).

Answer 3

Voici une solution:

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

Voici une version utilisant une fonction d'assistance et un accumulateur permettant la récursion de la queue:

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

Avec de tels problèmes de liste, il est souvent plus facile de résoudre un problème plus général.

  

Comment créer une liste contenant les entiers i tels que n < = i < = m , dans l'ordre?

La solution a un cas de base et une étape d'induction:

• Si n > m , la liste est vide.

• Si n < = m , la solution consiste à écrire n suivi de la solution au problème n + 1 < !> lt; = i < = m .

Cette vue conduit rapidement à un code ML clair et concis (testé):

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