crosswords for real

Archiv Algorithmik II
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

crosswords for real
Mir ist leider zu Ohren gekommen das es wohl nur eine hässliche Musterlösung zur crosswords-Aufgabe (5-4) gab und da hab ich mich der Sache mal angenommen:

(define (crosswords . args)
    (foldr cross '(())
           (map (lambda (x)
                       (if (pair? x) x
                          (list x))) args)))

(define (cross l1 l2)
    (foldr append '()
           (map
            (lambda (x)
              (map (lambda (y) (cons x y))
                   l2))
            l1)))

Foldr, falls nicht anderweitig bekannt:

(define (foldr f b l)
    (if (null? l) b
        (f (car l) (foldr f b (cdr l)))))

Vllt noch zur Erinnerung(?):
| sei cons als binärer Infixoperator (natürlich rechtsassoziativ), + die folding-Operation als binärer Infixoperator, dann gilt:
foldr + B a|b|c|d|'() = a+(b+(c+(d+B)))
(ja, das r in foldr steht für rechtsassoziativ ;P)

Wenn man sich die rekursive Definition des kartesischen Produktes vor Augen führt, wirds wahrscheinlich leichter verständlich. Cross ist hier quasi das binäre kartesische Produkt…

Ach was solls, ich mach noch das Beispiel:
(crosswords '(peter ute) 'isst 'gerne '(rueben bohnen))
=> '(peter ute) x [ '(isst) x [ '(gerne) x [ '(rueben bohnen) x '(()) ] ] ] (x=cross als binärer Infixoperator)
=> '(peter ute) x [ '(isst) x [ '(gerne) x '((rueben) (bohnen)) ] ]
=> '(peter ute) x [ '(isst) x ((gerne rueben) (gerne bohnen)) ]
=> '(peter ute) x '((isst gerne rueben) (isst gerne bohnen))
=> '((peter isst gerne rueben) (peter isst gerne bohnen) (ute isst gerne rueben) (ute isst gerne bohnen))

3

Coole Sache,besten dank.

4

Irgendwie wesentlich klarere als das in der Übung…