球拍图笛卡尔积物

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

请参阅cartesian-product%29%29

Answer 3

在SCIP第2.2.3章“序列作为常规接口，作者向我们展示了解决此类问题的一般方法。实际上有一个类似的例子。该书使用平面图作为一个常见的抽象。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))