球拍映射笛卡尔积事物

Question

在 racket 中，像 map 这样的高阶函数用在两个列表上是这样做的：

(map list '(1 2 3) '(1 2 3))
> '( (1 1) (2 2) (3 3) )

但我想要这样的笛卡尔积：

'( (1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3) )

我怎样才能做到这一点？最好有高阶函数？

Answer 1

这是一个完全使用高阶函数的方法（foldr、append-map和map；现在还有compose1、curry、和 curryr):

(define (cartesian-product . lists)
  (foldr (lambda (a b)
           (append-map (compose1 (curryr map b) (curry cons))
                       a))
         '(())
         lists))

请原谅可怕的参数名称。总有一天我会想出一件好事。 :-)

Answer 2

> (require unstable/list)
> (cartesian-product '(1 2 3) '(a b c))
'((1 a) (1 b) (1 c) (2 a) (2 b) (2 c) (3 a) (3 b) (3 c))

见http://docs.racket-lang.org/unstable/list.html#%28def._%28%28lib._unstable%2Flist..rkt%29._cartesian-product%29%29

Answer 3

在 SCIP 第 2.2.3 章“Sequences as Conventional Interfaces”中，作者向我们展示了解决此类问题的一般方法。实际上有一个类似的例子。该书使用平面图作为通用抽象。The combination of mapping and accumulating with append is so common in this sort of program that we will isolate it as a separate procedure: flatmap。这是使用平面图的解决方案：

>(define (flatmap proc seq)                                                                                                                                    
  (foldr append '() (map proc seq)))   
>(flatmap                                                                                                                                  
   (lambda (x)                                                                                                                              
     (map                                                                                                                                   
       (lambda (y) (list y x))                                                                                                               
       '(1 2 3)))                                                                                                                            
   '(a b c))                                                                                                                                
'((1 a) (2 a) (3 a) (1 b) (2 b) (3 b) (1 c) (2 c) (3 c))

球拍映射笛卡尔积事物

Racket map cartesian product thing

dictionary

cartesian-product

racket