Funktional: bauen eine Liste von ganzen Zahlen 1..n

Question

Das ist keine Hausaufgaben. Ich lerne Standard ML auf eigene Faust. Ich weiß, ein bisschen Schema, zu, so dass diese Frage sollte in beiden Sprachen verantwortlich sein.

Meine selbst auferlegte Aufgabe ist es, eine Funktion zu schreiben, die eine Liste von ganzen Zahlen von 1 bis n-Konstrukte. Zum Beispiel sollte die Liste (7) return [1,2,3,4,5,6,7]. Eine O (n) Lösung wäre ideal.

Es ist einfach eine Liste in umgekehrter Richtung (das heißt [n, n-1, .., 1]) in linearer Zeit zu konstruieren:

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

Mein Versuch, eine Liste für die Zukunft zu konstruieren, ist O (n ^ 2), da der Anfügevorgang linear ist.

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

Mein nächster Versuch war eine Liste von dem Ende nach vorne (rechts nach links) durch, beginnend mit dem Null zu bauen, an den vorderen Befestigung n und Rekursion rückwärts zu 1. Aber es hat nicht funktioniert.

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

Etwas macht mich glaube, ich brauche eine Hilfsfunktion, die un-terminierten Listen baut sich in der Rekursion verwendet werden, aber ich bin ratlos.

Answer 1

Mit der Basis-Bibliothek ,

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

Mit einem einfachen Akkumulator,

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

Dies baut eine Liste aus dem Schwanzende beginnen. Wenn Sie die Kürzungen denken,

   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]

Alternativ

  

Etwas macht mich glaube, ich brauche eine Hilfsfunktion, die un-terminierten Listen baut sich in der Rekursion verwendet werden, aber ich bin ratlos.

Eine Darstellung einer ungekündigten Liste ist eine Funktion, die eine Liste nimmt und gibt eine Liste: zum Beispiel darzustellen 10::_, Sie fn x => 10::x verwenden könnten

.

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

Noch einmal, wenn Sie von den Kürzungen denken,

   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 diesem Fall kann der Algorithmus so aufgebaut sein, dass eine ordentliche Datenstruktur für den Akkumulator genügt, sondern eine Fortsetzung als Speicher verwendet, ist eine sehr leistungsfähige und nützliche Technik, die nicht übersehen werden soll.

Answer 2

Ein klassischer Ansatz ist es in umgekehrter Reihenfolge zu bauen, dann umkehren. Das ist zwei mal O (n), was natürlich nur als O (n).

Answer 3

Hier ist eine Lösung:

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

Hier ist eine Version eine Hilfsfunktion und einen Schwanz-Rekursion ermöglich Akkumulator mit:

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

Mit Liste Problemen wie diese, ist es oft einfacher, ein allgemeineres Problem zu lösen.

  

Wie erstelle ich eine Liste mit den ganzen Zahlen i , so dass n <= i <= m , um?

Die Lösung hat einen Basisfall und einen Induktionsschritt:

• Wenn n> m , die Liste leer ist.

• Wenn n <= m , die Lösung ist n durch die Lösung anschließend zu schreiben, um das Problem n + 1 <= i <= m .

Diese Ansicht führt schnell zu klaren, prägnanten ML-Code (getestet):

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