Scheme: Rekursiv - aber wie?

Begonnen von ingmar, Freitag, 24. November 2017, 19:32

« vorheriges - nächstes »

ingmar

Hallo,


der folgende Code kompiliert einwandfrei, tut aber nicht, was ich erwarte. Aufbauend auf der Antwort zu meiner letzten Frage, möchte ich nun einen rekursiven Aufruf der Funktion test erreichen, so dass, beginnend bei 1, alle Zahlen bis einschließlich der als Argument Übergebenen ausgegeben werden.

Was mache ich falsch? (Ein \void \displayScheme hilft hier leider auch nicht...)

\version "2.19.64"

test = #(define-scheme-function (i) (integer?)
(if (> i 1)
(begin
(test (- i 1))
#{ \markup #(number->string i ) #})))

\test 4


Danke für die Hilfe!
--ingmar

harm6

#1
Hallo Ingmar,

(1) Ich würde define-scheme-function nicht verwenden. Es gibt zu viele Fallstricke und Überraschungen. Sondern erst mal natives scheme benutzen.
(2) Deine Funktion krankt u.a. daran, daß die eigentlich auszugebenden Werte nicht akkumuliert werden.
(3) Mach Dir klar was tail-rekursiv bedeutet.
-> https://de.wikipedia.org/wiki/Scheme Scroll runter zu "Schleifen"

Hier drei native scheme-Definitionen, die erst mal nur die Liste der Zahlen ausgeben. Gefolgt von einem Aufruf als markup, der dann allerdings noch Sorge tragen muß, daß strings verwendet werden. Die string-Conversion hätte man auch gleich mit machen können, hab' ich aber der Klarheit wegen unterlassen.

Die erste ist nicht tail-rekursiv.
Die zweite sehr wohl und benutzt eine zusätzliche Variable um die Ausgabewerte zu sammeln.
Die dritte benutzt die zweite, um die zusätzliche Variable zu eliminieren, syntactic sugar :D

1. (nicht tail-rekursiv)

#(define (foo n)
  (if (> n 1)
      (cons n (foo (1- n)))
      '(1)))
 
#(write (foo 4))

\markup #(map number->string (foo 4))


2. (tail-rekursiv)

#(define (bar l i)
  (if (< i 1)
      (reverse l)
      (bar (cons i l) (1- i) )))
     
#(write (bar '() 4))

\markup #(map number->string (bar '() 4))


3. (syntactic sugar)

#(define (buzz n)
  (bar '() n))
 
#(write (buzz 4))

\markup #(map number->string (buzz 4))


Um den Unterschied von 1. (nicht tail-rekursiv) und 2. (tail-rekursiv) besser zu sehen, öffne einen guile-prompt.
Also im terminal guile oder gehe in die scheme-sandbox (lilypond scheme-sandbox). Dann:

Zitat von: terminal
guile> (use-modules (ice-9 debug))
guile> (define (foo n)
  (if (> n 1)
      (cons n (foo (1- n)))
      '(1)))
guile> (trace foo)
(foo)
guile> (foo 4)
[foo 4]
|  [foo 3]
|  |  [foo 2]
|  |  |  [foo 1]
|  |  |  (1)
|  |  (2 1)
|  (3 2 1)
(4 3 2 1)
(4 3 2 1)
guile>

im Unterschied zu:
Zitat von: terminal
guile> (use-modules (ice-9 debug))
guile> (define (bar l i)
  (if (< i 1)
      (reverse l)
      (bar (cons i l) (1- i) )))
guile> (trace bar)
(bar)
guile> (bar '() 4)
[bar () 4]
[bar (4) 3]
[bar (3 4) 2]
[bar (2 3 4) 1]
[bar (1 2 3 4) 0]
(4 3 2 1)
(4 3 2 1)


Falls Du wirklich und unbedingt die scheme-function haben willst:

Nicht tail-rekursiv:

test = #(define-scheme-function (i) (integer?)
(if (> i 1)
(cons #{ \markup \with-color #red #(number->string i) #} (test (- i 1)))
(list #{ \markup \with-color #red #(number->string i) #})))

\markup \test #4


Tail-rekursiv:

testII = #(define-scheme-function (acc-l i) (list? integer?)
(if (>= i 1)
(testII
  (cons #{ \markup \with-color #cyan #(number->string i) #} acc-l)
  (1- i))
(reverse acc-l)))

\markup \testII #'() #4


HTH,
  Harm

P.S. Die einfachste Methode für bloße Zahlem wäre natürlich iota zu verwenden, das führt hier zu:

\markup #(map number->string (reverse (iota 4 1 1)))


ingmar

#2
Hallo Harm,

danke für die Antwort! Einiges wird klarer, anderes aber noch nicht...

Ich hab nun aber mal etwas anderes versucht.

\version "2.19.64"

numbers = #( list "1" "2" "3" "4" "5" "6" "7" "8" "9")

printnumbers = #(define (mylist mystring) (list? string?)
(let ((this-number (car mylist))
       (mylist = (cdr mylist)))
#{ \markup $this-number #}
(if (not (empty? mylist))
(printnumbers mylist))))

\printnumbers \numbers

Aufruf der Funktion mit einer vordefinierte Liste, von der ich anschließend den ersten Eintrag nehme und per \markup anzeige. Dann ruft sich die Funktion mit dem Rest der Liste selbst wieder auf. Kompiliert, funktioniert. Oder fühlt sich zumindest so an...

Denn wenn ich die Zeile auskommentiere, die nach meiner Meinung den Ausdruck vornimmt - also schreibe

;   #{ \markup $this-number #}

.. dann wird die Liste erschreckenderweise trotzdem ausgedruckt!! Was passiert da? Wahrscheinlich eine entsetzliche Dummheit, für die ich mich jetzt schämen müsste...?


Danke, Gruß,
--ingmar

EDIT: Das zweite Argument wäre für ein Minimalbeispiel natürlich nicht nötig. Ich habe dringelassen für meine nächste Frage...

harm6

Hallo Ingmar,

ich habe ein paar Tage drüber nachgedacht, wie ich antworten könnte...
Eigentlich weiß ich es immer noch nicht, denn Dein Versuch ist absolut verkorkst.

Vielleicht besser Du schreibst was Du erreichen willst.


Gruß,
  Harm

ingmar

Tja!

Zuerst mal danke für deine Antwort. Und sorry, wenn ich dir wirklich mit mehreren Tagen Nachdenken einiges an Zeit gestohlen habe!

Dieses letzte Beispiel ist wohl verwirrend, wenn man es in Relation zu meinen vorhergehenden Postings sehen will, mit denen es nicht soviel zu tun hat. Es gibt auch (erstmal) kein unmittelbares musikalisches Ziel, das ich hier erreichen möchte. Ich möchte einer Scheme-Funktion eine Liste von Strings übergeben und diese dort einzeln verarbeiten lassen, bis die Liste leer ist. Da ich vorher nicht weiß, wie lang meine Liste sein wird, hab ich verstanden, dass ich Rekursion dafür brauche.

Bei jedem Durchgang möchte ich damit wieder LilyPond-Code erzeugen. Ich hatte bisher die Vorstellung, dass in Guile alles in #{ ... #} Eingeklammerte unmittelbar als LilyPond-Code verstanden und entsprechend interpretiert (also ins Ergebnisfile geschrieben) wird. Offenbar ist dieses Bild also falsch! Muss ich den entstehenden LilyPond-Code aggregieren und als Ergebnis meiner Funktion zurückgeben? Wie mach ich das am einfachsten? Ich hatte beispielhaft \markup verwendet, weil ich das für besonders einfach hielt - vielleicht auch ein Irrtum.

Mein Ziel ist im Moment nur, das Zusammenspiel zwischen Scheme und LilyPond besser zu verstehen. Immer, wenn ich Werte in die eine oder andere Richtung übergeben möchte, stolpere ich und gebe die Sache irgendwann auf. Besonders, wenn es mehrere Werte sind. Das hat auch mit den - sicher richtigen, aber für mich of wenig intuitiven - Fehlermeldungen zu tun. Die Scheme-Sandbox  auf dem Mac zum Laufen zu kriegen, ist mir leider immernoch nicht gelungen.

Tja - kann nicht mal jemand einen VHS-Kurs zum Thema "LilyPond und Scheme" anbieten? Ich käme bestimmt, wenn irgend möglich.. : - (

Gruß,
--ingmar

harm6

ZitatZuerst mal danke für deine Antwort. Und sorry, wenn ich dir wirklich mit mehreren Tagen Nachdenken einiges an Zeit gestohlen habe!

Zeit hast Du mir keine gestohlen ;)
Aber ich wußte nicht wie antworten...

Zitat
Ich möchte einer Scheme-Funktion eine Liste von Strings übergeben und diese dort einzeln verarbeiten lassen, bis die Liste leer ist. Da ich vorher nicht weiß, wie lang meine Liste sein wird, hab ich verstanden, dass ich Rekursion dafür brauche.

Du brauchst nicht zwangsläufig eine selbst definierte Rekursion. Oft reicht `map', welches eine procedure auf eine Liste so anwendet, daß die procedure auf jedes Elemente der Liste angewendet wird. `map' returniert dann die "Ergebnisliste".
`map' ist übrigens selbst rekursiv definiert...
Darüberhinaus gibt es noch Verwandte und Abkömmlinge wie `filter', `remove', etc

Ein Beispiel:

numbers = #(list "1" "2" "3" "4" "5" "6" "7" "8" "9")
\markuplist #(map (lambda (s) #{ \markup \with-color #red $s #}) numbers)


Zitat
Ich hatte bisher die Vorstellung, dass in Guile alles in #{ ... #} Eingeklammerte unmittelbar als LilyPond-Code verstanden und entsprechend interpretiert (also ins Ergebnisfile geschrieben) wird. Offenbar ist dieses Bild also falsch! Muss ich den entstehenden LilyPond-Code aggregieren und als Ergebnis meiner Funktion zurückgeben?

Wenn irgendwo #{ ... #} in guile-code steht, so bedeutet das lediglich, daß guile in LilyPond versteht was da steht.
Ganz generell wird in guile-Definitionen immer der letzte bearbeitete Ausdruck ausgegeben.

Beispiel:

#(define (xy)
  #{ c'4 #}
  #{ d'4 #})

#(define xyz
(lambda ()
  #{ c'4 #}
  #{ d'4 #}))
 
#(display-lily-music (xy))
#(display-lily-music (xyz))

{ $(xy) $(xyz) }

Hier sind zwei proceduren definiert, im Prinzip identisch aber mit unterschiedlicher Syntax. Beide proceduren erwarten kein Argument und geben den letzten Ausdruck aus. c'4 fehlt also!

Du mußt selbst dafür Sorge tragen die Ergebnisse zu akkumulieren. Wie man das macht hängt vom Ziel ab.

Hier ein Beispiel:

#(define (zz)
  (make-sequential-music
    (list #{ c'4 #} #{ d'4 #})))
 
$(zz)


HTH,
  Harm

ingmar

#6
Vielen Dank für die ausführliche Antwort, die mir ein ganzes Stück weitergeholfen hat!

Aber trotzdem gelingt es mir immer noch nicht, Musikfetzen nach und nach an eine leere Liste anzuhängen, um das Resultat zuletzt als Musik auszugeben. Ich hab hier zwei Versuche:
\version "2.19.64"

A = #(define-music-function () ()
(let (( result (list '() )))
(append result #{ a'2 #})
(append result #{ b'4 #})
(append result #{ c''2 #})
(display result)
(make-sequential-music (result))))

B = #(define-music-function () ()
(let (( result (list '() )))
(cons #{ c''2 #} result)
(cons #{ b'2 #} result)
(cons #{ a'2 #} result)
(display result)
(make-sequential-music (reverse result))))

%\A
%\B


Das kompiliert einwandfrei. Aber wenn ich die zwei letzten Zeilen auskommentiere, meine Funktionen also aufrufe, sehe ich Fehler - jedoch nicht in meinem eigenen Code. Andererseits, die beiden Zeilen (display result) zeigen deutlich, dass die Listen in beiden Fällen offenbar leer bleiben; das Anhängen funktioniert also nicht. Was mach ich diesmal falsch!?

Danke, Gruß,
--ingmar

EDIT: Titel

harm6

Zitat
wenn ich [...] meine Funktionen also aufrufe, sehe ich Fehler - jedoch nicht in meinem eigenen Code.

Nun, es sind einige Fehler in Deinem code. Bloß weil das kompilieren der Definition keine Fehlermeldung gibt, so heißt das noch nicht, daß sie richtig oder sinnvoll ist ;)

Ein Beispiel:

#(define (xy) (/ 1 0))


Hier ist die Division von 1 durch null als procedure mit dem Namen `xy' definiert. Diese procedure erwartet kein Argument.
Setz die Definition in ein file und es wird fehlerfrei kompilieren. Falls Du die Definition allerdings ausführst:
#(xy)
fliegt sie Dir natürlich um die Ohren.

Nun zu Einzelheiten:
(let (( result (list '() )))
definiert `result' als eine Liste, die eine leere Liste enthält. Da seh ich keinen Sinn. Also entweder (list) oder '().
Beides ist oft äquivalent.

(make-sequential-music (result))
Warum `result' in Klammern? Das bedeutet `result' wird als Operator für die ansonsten leere Liste gesehen. `result' ist aber kein Operator sondern selbst eine Liste. Kann nicht klappen...

(make-sequential-music result)
funktioniert allerdings auch nicht, da es sich um eine Liste handelt, die eine leere Liste enthält. Irgendwo erwartet `make-sequential-music' schon music, bekommt stattdessen aber etwas anderes.

Bei einer einfachen leeren Liste
(make-sequential-music '())
gibts nur noch eine Warnung:
warning: no music found in score

(append result #{ a'2 #})
Mit dieser Zeile bildest Du eine Liste mit den Elementen `result' und #{ a'2 #}. Aber sie modifiziert nicht `result'. De facto wird das Ergebnis also weggeworfen.
Die Folgezeilen ebenso, also bleibt `result' unverändert.

Hier eine mit Naserümpfen betrachtete Methode. (Sie hat tatsächlich auch einige Fallstricke auf die ich hier nicht näher eingehe. Ich poste sie trotzdem, da sie sehr leicht nachvollziehbar ist.):

A = #(define-music-function () ()
(let ((result (list)))
  (set! result (cons #{ a'2 #} result))
  (set! result (cons #{ b'4 #} result))
  (set! result (cons #{ c''2 #} result))
  (display-scheme-music result)
  (make-sequential-music result)))

\A


Jede Zeile mit set! setzt (destruktiv) einen neuen Wert für `result'. Somit werden die Werte in `result' akkumuliert.

Etwas besser:

A = #(define-music-function () ()
(let* ((result (list))
       (new-result
        (cons #{ a'2 #}
          (cons #{ b'4 #}
            (cons #{ c''2 #} result)))))
  (display-scheme-music new-result)
  (make-sequential-music new-result)))

\A


Soweit erstmal...

Gruß,
  Harm



harm6

Apropos Rekursion...

Hier ein Problem an dem ich jetzt Stunden gesessen habe:
In einer geschachtelten Liste kommen Sublisten vor die mit einem Symbol beginnen. Diese können allerdings keine weitere Sublisten mit solch einem Symbol enthalten.

Gebe eine Liste aus die nur die Einträge direkt rechts vom Symbol enthält. Rechts von zwei verschiedenen positionierten gleichen Symbolen können identische Einträge vorkommen.

Das Symbol: 'pl
Die Liste:
    '(a
      b
      (foo (pl (1 2 3) bar rr tt) x y)
      (f g (pl (1 2 3) wtf))
      ((((pl (2 3 4)))))
      w
      z
      (pl (x y z) buzz))
Das gewünschte Ergebnis: '((1 2 3) (1 2 3) (2 3 4) (x y z))

Ich habe jetzt einen Code dafür, aber ich bin nicht so recht zufrieden damit. Wenn also jemand eine eigene Lösung posten kann, würde ich die Codes sehr gern vergleichen. Dann poste ich natürlich auch meinen. :)

Gruß,
  Harm

Malte

\version "2.19.80"

thesymbol = #'pl

thelist =
#'(a
   b
   (foo (pl (1 2 3) bar rr tt) x y)
   (f g (pl (1 2 3) wtf))
   ((((pl (2 3 4)))))
   w
   z
   (pl (x y z) buzz))

#(define ((foo ts) tl)
   (if (pair? tl)
       (if (eq? ts (car tl))
           (list (cadr tl))
           (concatenate (map (foo ts) tl)))
       '()))

#(display ((foo thesymbol) thelist))

Wenn man den Aufruf als(foo thesymbol thelist)haben will (also ein Klammernpaar weniger), muß man sich in dem map mit nem λ-Ausdruck behelfen, oder#(define (baz a b) ((foo a) b))
#(display (baz thesymbol thelist))

Oder gibts da noch ne einfachere Lösung?

harm6

#10
Hallo Malte,

sorry für die späte Antwort...

Dein Code ist erstmal ganz hervorragend, erfüllt meine Bedingungen (soweit ich sie formuliert habe) und die Anwendung auf die Beispielliste ist wie gewollt.

Jedoch ein paar Bemerkungen
(1) Der Code wirft einen error aus, falls ein pair wie '(1 . 2) in der Liste enthalten ist.
Ich weiß, es war kein pair in der Beipielliste :(
Läßt sich mit der Prüfung auf list? beheben
(2) (concatenate (map ...))
kann man hier zu (append-map ...) vereinfachen.
(3) Einen λ-Ausdruck empfinde ich nicht als Behelf sondern Eleganz ;)

Führt zu:
Zitat
#(define (fooII ts tl)
   (if (list? tl)
       (if (eq? ts (car tl))
           (list (cadr tl))
           (append-map (lambda (l) (fooII ts l)) tl))
       '()))

Im weiteren Verlauf bin ich darauf gestoßen, daß ich manchmal anders auswählen sowie selektieren möchte.
Auswählen heißt, daß ich manchmal nicht das direkt auf das symbol folgende haben möchte, sondern einen der anderen folgenden Einträge.
Also nicht cadr sondern z.B. den ersten Wert der folgenden Liste, d.h. caadr.
Selektieren meint, wenn ich in einer sublist zwei subsublisten mit auszuwählenden gleichen Einträgen habe, sollen beide genommen werden oder eben nur einer?

Insoweit habe ich Deinen Code erweitert, indem ich ihm ein Argument für die Auswahl-procedure und ein optionales Argument für die Selektierungs-procedure mitgebe.
Auch finde ich geschachtelte if-expressions sehr schnell unübersichtlich, habe ich auf (cond ...) geändert.

Führt zu:

#(define lstI
  '((pl (1 2 3) foo)
    (foo (pl (1 2 3) bar) (pl (1 2 3) buzz))))
   
#(define* (fooIII ts proc tl #:optional (select-proc identity))
   (cond ((and (list? tl) (eq? ts (car tl)))
           (list (proc tl)))
         ((list? tl)
           (append-map
             (lambda (l) (select-proc (fooIII ts proc l select-proc )))
             tl))
         (else '())))

#(format #t "\nRESULT-IIIa:\n~y" (fooIII 'pl  caadr lstI))
#(format #t "\nRESULT-IIIb:\n~y" (fooIII 'pl  caadr lstI delete-adjacent-duplicates))


Wobei `delete-adjacent-duplicates' leicht verändert aus dem guile-manual stammt.


#(define (delete-adjacent-duplicates lst)
  (if (pair? lst)
      (fold-right
        (lambda (elem ret)
          (if (equal? elem (first ret))
              ret
              (cons elem ret)))
        (list (last lst))
        lst)
      lst))


Nochmals vielen Dank!

Gruß,
  Harm

Wenn ich ein bißchen mehr Zeit habe schreib ich auch über "Wozu das Ganze?" :)


harm6

Nachtrag, ich wollte doch auch meinen Code gepostet haben.

#(define (get-next-to-sym ls symbol proc)
  (define (helper l rl sym proc)
    (if (list? l)
        (append-map
          (lambda (x)
            (delete-adjacent-duplicates
              (helper
                x
                (remove
                  null?
                  (if (eq? sym (car l))
                      (cons (proc l) rl)
                      rl))
                sym
                proc)))
          l)
        rl))
  (helper ls '() symbol proc))

Aber lange nicht so elegant wie das Endergebnis aus meinem vorigen post.

Gruß,
  Harm