Scheme / Lisp嵌套循环和递归 [英] Scheme/Lisp nested loops and recursion

问题描述

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

例如。我有两个列表，我必须检查他们的Cartesian产品的条件。

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

---

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

常规的递归函数可能如下所示：

 （define因子n）
（factorial-impl n 1））
 
（define（factorial-implnt）
（if（eq？n 0）
t 
（factorial-impl（ -  n 1）（* tn））））
  

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

作为一个具体的例子，我正在寻找最简单的方式来访问两个列表的笛卡尔积的所有项目。 解决方案在计划中，
map函数通常用于计算基于另一个列表的一个列表。

事实上，在计划，地图tak es是一个n-argument函数，n列出并为每个列表的每个对应元素调用
函数：

 > （3 * 5）（1 2 3））
 b 
但是一个非常自然的添加就是一个笛卡尔映射函数，它可以通过从每个列表中选取一个元素的所有不同方式调用您的n参数函数。我花了一段时间才弄清楚如何做到这一点，但是在这里你会发现： 
 
 
 ;咖喱需要：
; *一个p参数函数AND 
; * n实际参数，
;并返回一个只需要（p-n）参数
的函数;第一个n参数已经绑定。一个简单的
;例如
; （定义add1（咖喱+ 1））
; （add1 3）
; => 4 
;无论何时拨打
，许多其他语言都会隐含咖喱;一个没有足够参数的函数。 
（define curry 
（lambda（f。c））（lambda x（apply f（append c x）））））
 
;取一个元组列表和一个元素，返回另一个列表
;将该元素拼接到每个元组：
;例如
; > （针'（1 2 3）4）
; （（4.1）（4.2）（4.3））
（定义针
（lambda（元组元素）
（map（咖喱元素）元组））
 
; Flatten获取列表并生成一个列表
;例如
; > （flatten'（（1 2）（3 4）））
; （1 2 3 4）
（定义扁平
（咖喱申请追加））
 
;笛卡尔需要两个列表并返回它们的笛卡尔积
;例如
; > （笛卡儿'（1 2 3）'（4 5））
; （（1.4）（1.5）（2.4）（2.5）（3.4）（3.5））
（定义笛卡尔
（lambda（l1 l2）
（flatten（map（curry stitch l2）l1））））
 
;笛卡尔列表需要列表
;并返回包含所有列表的笛卡尔乘积的单个列表。 
;我们从一个包含单个'零'的列表开始，以便创建一个
; 列表清单而不是元组列表。 
 
;我们在这里使用的另一个有趣的函数是右对齐（有时称为
;在其他实现中称为foldr或reduce）。它可以用
;使用一些二进制操作和
从右到左折叠列表;初始值。 
;例如
; （fold-right cons'（）'（1 2 3））
;相当于
; （（cons 1（cons 2（cons 3'（））））
;在我们的例子中，我们有一个列表清单，我们的二元运算是获得
;笛卡尔乘积每个列表
（定义笛卡尔列表
（lambda（列表）
（折叠右笛卡尔'（（））列表）））
 
; cartesian- map使用n参数函数，n列出
;并返回一个单独的列表，其中包含调用
的结果;列表中每个元素的每个组合的n参数函数：
;> ;（笛卡尔地图列表（ab）'（cde）'（fg））
;（（acf）（acg）（adf）（adg）（aef）（aeg）（bcf）
 ;（bcg）（bdf）（bdg）（bef）（beg））
（定义cartesian-map 
（lambda（f。lists）
（map（curry apply f） -list列表））））
  
没有所有的注释和一些更紧凑的函数定义语法，我们有：  
 
 
 （define（curry f。c）（lambda x（apply f（append cx））））
定义（拼接元组）
（map（咖喱元素）元组）
（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。列表）
（map（curry apply f）（cartesian-lists lists）））
  
我认为上面是相当优雅的......直到有人向我展示了相当于Haskell的定义：
  cartes f（a： b：[]）= [fxy | （a：b：bs）= cartes f（[fxy | x <-a，y< -b]：bs）
  
 2行!!!  
 
 
我不是对我执行的效率很有信心 - 尤其是扁平化的步骤很快就写出来了，但最终可能会调用追加
来获得大量的列表，这些列表在一些Scheme中可能有效或可能不是很有效b $ b实现。
 
 
为了最终的实用性/实用性，您需要一个可以采用懒惰评估列表/流/迭代器而不是完全指定列表的版本...如果你愿意的话，可以使用cartesian-map-stream函数，然后返回结果的流......但这取决于上下文（我正在考虑在SICP中引入的stream概念）。 ..并且可以免费获得Haskell版本，这要归功于它的懒惰评估。
 
 
 
一般来说，在Scheme中，如果您想要爆发循环有些观点你也可以用一个继续（就像抛出一个异常，但它在控制流程的Scheme中被接受）。
 
 
我很开心写这个！
 
I'm trying to solve a problem in Scheme which is demanding me to use a nested loop or a nested recursion.

e.g. I have two lists which I have to check a condition on their Cartesian product.

What is the best way to approach these types of problems? Any pointers on how to simplify these types of functions?


I'll elaborate a bit, since my intent might not be clear enough.


A regular recursive function might look like this:
(define (factorial n)
  (factorial-impl n 1))

(define (factorial-impl n t)
  (if (eq? n 0)
      t
      (factorial-impl (- n 1) (* t n))))
Trying to write a similar function but with nested recursion introduces a new level of complexity to the code, and I was wondering what the basic pattern is for these types of functions, as it can get very ugly, very fast.

As a specific example, I'm looking for the easiest way to visit all the items in a cartesian product of two lists.
解决方案
In Scheme,
The "map" function is often handy for computing one list based on another.

In fact, in scheme, map takes an "n-argument" function and "n" lists and calls the
function for each corresponding element of each list:
> (map * '(3 4 5) '(1 2 3))
(3 8 15)
But a very natural addition to this would be a "cartesian-map" function, which would call your "n-argument" function with all of the different ways of picking one element from each list. It took me a while to figure out exactly how to do it, but here you go:
; 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))))
Without all the comments and some more compact function definition syntax we have:
(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)))
I thought the above was reasonably "elegant"... until someone showed me the equivalent Haskell definition:
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 lines!!!

I am not so confident on the efficiency of my implementation - particularly the "flatten" step was quick to write but could end up calling "append"
with a very large number of lists, which may or may not be very efficient on some Scheme
implementations.

For ultimate practicality/usefulness you would want a version that could take "lazily evaluated" lists/streams/iterator rather than fully specified lists.... a "cartesian-map-stream" function if you like, that would then return a "stream" of the results... but this depends on the context (I am thinking of the "stream" concept as introduced in SICP)... and would come for free from the Haskell version thanks to it's lazy evaluation.

In general, in Scheme, if you wanted to "break out" of the looping at some point you could also use a continuation (like throwing an exception but it is accepted practise in Scheme for control flow).

I had fun writing this!

                        
这篇关于Scheme / Lisp嵌套循环和递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！