Basic Programs Written in Scheme

I’ve recently been programming in Scheme which is a functional programming language. Scheme is a very minimalist language and doesn’t come with much functionality built in, but nonetheless is very easy to extend. You can start programming in Scheme yourself by installing Kawa, an open-source implementation of Scheme written in Java.

This post contains some useful functions, such as determining the size of a list, reversing a list, and insertion sort, all written in Scheme. As trivial as some of these programs are, they are not available in Scheme by default.

Factorial

Naturally, factorial and fibonacci methods are implemented elegantly in functional programming languages.

(define (factorial n)
	(if (= n 1)
		1
		(* n (factorial (- n 1)))
	)
)

Fibonacci

(define (fibonacci n)
	(cond
		((= n 0) 0)
		((= n 1) 1)
		(else (+ (fibonacci (- n 1)) (fibonacci (- n 2))))
	)
)

Factorial (Interactive)

Although, scheme has a very simple I/O API, it gets the job done for simple programs. Here is an interactive version of the factorial problem, in which the program asks the user for a number as an input, and outputs the factorial of that number.

(define (factorial-interactive)
	(display "Please enter an integer: ")
	(let ((n (read)))
	   (display "The factorial of ")
	   (display n)
	   (display " is ")
	   (display (factorial n))
	   (newline)
	)
)

Size of a List

Determining the size of a list (the number of items in a list) can be written in several different (and clever) ways in Scheme. Using map-reduce, you can map a 1 to each element of the list and then reduce the list by summing the 1’s to determine the size of the list.

(define (size x)
	(if (null? x)
		0
		(+ 1 (size (cdr x)))
	)
)

; Size of a list with map-reduce.
(define size(lambda (list)
	(reduce + 0
		(map (lambda (x) 1) list)))
)

Summing a List

This function takes a list as a parameter and sums the values of the list. If the input criteria does not guarantee that the list will contain all numbers, use number? as a check before adding the value to the sum. Alternatively (and less optimally), you can use the numberlist method defined below and run it on the input to make sure the list contains only numbers.

(define (sum x)
	(if (null? x)
		0
		(+ (car x) (sum (cdr x)))
	)
)

Number List?

This method checks whether the list contains only numbers.

(define (numberlist l)
	(cond
		((null? l) #t)
		((not(number? (car l))) #f)
		(else
			(numberlist (cdr l))
		)
	)
)

Member of a List

(define (member x l)
	(cond
		((null? l) #f)
		((equal? x (car l)) #t)
		(else
			(member x (cdr l))
		)
	)
)

Reverse a List

(define (reverse l)
	(if (null? l)
		()
		(append (reverse (cdr l)) (list (car l)))
	)
)

n^th element of a List

This method returns the n^th element of the supplied list, assuming the list is non-empty and n >= 0.

(define (nth lst n)
	(if (= n 0)
	    (car lst)
	    (nth (cdr lst) (- n 1))
	)
)

Compose

Scheme supports higher-order functions, meaning functions can accept other functions as parameters.
This method takes parameters that are functions, and applies the output of the second function to the first function.
It acts like so: \(f(g(x))\)

(define (compose f g)
	(lamda (x)
		(f (g x))
	)
)