Вставить элемент в начало списка в списке списков

Question

У меня небольшие проблемы с заданием. Я должен создать процедуру, которая запрашивает список списков и элемент, и переходит к добавлению элемента в первую позицию в каждом подсписке. Мне удалось сделать это, и это выглядит следующим образом:

(define (add-element lst elem) 
    (foldr cons lst (list elem))) 

(define (insert-first lst1 x) 
    (cond 
    [(empty? lst1) empty] 
    [else (local [(define insert (add-element(first lst1) x))] 
     (cons insert (insert-first (rest lst1) x)))])) 

Так что, если вы должны были ввести (insert-first '((a b) (c d)) вы в конечном итоге с (list (list 'x 'a 'b) (list 'x 'c 'd))

Единственная проблема заключается в том, что я должен кодировать процедуру с использованием map и local. Последний, по-моему, я сделал, но я не могу на всю жизнь понять, как использовать map.

Answer 1

(define (insert-first elt lst) 
    (map (lambda (x) 
     (cons elt x)) 
     lst)) 

затем

(insert-first 'x '((a b) (c d))) 
=> '((x a b) (x c d)) 

Answer 2

(define (insert-first lst elem) 
    (foldr (lambda (x y) (cons (cons elem x) y)) '() lst)) 

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

Answer 3

foldr embodies определенный шаблон рекурсии,

(foldr g init [a,b,c,...,z]) 
= (g a (foldr g init [b,c,...,z])) 
.... 
= (g a (g b (g c ... (g z init) ...))) 

если вручную расширить foldr вызов в определении функции add-element, мы получаем

(add-element lst elem) 
    = (foldr cons lst (list elem)) 
    = (cons elem (foldr cons lst '())) 
    = (cons elem lst) 

затем, глядя на вашу insert-first функцию, мы видим также следует за рекурсивным рисунком foldr,

(insert-first lst1 x) 
= (foldr (lambda(a r)(cons (add-element a x) r)) empty lst1) 
= (foldr (lambda(a r)(cons (cons x a) r)) empty lst1) 

Но (foldr (lambda(a r) (cons (g a) r)) empty lst) === (map g lst), потому что для объединения суб-терминов с cons необходимо построить список, что и есть map; и таким образом мы получаем

(insert-first lst1 x) = (map (lambda(a)(cons x a)) lst1) 

и поэтому мы можем написать

(define (insert-first lst1 x) 
    (local [(define (prepend-x a) (cons ... ...))] 
    (map ... ...)))