Sơ đồ/vòng lặp lồng nhau Lisp và đệ quy

Question

Tôi đang cố giải quyết vấn đề trong Đề án đang yêu cầu tôi sử dụng vòng lặp lồng nhau hoặc đệ quy lồng nhau.

ví dụ: Tôi có hai danh sách mà tôi phải kiểm tra một điều kiện trên sản phẩm Descartes của họ.

Cách tốt nhất để tiếp cận các loại vấn đề này là gì? Bất kỳ con trỏ nào về cách đơn giản hóa các loại chức năng này?

---

Tôi sẽ giải thích một chút, vì mục đích của tôi có thể không đủ rõ ràng.

Một hàm đệ quy thường xuyên có thể trông như thế này:

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

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

Đang cố gắng để viết một chức năng tương tự nhưng với lồng đệ quy giới thiệu một cấp độ mới của sự phức tạp để mã, và tôi đã tự hỏi những gì mô hình cơ bản là cho các loại chức năng này, vì nó có thể rất xấu, rất nhanh.

Ví dụ cụ thể, tôi đang tìm cách dễ nhất để truy cập tất cả các mục trong một sản phẩm Descartes của hai danh sách.

Answer 1

Trong sơ đồ, Chức năng "bản đồ" thường hữu ích để tính toán một danh sách dựa trên danh sách khác.

Trong thực tế, trong sơ đồ, bản đồ có một "n đối số" chức năng và "n" danh sách và gọi chức năng cho mỗi phần tử tương ứng của mỗi danh sách:

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

Nhưng một bổ sung rất tự nhiên để đây sẽ là một chức năng "bản đồ Descartes", sẽ gọi hàm "n-argument" của bạn với tất cả các cách khác nhau để chọn một phần tử từ mỗi danh sách. Tôi đã mất một thời gian để tìm ra chính xác làm thế nào để làm điều đó, nhưng ở đây bạn đi:

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

Nếu không có tất cả các ý kiến ​​và một số cú pháp định nghĩa hàm nhỏ gọn hơn chúng ta có:

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

Tôi nghĩ ở trên là hợp lý "thanh lịch" ... cho đến khi ai đó cho tôi thấy định nghĩa Haskell tương đương:

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 dòng !!!

Tôi không tự tin về hiệu quả thực hiện của mình - đặc biệt là bước "làm phẳng" nhanh chóng viết nhưng có thể kết thúc cuộc gọi "nối thêm" với số lượng danh sách rất lớn, có thể có hoặc không hiệu quả trên một số sơ đồ triển khai .

Để có tính thực tiễn/hữu ích cuối cùng, bạn sẽ muốn có phiên bản "danh sách/luồng/vòng lặp được đánh giá một cách lười biếng" thay vì danh sách được chỉ định đầy đủ .... một chức năng "cartesian-map-stream" nếu bạn muốn, sau đó trả về một "dòng" của các kết quả ... nhưng điều này phụ thuộc vào ngữ cảnh (tôi đang nghĩ đến khái niệm "stream" như được giới thiệu trong SICP) ... và sẽ miễn phí từ phiên bản Haskell nhờ nó đánh giá lười biếng . Nói chung, trong Đề án, nếu bạn muốn "thoát ra" của vòng lặp tại một số điểm bạn cũng có thể sử dụng một sự tiếp tục (như ném một ngoại lệ nhưng nó được chấp nhận thực hành trong Đề án cho luồng điều khiển).

Tôi đã vui vẻ viết điều này!

Answer 2

Tôi không chắc mình thấy vấn đề là gì. Tôi tin rằng điều chính bạn phải hiểu trong lập trình hàm là: xây dựng các hàm phức tạp bằng cách soạn một số hàm đơn giản hơn.

Ví dụ, trong trường hợp này:

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

Bạn xác định các bước khác nhau: để có được những sản phẩm Descartes, nếu bạn "loop" trong danh sách đầu tiên, bạn sẽ có để có thể tính danh sách (x,y), cho y trong danh sách thứ hai.

Answer 3

Có một số câu trả lời tốt ở đây đã có, nhưng đối với các chức năng lồng nhau đơn giản (như thừa đuôi-đệ quy của bạn), tôi thích một let tên:

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