在满足谓词之前构建列表的替代方法？

Question

这是我构建斐波那契数列的方法，其值不超过 x:

(define (fibs-upto x)
  (for/list ([i (in-naturals)]
             #:break (> (fib i) x))
            (fib i)))

是否有另一种更简洁的方法可以在不使用 #:break 且不使用 #lang lazy 来构建无限懒惰列表的情况下执行此操作？

Answer 1

这里是 (fib i) 只计算一次的解决方案。

(define (fibs-upto x)
  (for*/list ([i     (in-naturals)]
              [fib-i (in-value (fib i))]
              #:break (> fib-i x))
    fib-i))

但阅读标准循环可能更容易：

(define (fibs-upto x)
  (define (loop i)
    (define fib-i (fib i))
    (if (> fib-i x)
        '()
        (cons fib-i (loop (+ i 1)))))
  (loop 0))

也就是说，重要的是 fib 将上述解决方案的先前计算值缓存为 O(n)。

更新

使用sequence-map的版本：

(define (fibs-upto x)
  (for/list ([y (sequence-map fib (in-naturals))]
             #:break (> y x))
    y))

Answer 2

由于您在 racket 中发布了此内容...这可能是解决问题的方法，但我确实更改了其中的一部分，如果出现问题则很容易解决。希望对您有所帮助

// i = 开始的数字，x = 上升到的数字

(define (fibs-upto i x)
  (cond
    [(> (fib i) x) empty]
    [else (cons (fib i)(fibs-upto (+ i 1) x))]))

解决方法

(define (fibs-upto x)
  (fibs-help 0 x))

(define (fibs-help i x)
  (cond
    [(> (fib i) x) empty]
    [else (cons (fib i)(fibs-help (+ i 1) x))]))

Answer 3

如果您只想要斐波那契数列，您可以例如

(define (fib-upto limit)
  (let loop ([fibs '(1 1)])
    (let ((fn (+ (first fibs) (second fibs))))
      (if (> fn limit)
          (reverse fibs)
          (loop (cons fn fibs))))))
;; e.g.:
(fib-upto 100)
'(1 1 2 3 5 8 13 21 34 55 89)

如果您想了解一些使用停止条件构建列表的惯用方法，请查看展开（或展开-right，尽管您更愿意展开）-- http://srfi.schemers.org/srfi-1/srfi-1.html#FoldUnfoldMap

在满足谓词之前构建列表的替代方法？

Alternative way to build a list until predicate is satisfied?

lisp

racket