En Scheme, La función "mapa" suele ser útil para calcular una lista basada en otra.
De hecho, en el esquema, mapa tiene una función de "n-argumento" y "n" listas y llama a la función para cada elemento correspondiente de cada lista:
> (map * '(3 4 5) '(1 2 3))
(3 8 15)
Pero una adición muy natural esto sería una función de "mapa cartesiano", que llamaría a su función "n-argumento" con todas las diferentes formas de elegir un elemento de cada lista. Me tomó un tiempo para averiguar exactamente cómo hacerlo, pero aquí van:
; curry takes:
; * a p-argument function AND
; * n actual arguments,
; and returns a function requiring only (p-n) arguments
; where the first "n" arguments are already bound. A simple
; example
; (define add1 (curry + 1))
; (add1 3)
; => 4
; Many other languages implicitly "curry" whenever you call
; a function with not enough arguments.
(define curry
(lambda (f . c) (lambda x (apply f (append c x)))))
; take a list of tuples and an element, return another list
; with that element stitched on to each of the tuples:
; e.g.
; > (stitch '(1 2 3) 4)
; ((4 . 1) (4 . 2) (4 . 3))
(define stitch
(lambda (tuples element)
(map (curry cons element) tuples)))
; Flatten takes a list of lists and produces a single list
; e.g.
; > (flatten '((1 2) (3 4)))
; (1 2 3 4)
(define flatten
(curry apply append))
; cartesian takes two lists and returns their cartesian product
; e.g.
; > (cartesian '(1 2 3) '(4 5))
; ((1 . 4) (1 . 5) (2 . 4) (2 . 5) (3 . 4) (3 . 5))
(define cartesian
(lambda (l1 l2)
(flatten (map (curry stitch l2) l1))))
; cartesian-lists takes a list of lists
; and returns a single list containing the cartesian product of all of the lists.
; We start with a list containing a single 'nil', so that we create a
; "list of lists" rather than a list of "tuples".
; The other interesting function we use here is "fold-right" (sometimes called
; "foldr" or "reduce" in other implementations). It can be used
; to collapse a list from right to left using some binary operation and an
; initial value.
; e.g.
; (fold-right cons '() '(1 2 3))
; is equivalent to
; ((cons 1 (cons 2 (cons 3 '())))
; In our case, we have a list of lists, and our binary operation is to get the
; "cartesian product" between each list.
(define cartesian-lists
(lambda (lists)
(fold-right cartesian '(()) lists)))
; cartesian-map takes a n-argument function and n lists
; and returns a single list containing the result of calling that
; n-argument function for each combination of elements in the list:
; > (cartesian-map list '(a b) '(c d e) '(f g))
; ((a c f) (a c g) (a d f) (a d g) (a e f) (a e g) (b c f)
; (b c g) (b d f) (b d g) (b e f) (b e g))
(define cartesian-map
(lambda (f . lists)
(map (curry apply f) (cartesian-lists lists))))
Sin todos los comentarios y una sintaxis de definición de función más compacto tenemos:
(define (curry f . c) (lambda x (apply f (append c x))))
(define (stitch tuples element)
(map (curry cons element) tuples))
(define flatten (curry apply append))
(define (cartesian l1 l2)
(flatten (map (curry stitch l2) l1)))
(define cartesian-lists (curry fold-right cartesian '(()))))
(define (cartesian-map f . lists)
(map (curry apply f) (cartesian-lists lists)))
me pareció que el arriba era razonablemente "elegante" ... hasta que alguien me mostró la definición Haskell equivalente:
cartes f (a:b:[]) = [ f x y | x <- a , y <- b ]
cartes f (a:b:bs) = cartes f ([ f x y | x <- a , y <- b ]:bs)
2 líneas !!!
No estoy tan seguro de la eficacia de mi implementación, particularmente el paso "aplanar" fue rápido para escribir pero podría terminar llamando a "anexar" con un gran número de listas, que pueden ser o no muy eficiente en algunas implementaciones de Scheme .
Para la practicidad/utilidad última, usted querría una versión que pudiera tomar listas/secuencias/iterador "evaluadas perezosamente" en lugar de listas completamente especificadas .... una función "cartesian-map-stream" si lo desea, eso a continuación, devuelve una "secuencia" de los resultados ... pero esto depende del contexto (estoy pensando en el concepto de "transmisión" como se introdujo en SICP) ... y vendría gratis de la versión de Haskell gracias a su evaluación perezosa .
En general, en Scheme, si deseaba "romper" el bucle en algún punto, también podría usar una continuación (como lanzar una excepción pero es práctica aceptada en Scheme para el flujo de control).
¡Me divertí escribiendo esto!
Su pregunta no es muy específica. ¿Podría dar más información sobre lo que está tratando de hacer y con lo que está teniendo problemas? –
¿Tal vez podría intentar escribirlo con SRFI-42 y publicarlo aquí para demostrar lo que quiere lograr? – grettke