ファレイ数列

30分プログラム、その720。mixiの課題コミュニティからのインスパイアです。
趣旨としては、wikipedia:ファレイ数列を生成せよ、という問題です。Wikipediaのページの中盤に書いてある中間数を利用します。

使い方

gosh> (map frac->string (farey 1))
("0/1" "1/1")
gosh> (map frac->string (farey 2))
("0/1" "1/2" "1/1")
gosh> (map frac->string (farey 3))
("0/1" "1/3" "1/2" "2/3" "1/1")
gosh> (map frac->string (farey 4))
("0/1" "1/4" "1/3" "1/2" "2/3" "3/4" "1/1")

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; farey.scm -
;;
;; Copyright(C) 2010 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2010/01/13 20:59:06
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;
(use srfi-1)
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (modulo a b))))

(define (make-frac a b)
  (let1 d (gcd a b)
	(cons (/ a d)
	      (/ b d))))
(define (num x)
  (car x))
(define (denom x)
  (cdr x))

(define (frac->string n)
  (string-append (number->string (car n))
		 "/"
		 (number->string (cdr n))))

(define (add-frac x y)
  (make-frac (+ (num x) (num y))
	     (+ (denom x) (denom y))))

(define (farey n)
  (if (= n 1)
      (list (make-frac 0 1) (make-frac 1 1))
      (let1 xs (farey (- n 1))
	    (filter (lambda (x) (<= (denom x) n))
		    (append
		     (append-map (lambda (x y)
				   (list x
					 (add-frac x y)))
				 xs (cdr xs))
		     (list (make-frac 1 1)))))))