Scheme 函数从 x 上下写数字

Scheme function to write numbers up and down from x

我不确定最好的表达方式是什么,所以我只是想举个例子。

(高-低 4) -> (0 1 2 3 4 3 2 1 0)

(高-低 0) -> (0)

(define low 
(λ (a)
   (cond
       [(zero? a) '()]
       [else (cons (sub1 a) (low (sub1 a)))])))

我认为最好的方法是将它分成两个独立的函数并在主函数中调用它们。上面的代码是函数的第二部分,但我正在努力定义它的高部分 (0-a)

欢迎任何帮助 (这不是作业,我只是想了解 Scheme 的工作原理)。

使用内置列表程序如何?它会容易得多,此外,这是使用 Scheme 时考虑解决方案的推荐方式,它鼓励函数式编程风格的编码:

(define (high-low n)
  (let ((lst (build-list n identity)))
    (append lst
            (cons n
                  (reverse lst)))))

例如:

(high-low 4)
=> '(0 1 2 3 4 3 2 1 0)

既然你想学,我猜你也不想用很多实用函数,所以我帮你high。请注意,当您要构建列表时,有两件事:起始编号和结束编号。

对于low,这很容易,因为结束数字是字面上的 0,而起始数字会发生变化,因此您可以仅使用一个变量来跟踪。

对于high,每次迭代都需要更改起始编号,如low。但是,结尾数字不是文字(尽管它是常量),因此我们需要它的信息。因此,我们将添加结束数字作为函数的参数之一。也就是说,我们期望

(high 1 10) ; evaluates to (list 1 2 3 4 5 6 7 8 9 10)

正文将是:

(define high
  (λ (start stop)
    ...))

终止条件是start超过stop。这是答案为 '().

的基本情况
(define high
  (λ (start stop)
    (cond
      [(> start stop) '()]
      ...)))

否则,start小于或等于stop。答案是从 start 开始并在 stop 结束的列表,与 start 附加到从 (add1 start) 开始并在 [=20 结束的列表的前面相同=].即:

high start stop = [start start+1 start+2 ... stop] 
                = [start] + [start+1 start+2 start+3 ... stop]
                = [start] + high start+1 stop

因此:

(define high
  (λ (start stop)
    (cond
      [(> start stop) '()]
      [else (cons start (high (add1 start) stop))])))

#!racket(又名 #lang racket)有一个 range 程序,所以如果你手上有球拍的力量,你可以这样做:

(define (high-low n)
  (append (range n)         ; 0 to n-1
          (range n -1 -1))) ; n to 0

如果您想滚动自己的递归循环,您可以将其视为反向构建一个列表,从零开始递增 1 直到达到极限,然后递减直到零。步骤发生变化,当您的当前值等于最终值并且您的方向正在减少时,您是终点线的一个元素。

(define (high-low n)
  (let loop ((cur 0) (limit n) (step add1) (acc '()))
    (cond ((not (= cur limit)) ; general step in either direction
           (loop (step cur) limit step (cons cur acc)))
          ((eq? step add1)     ; turn
           (loop cur 0 sub1 acc))
          (else                ; finished
           (cons cur acc)))))

我想有很多方法可以给这只猫蒙皮,而这只是一种尾递归方法。

这里还有几个选项。使用 named letquasi-quote...

(define (high-low n)
  (let hi-lo ((i 0))
    (if (= i n) `(,i) `(,i ,@(hi-lo (+ i 1)) ,i))))

...使用 do 的另一个选项:

(define (high-low2 n)
  (do ((i (- n) (+ i 1))
       (out '() (cons (- n (abs i)) out)))
      ((> i n) out)))

这是一个过于笼统的解决方案,它建立在一个以相当笼统的方式构建列表的函数之上。它的优点是尾递归:它可以构建任意长的列表而不会爆炸,但缺点是需要向后构建它们并且有点难以理解。

函数如下:

(define (lister base inc stop cont)
  ;; start with a (non-empty) list, base;
  ;; cons more elements of the form (inc (first ...)) to it;
  ;; until (stop (first ...)) is true;
  ;; finally call cont with the resulting list
  (define (lister-loop accum)
    (if (stop (first accum))
        (cont accum)
        (lister-loop (cons (inc (first accum)) accum))))
  (lister-loop base))

(注意这显然可以将 named-let 用于内部函数。)

这里有一个函数使用这个函数,两次,向上和​​向下计数。

(define (cud n)
  ;; count up and down
  (lister '(0)
          (λ (x) (+ x 1))
          (λ (x) (= x n))
          (λ (accum)
            (lister accum
                    (λ (x) (- x 1))
                    zero?
                    (λ (a) a)))))

然后:

> (cud 10)
'(0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1 0)

请注意,这是使用 Racket 编写的:我认为这是非常便携的 Scheme,除了我调用了 lambda λ 并且 Scheme 可能没有 first 等等.