pascal-triangle.scm

;; This is free and unencumbered software released into the public domain.

;; Anyone is free to copy, modify, publish, use, compile, sell, or
;; distribute this software, either in source code form or as a compiled
;; binary, for any purpose, commercial or non-commercial, and by any
;; means.

;; In jurisdictions that recognize copyright laws, the author or authors
;; of this software dedicate any and all copyright interest in the
;; software to the public domain. We make this dedication for the benefit
;; of the public at large and to the detriment of our heirs and
;; successors. We intend this dedication to be an overt act of
;; relinquishment in perpetuity of all present and future rights to this
;; software under copyright law.

;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
;; IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
;; OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
;; ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
;; OTHER DEALINGS IN THE SOFTWARE.

;; For more information, please refer to <http://unlicense.org/>


(define previous-row '())

;; Number -> List<Number>
;; Returns the nth row of the pascal triangle
(define (pascal row)
  (letrec ((iter (lambda (index lst)
                   (if (= index (- row 1))
                       (begin
                         (set! previous-row (cons 1 lst))
                         (cons 1 lst))
                       (iter (+ index 1) (cons (left-right row index)
                                               lst))))))
    (begin
      (set! previous-row '())
      (iter 0 '()))))

(define (left-right row index)
  (letrec ((iter (lambda (index lst)
                   (cond
                    ((= index 0) 1)
                    ((= index 1) (+ (car lst) (car (cdr lst))))
                    (else (iter (- index 1) (cdr lst)))))))
    (if (null? previous-row)
        (iter index (pascal (- row 1)))
        (iter index previous-row))))

;; Number Number -> Number
;; Returns the number to the left on the previous pascal triangle row
(define (left row index)
  (letrec ((iter (lambda (index lst)
                   (cond
                    ((= index 0) 0)
                    ((= index 1) (car lst))
                    (else (iter (- index 1) (cdr lst)))))))
    (iter index (pascal (- row 1)))))

;; Number Number -> Number
;; Returns the number to the right on the previous pascal triangle row
(define (right row index)
  (letrec ((iter (lambda (index lst)
                   (cond
                    ((= index 0) 1)
                    ((= index 1) (car (cdr lst)))
                    (else (iter (- index 1) (cdr lst)))))))
    (iter index (pascal (- row 1)))))