Scheme/Lisp вложенные циклы и рекурсия

Question

Я пытаюсь решить проблему на Схеме, которая требует от меня использования вложенного цикла или вложенной рекурсии.

например. У меня есть два списка, которые я должен проверить на их декартово произведение.

Каков наилучший способ решения этих проблем? Любые указатели на то, как упростить эти типы функций?

---

Я немного уточню, так как мое намерение может быть недостаточно ясным.

Регулярное рекурсивная функция может выглядеть следующим образом:

(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

В схеме Функция «карта» часто удобна для вычисления одного списка на основе другого.

В самом деле, в схеме, карта имеет функцию «п-аргумент» и «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))) 

Я думал, выше было достаточно «элегантным» ... пока кто-то не показал мне эквивалентное определение Haskell:

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 линии !!!

Я не настолько уверен в эффективности моей реализации - в частности, шаг «сглаживания» был быстрым, но мог в конечном итоге вызвать «добавить» с очень большим количеством списков, что может быть или не быть очень эффективны на некоторых схемах .

Для максимальной практичности/полезности вам понадобится версия, которая может принимать «лениво оцененные» списки/потоки/итератор, а не полностью указанные списки .... функция «декартовой карты-потока», если хотите, что бы затем верните «поток» результатов ... но это зависит от контекста (я думаю о концепции «потока», представленной в SICP) ... и будет освобождаться от версии Haskell благодаря ленивой оценке ,

В общем, на схеме, если вы хотите «вырваться» из цикла в какой-то момент, вы также можете использовать продолжение (например, выброс исключения, но это принято на схеме в контрольном потоке).

Мне было весело писать это!

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