Как сделать последовательность Фибоначчи в ракетке, используя функции абстрактного списка

Question

Я пытаюсь написать ракетную программу, которая вычисляет сумму первых n членов в последовательности Фибоначчи без использования рекурсии и только с использованием функций абстрактного списка (например, map, builld-list, foldr, foldl). Я могу использовать вспомогательные функции. Я застрял на том, как составить список чисел Фибоначчи без использования рекурсии. Я думал, что мог бы использовать лямбда-функцию:

(lambda (lst) (+ (list-ref lst (- (length lst) 1)) (list-ref lst (- (length lst 2)))))

Но я не уверен, как сгенерировать список ввода / как добавить это в функцию. Когда у меня есть последовательность Фибоначчи, я знаю, что могу просто использовать (foldl + (car lst) (cdr lst)), чтобы найти сумму. Может ли кто-нибудь объяснить мне, как сделать последовательность Фибоначчи / дать мне подсказку?

Answer 1

; This is how I figure out
#|
(1 2 3 4 (0 1))
-> (1 2 3 (1 1))
-> (1 2 (1 2))
-> (1 (2 3))
-> (3 5)
|#

(define (fib n)
  (cond
    [(= n 0) 0]
    [(= n 1) 1]
    [(> n 1)
     (second
      (foldr (λ (no-use ls) (list (second ls) (+ (first ls) (second ls))))
             '(0 1)
             (build-list (- n 1) (λ (x) x))))]))

(fib 10)
(build-list 10 fib)

Версия обновления 2

(define (fib-v2 n)
  (first
   (foldr (λ (no-use ls) (list (second ls) (+ (first ls) (second ls))))
          '(0 1)
          (build-list n (λ (x) x)))))


(build-list 10 fib-v2)

Answer 2

fib-seq создает список первых n чисел Фибоначчи, а fib-sum - сумму первых n чисел Фибоначчи.

; Number -> [List-of Number]
(define (fib-seq n)
  (cond [(= n 0) '()]
        [(= n 1) '(0)]
        [else (reverse
               (for/fold ([lon '(1 0)]) ([_ (in-range (- n 2))])
                 (cons (apply + (take lon 2)) lon)))]))

; Number -> Number
(define (fib-sum n)
  (if (= n 0) 0 (add1 (apply + (take (fib-seq n) (sub1 n))))))

Примечание: fib-sum эквивалентно следующим рекурсивным версиям:

(define (fib0 n)
  (if (< n 2) n (+ (fib0 (- n 1)) (fib0 (- n 2)))))

(define (fib1 n)
  (let loop ((cnt 0) (a 0) (b 1))
    (if (= n cnt) a (loop (+ cnt 1) b (+ a b)))))

(define (fib2 n (a 0) (b 1))
  (if (= n 0) 0 (if (< n 2) 1 (+ a (fib2 (- n 1) b (+ a b))))))

Когда у меня есть последовательность Фибоначчи, я знаю, что могу просто использовать (foldl + (car lst) (cdr lst)), чтобы найти сумму.

Примечаниечто вам не нужно генерировать промежуточную последовательность, чтобы найти сумму. Рассмотрим (быстрое) матричное решение для возведения в степень:

(require math/matrix)
(define (fib3 n)
  (matrix-ref (matrix-expt (matrix ([1 1] [1 0])) n) 1 0))

Тестирование:

(require rackunit)
(check-true
 (let* ([l (build-list 20 identity)]
        [fl (list fib0 fib1 fib2 fib3 fib-sum)]
        [ll (make-list (length fl) l)])
   (andmap (λ (x) (equal? (map fib0 l) x))
           (map (λ (x y) (map x y)) fl ll))))