Donc, j'essaie de faire ce problème hw: écrivez une fonction qui prend deux arguments, une liste et un nombre, et la fonction renvoie l'index de l'occurrence la plus à gauche du nombre dans la liste. Par exemple:
Si '(1 2 3 3 4) et num = 3 , alors il renvoie 2
Si '(3 2 3 3 4) et num = 3 , alors il renvoie 0
J'ai pu faire cette partie, mais que faire si le numéro n'a jamais été trouvé? Que faire si je veux retourner false lorsque num n'est pas trouvé dans la liste? Comment je fais ça?
N'oubliez pas que j'essaie de faire cela avec une récursion correcte, pas une récursion de queue.
Voici mon code.
(define (first_elt_occ lst num)
(cond
((null? lst) #f)
((eq? (car lst) num) 0)
(else
(+ 1 (first_elt_occ (cdr lst) num)))))
(first_elt_occ '(1 2 3 3 4) 3) ;2
(first_elt_occ '(3 2 3 3 4) 3) ;0
(first_elt_occ '(1 2 5 4 3) 3) ;4
(first_elt_occ '(1 2 5 4 3) 6) ;Error
;(makes sense because you can't add boolean expression)
Une autre question que j'ai est, comment pourrais-je aborder ce problème, si on me demandait de renvoyer l'index de l'occurrence la plus à droite du nombre dans une liste (récursivité appropriée). Par exemple: '(3 4 5 4 3 7 ) , num = 3 renvoie 4 .
Merci!
4 Réponses :
Comme suggéré dans les commentaires, ce sera plus facile si nous implémentons la procédure en utilisant la récursivité de la queue - au fait, la récursivité de la queue est une «récursion appropriée», qu'est-ce qui vous fait penser autrement?
En définissant une procédure d'assistance appelée loop et en passant le résultat accumulé dans un paramètre, nous pouvons retourner soit #f soit l'index de l'élément:
(first_elt_occ '(1 2 3 3 4) 3) ; 2 (first_elt_occ '(3 2 3 3 4) 3) ; 0 (first_elt_occ '(1 2 5 4 3) 3) ; 4 (first_elt_occ '(1 2 5 4 3) 6) ; #f
Si, pour une exigence bizarre, vous ne pouvez pas utiliser la récursivité de queue dans votre solution, il est possible de réécrire votre solution originale pour tenir compte du cas où la réponse est #f - mais ce n'est pas aussi élégant ou efficace:
(define (first_elt_occ lst num)
(cond
((null? lst) #f)
((equal? (car lst) num) 0)
(else
(let ((result (first_elt_occ (cdr lst) num)))
(if (not result) #f (add1 result))))))
Quoi qu'il en soit, cela fonctionne comme prévu:
(define (first_elt_occ lst num)
(let loop ((lst lst) (acc 0))
(cond
((null? lst) #f)
((equal? (car lst) num) acc)
(else (loop (cdr lst) (add1 acc))))))
Merci. Mon professeur veut que nous implémentions le problème en utilisant la récursivité de la queue et la "récursivité appropriée" - la pile grandit et rétrécit. Je savais déjà comment l'implémenter dans la récursivité de la queue.
On ne sait pas pourquoi vous vous opposez à la récursivité de la queue. Vous parlez de "récursivité appropriée", qui n'est pas un terme technique que quiconque utilise, mais je suppose que vous voulez dire une récursivité sans queue: un processus récursif plutôt qu'un processus itératif, en termes SICP. Soyez assuré que la récursivité de la queue est tout à fait appropriée et qu'elle est en général préférable à la récursivité sans queue, à condition de ne pas avoir à faire d'autres compromis pour permettre la récursivité de la queue.
Comme le dit Óscar López, ce problème est vraiment plus facile à résoudre avec la récursivité de la queue. Mais si vous insistez, il est certainement possible de le résoudre à la dure. Vous devez éviter d'ajouter aveuglément 1 au résultat: à la place, inspectez-le, ajoutez-lui 1 s'il s'agit d'un nombre, ou renvoyez-le inchangé s'il est faux. Par exemple, voyez le number? prédicat.
Je ne recommande pas réellement d'adopter cette approche car une implémentation récursive de queue normale est beaucoup plus efficace, plus simple et plus facile à comprendre, mais vous pouvez utiliser une continuation pour court-circuiter le déroulement de la pile d'appels en cas d'échec:
(define (first_elt_occ lst num)
(call/cc
(lambda (return)
(letrec ((loop (lambda (lst)
(cond
((null? lst) (return #f))
((= (car lst) num) 0)
(else (+ 1 (loop (cdr lst))))))))
(loop lst)))))
Merci. Mon professeur veut que nous implémentions le problème en utilisant la récursivité de la queue et la "récursivité appropriée" - la pile grandit et rétrécit. Je savais déjà comment l'implémenter dans la récursivité de la queue.
La fonction de base "squelette" de recherche de première occurrence est
(define (first_elt_occ lst num)
(let ((+ (lambda (a b) ...... )))
(and (not (null? lst))
(+ (and (= (car lst) num) 0)
(first_elt_occ (cdr lst) num)))))
Cela ne renvoie cependant pas d' index. Comment l'ajouter?
> (first_elt_occ '(1 2 3 3 4) 3) 2 > (first_elt_occ '(3 2 3 3 4) 3) 0 > (first_elt_occ '(3 2 3 3 4) 5) #f
Est-ce que ça marche? Pas si l'élément n'est pas là! Cela provoquera alors une erreur. Comment y remédier? Changer le + , c'est comme ça!
(define (first_elt_occ lst num)
(let ((+ (lambda (a b) (if b (+ a b) b))))
(and (not (null? lst))
(or (and (= (car lst) num) 0)
(+ 1 (first_elt_occ (cdr lst) num))))))
Et maintenant, cela fonctionne comme prévu:
(define (first_elt_occ lst num)
(and (not (null? lst))
(or (and (equal (car lst) num) 0)
(+ 1 (first_elt_occ (cdr lst) num)))))
Et pour obtenir votre deuxième fonction souhaitée, nous la restructurons un peu, en
(define (first_elt_occ lst num)
(and (not (null? lst))
(or (equal (car lst) num)
(first_elt_occ (cdr lst) num))))
Maintenant, que devrait être ce nouveau + ? Pouvez-vous finir ça? C'est simple!
Trivial à voir avec la récursion de queue (et plus efficace) ....
grandement demandé! :)
Vous avez deux questions différentes dans le même article, abordons la première ici et postez une deuxième question une fois que vous avez trouvé une réponse satisfaisante pour la première question.