неявная рекурсия по схеме

Question

Мне нужна помощь при выполнении рекурсии в схеме, используя только функции абстрактного списка. В качестве примера, как бы я изменить этот код с явной рекурсии так, что она не будет иметь имя функции в организме:

(define (make_unique_list lst) 
    (cond 
    [(empty? lst) empty] 
    [(member? (first lst) (rest lst)) (make_unique_list (rest lst))] 
    [else (cons (first lst) (make_unique_list (rest lst)))])) 

Спасибо!

Answer 1

В R6RS схеме:

(import (rnrs) (rnrs lists)) 

(define (make-unique-list lst) 
    (reverse 
    (fold-left 
    (lambda (r e) (if (member e r) r (cons e r))) 
    '() 
    lst))) 

(display (make-unique-list '(1 2 3 4 3 5 6 3 2 1 7))) 
=> {1 2 3 4 5 6 7} 

В Ракетка:

(define (make-unique-list lst) 
    (reverse 
    (foldl 
    (lambda (e r) (if (member e r) r (cons e r))) 
    '() 
    lst))) 

или

(define (make-unique-list lst) 
    (reverse 
    (for/fold ((r '())) ((e (in-list lst))) 
    (if (member e r) r (cons e r))))) 

Обратите внимание, что в первые 2 примерах я использую reverse и foldl/fold-left, не foldr или fold-right (попробуйте сами убедиться, почему).

Кстати, эта процедура часто называют remove-duplicates и встраиваться в Ракетка:

(remove-duplicates '(1 2 3 4 3 5 6 3 2 1 7)) 

Answer 2

Это выглядит как fold. Объединив логику из непустых случаев в cond в одну функцию накопления, мы можем выборочно накапливать элементы в списке, который мы еще не видели.

Напомним, что функция, заданная для сгиба, имеет два параметра: один - текущий элемент, а другой - текущее накопленное значение. В этом случае текущий элемент будет иметь тип X, а текущим накопленным значением будет список X. Функция должна вернуть список X.

Если вам нужно сохранить порядок ввода списка, быть разумным при выборе между fold-right и fold-left или эквивалентами в вашей среде.

Answer 3

можно выразить анонимные рекурсивные функции в схеме с использованием так называемого Y combinator. Я не использовал его сам, но это в основном потому, что это сложно понять. Это полезно.

Смотри также: https://en.wikipedia.org/wiki/Fixed-point_combinator