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.
fibonacci methods are implemented elegantly in functional programming languages.
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))) ) )
(define (fibonacci n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))) ) )
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))) ) )
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))) ) )
nth element of a List
This method returns the nth 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)) ) )
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)) ) )