;; Pythagorean triples using combinations. (1.01)

(use-modules (srfi srfi-1))

;; Utility.

(define (pair-map proc sequence)
  (pair-fold-right (lambda (item init)
                     (cons (proc item) init))
                   '() sequence))

(define (pair-append-map proc sequence)
  (apply append (pair-map proc sequence)))

;; Combinations.

(define (combinations sequence k)
  (if (zero? k)
      (list '())
      (pair-append-map (lambda (rest)
                         (map (lambda (comb)
                                (cons (car rest) comb))
                              (combinations (cdr rest) (- k 1))))
                       sequence)))

;; Pythagorean triples.

(define (primitive-pythagorean-triple? x y z)
  (and (< x y z)
       (= (+ (* x x) (* y y)) (* z z))
       (= (gcd x y z) 1)))

(define (pythagorean-triples n)
  (sort
    (filter-map
      (lambda (triple)
        (apply (lambda (x y z)
                 (if (primitive-pythagorean-triple? x y z)
                     triple
                     #f))
               triple))
     (combinations (iota n 1) 3))
   (lambda (x y) (< (third x) (third y)))))

;; Show.

(define n 5)
(define a (iota n 1))
(for-each (lambda (k)
            (format #t "~A~%" (combinations a k)))
          (iota n 1))
(newline)
(format #t "~A~%" (pythagorean-triples 53))