;;; utils.ss
;;;   A set of simple utilities for Scheme programming.  Created primarily
;;;   as part of an answer key of CS302 98S.
;;; Author
;;;   Samuel A. Rebelsky
;;; Version
;;;   1.0 of April 1998
;;; Copyright (c) Samuel A. Rebelsky.  All rights reserved.

;;; Select all elements of a list that meet a predicate.
(define (select pred lst)
  (if (null? lst) nil
      (let ((first (car lst))
            (rest (select pred (cdr lst))))
         (if (pred first) 
             (cons first rest)
             rest))))

;;; Compose two functions.
(define (compose f g) (lambda (x) (f (g x))))

;;; The identity function
(define id (lambda (x) x))

;;; Generate a list of "random" numbers in the range -1000 to 1000.
;;; Note that (random x) generates a "random" number from 0 to x-1.
(define (randlist n)
  (if (zero? n) nil
      (cons (- (random 2002) 1000)
            (randlist (- n 1)))))

;;; Compute the first n integers beginning with start.
;;; Precondition: n >= 0
;;; Postcondition: returns (start start+1 start+2 ... start+n-1)
;;; Strategy:
;;;   Base case: if n is 0, return the empty list
;;;   Recursive case: compute the n-1 integers starting with start+1
;;;     (that is, (start+1 start+2 ... start+n-1)), and then prepend
;;;     start.
;;; Note:
;;;   I've used n <= 0 as the base case to handle obnoxious people
;;;   who pass in a negative list length.
(define (nints n start)
  (if (<= n 0)
      nil
      (cons start (nints (- n 1) (+ start 1)))))

;;; Generate a list of n copies of val
;;; precondition: n >= 0
;;; postcondition: returns the list (val val val ... val) such that
;;;   length of the list is n
(define (ncopies n val)
  (if (<= n 0)
      nil
      (cons val (ncopies (- n 1) val))))

;;; Compute all permutations of a list.
;;; Design:
;;;   If the list is empty, then the list of the empty list gives all of its 
;;;     permutations (the same is true for the single-element list, but
;;;     we'll handle it in the recursive case).
;;;   Otherwise, compute all the permutations of the cdr, insert the
;;;     car "everywhere" in each permutation, and join the results
;;;     together.
(define (permutations lst)
  (if (= (length lst) 0)
      (list nil)
      (let ((subperms (permutations (cdr lst)))
            (first (car lst)))
         (apply append
                (map (lambda (sub) 
                       (insert-everywhere first sub)) 
                    subperms)))))

;;; Given an element and a list, create a list of lists such that
;;; each element of the list-of-lists consists of the original
;;; list with the element inserted at some position.
(define (insert-everywhere elt lst)
  (map (lambda (pos) (insert-at pos elt lst))
       (nints (+ 1 (length lst)) 1)))

;;; Given a position, an element, and a list, insert the element
;;; at the appropriate position of the list.  For example,
;;; Precondition: 1 <= pos <= (length lst) + 1
;;;   (insert-at 1 'a '(b c d)) => (a b c d)
;;;   (insert-at 2 'a '(b c d)) => (b a c d)
;;;   (insert-at 3 'a '(b c d)) => (b c a d)
;;;   (insert-at 4 'a '(b c d)) => (b c d a)
;;;   (insert-at 4 'a '(b c d)) => BOOM
(define (insert-at pos elt lst)
  (if (= pos 1)
      (cons elt lst) 
      (cons (car lst) (insert-at (- pos 1) elt (cdr lst)))))