Scheme/Lisp嵌套循环和递归

Question

我试图解决一个问题，要求我使用嵌套循环或嵌套递归的Scheme。

例如我有两个名单，我必须检查他们的笛卡尔产品的条件。

解决这些类型问题的最佳方法是什么？任何关于如何简化这些类型的函数的指针？

---

我会详细说明一下，因为我的意图可能不够清楚。

有规律的递归函数可能是这样的：

(define (factorial n) 
    (factorial-impl n 1)) 

(define (factorial-impl n t) 
    (if (eq? n 0) 
     t 
     (factorial-impl (- n 1) (* t n)))) 

试图写一个类似的功能，但与嵌套递归引入了复杂的的代码一个新的水平，我想知道是什么的基本模式是这些类型的功能，因为它可以变得非常难看，速度非常快。

作为一个具体的例子，我正在寻找最简单的方式来访问两个列表的笛卡尔积中的所有项目。

Answer 1

在Scheme中， “map”函数通常用于计算基于另一个列表的一个列表。

事实上，在方案中，地图需要一个“正论证”功能和“n”名单，并调用 功能为每个列表中的每个对应的元素：

> (map * '(3 4 5) '(1 2 3)) 
(3 8 15) 

但一个很自然的除这将是一个“笛卡尔映射”函数，它将用你从每个列表中选取一个元素的所有不同方式调用你的“n-argument”函数。我花了一段时间才能弄清楚到底如何做到这一点，但在这里你去：

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

没有所有的评论和一些更紧凑的功能定义语法有：

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

我以为以上是合理的“优雅” ......直到有人向我展示了相当的哈斯克尔定义：

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线！

我不是那么有信心在我的执行效率 - 尤其是“扁平化”的步骤是快写，但最终可能会调用“追加” 一个非常大的数量的列表，这可能会或可能不会很在一些Scheme实现上效率很高。

为了达到最终的实用性/实用性，您需要一个可以采用“懒惰评估”列表/流/迭代器而不是完全指定列表的版本....如果您喜欢，可以使用“笛卡尔地图流”功能然后返回结果的“流”......但这取决于上下文（我正在考虑在SICP中引入的“流”概念）......并且由于它的延迟评估而免费来自Haskell版本。一般来说，在Scheme中，如果你想在某个时间点“循环”循环，你也可以使用延续（例如抛出一个异常，但在控制流程的Scheme中被接受）。

我很开心写这个！

Answer 2

我不知道我看到了什么问题。 我相信在函数式编程中你必须理解的主要事情是：通过编写几个更简单的函数来构建复杂的函数。

例如，在这种情况下：

;compute the list of the (x,y) for y in l 
(define (pairs x l) 
    (define (aux accu x l) 
    (if (null? l) 
     accu 
     (let ((y (car l)) 
       (tail (cdr l))) 
      (aux (cons (cons x y) accu) x tail)))) 
    (aux '() x l)) 

(define (cartesian-product l m) 
    (define (aux accu l) 
    (if (null? l) 
     accu 
     (let ((x (car l)) 
       (tail (cdr l))) 
      (aux (append (pairs x m) accu) tail)))) 
    (aux '() l))  

您识别不同的步骤：获得笛卡尔积，如果“循环”在第一列表中，你将不得不能计算第二个列表中的(x,y)的列表，y。

Answer 3

这里有一些很好的答案了，但对于简单的嵌套函数（如您的尾递归阶乘），我更喜欢一个名为令：

(define factorial 
    (lambda (n) 
    (let factorial-impl ([n n] [t 1]) 
     (if (eq? n 0) 
     t 
     (factorial-impl (- n 1) (* t n))))))