Scheme中的迭代範圍函數/ Lisp

我想實現範圍函數（start，end，inc），該函數從開始到結束產生所有自然數，增量爲inc。這是第一個版本：Scheme中的迭代範圍函數/ Lisp

(define (gen start end step) 
    (if (>= start end) 
    '() 
    (cons start (gen (+ step start) end step))))

的問題是，這並不是尾遞歸。另一個嘗試：

(define (gen-iter start end step acc) 
    (if (>= start end) 
    acc 
    (gen-iter (+ step start) end step (cons start acc))))

但這產生相反的順序:) 名單所以，是的，我可以用O（n）的扭轉它，並很高興，但我有點堅持在這裏，努力使功能將自始至終構建一個適當順序的列表，而不會在每個迭代上追加，因爲追加代價高昂。還有一個內置的列表，但我不知道它是如何運作的。

來源

2016-02-14 artemonster

你可以使用一個隊列：http://rosettacode.org/wiki/Queue/Usage#Racket – coredump

規範的Scheme方式是使用'reverse'，我敢說這不會是你的應用程序的瓶頸無論如何。至於Racket如何操作，請使用Dr Racket中的「打開定義文件」。 – uselpa

正如uselpa在評論中已經說過的那樣，解決方案將在末尾使用reverse。擴展後，range的球拍執行與gen-iter函數的結果非常相似，除了某些情況下您可能沒有想到。

的range球拍的實際實現使用(for/list ([i (in-range start end step)]) i)，但什麼是擴展到實際上相當於

(reverse 
(for/fold ([fold-var null]) 
      ([i (in-range start end step)]) 
    (cons i fold-var)))

，例外的是它採用了alt-reverse功能，而不是reverse，它使用for/fold/derived更好的錯誤報告。如果你展開，它相當於一些這方面的簡化（刪除不必要的let-values包裝，錯誤檢查等）

(reverse 
(let ([start start] [end end] [inc step]) 
    (let for-loop ([fold-var null] [pos start]) 
    (if (if (>= step 0) 
      (< pos end) 
      (> pos end)) 
     (let ([i pos]) 
      (let ([fold-var (cons i fold-var)]) 
      (for-loop 
       fold-var 
       (+ pos inc)))) 
     fold-var))))

而得名讓有相當於定義這樣一個輔助功能：（後部分替代let S和解除幫手range功能外）

(define (range start end step) 
    (reverse 
    (range-reversed null start end step))) 
(define (range-reversed fold-var pos end step) 
    (if (if (>= step 0) 
      (< pos end) 
      (> pos end)) 
     (range-reversed 
     (cons pos fold-var) 
     (+ pos step) 
     end 
     step) 
     fold-var))

這仍然是從您的解決方案不同，因爲你的解決方案假定step是積極的，而這一個工程，即使step爲負。如果step是肯定的，if條件將是(< pos end)而不是嵌套的if。

它也使用(< pos end)您使用(>= pos end)，但它也切換if情況。如果(< x y)與(not (>= x y))相同，這相當於您的解決方案，因爲(if (not a) b c)相當於(if a c b)。但是，至少有一種情況我可以想到哪裏不是這樣，start或end是+nan.0。對於這種情況，球拍的range函數將返回一個空列表，而您的解決方案將進入無限循環。

來源

2016-02-14 13:57:59

這並不總是那麼容易看到它，但「反向」在這裏是一個關鍵字。爲了使迭代，你需要做的實際工作中反向：

(define (my-range start end step)  
    (define (helper n acc) 
    (if (= end n) 
     (cons n acc) 
     (helper (- n step) (cons n acc)))) 

    (define actual-end end) ; this needs improvement 
    (helper actual-end '()))

正如range球拍，你應該得到這些結果：

(my-range 1 10 1) ; ==> (1 2 3 4 5 6 7 8 9) 
(my-range 10 1 -1) ; ==> (10 9 8 7 6 5 4 3 2)

爲了得到這個正確actual-end需要做的找到正確的基於數學的價值。

(my-range 1 10 2) ; ==> (1 3 5 7 9) (actual-end should be 9) 
(my-range 10 1 -2) ; ==> (10 8 6 4 2) (actual-end should be 2)

我想你可以使用ceiling程序與正常的數學程序一起得到這個正確的。

來源

2016-02-14 13:34:48 Sylwester

Scheme中的迭代範圍函數/ Lisp

回答

相關問題