Recent Content

#18: Multi-Function Application

posted on 2018-01-30

Given a list of $n$ unary functions $L:=(f_1, f_2,\ldots,f_n)$, write a function (appList L x) that returns $(f_1(x), f_2(x), \ldots, f_n(x))$. For example:

(appList (list sin cos tan) 3.14)
;; ==> (0.00159265291648683 -0.99999873172754 -0.00159265493640722)

#17: Square and Diagonal Matrices

posted on 2018-01-30

Write functions square-matrix? and diagonal-matrix? to determine if a matrix is square (same number of rows and columns), or if a matrix is diagonal (the only non-zero entries are those on the diagonal).

#16: Matrix Transpose

posted on 2018-01-30

Suppose a matrix is represented as a list of equally sized lists representing the rows. Write a function to transpose a matrix in this representation. Transposition is a process where every row becomes a column, and every column becomes a row.

#15: Simple Combinators

posted on 2018-01-30

Part 1

Implement the following combinators, high-order functions that are usually composed together. (Here we specify the type signatures in Haskell-like notation.)

  1. (constantly x), a function which takes an argument x and produces a unary function which always returns x.
  2. Using constantly, implement yes which always returns a true value, and no which always returns a false value.
  3. (complement f), a function which takes a function returning a Boolean, and produces another function which does the same but with the Boolean inverted.
  4. (conjunction f g) which returns a function which takes an argument and returns true iff both f and g are satisfied by x.
  5. (disjunction f g) which is like conjunction but checks iff either f or g are satisfied by the input.

One should note the similarity between these functions and some of the basic unary and binary Boolean predicates.

Part 2

Write out the type signature of each of the above functions.

Part 3

Implement Fizz Buzz using these combinators.

#14: Shunting Yard

posted on 2018-01-30

Read about and implement the shunting-yard algorithm.

#13: Simple `destructuring-bind`

posted on 2018-01-30

In Common Lisp, there's a macro called destructuring-bind which allows you to "take apart" a list and bind the parts to variables. It's a primitive form of pattern matching for lists.

Implement a basic version that allows the following to work:

(define lst '(1 2 3))
(define cns '(1 . 2))

(destructuring-bind (a b c) lst
  (+ a b c))                    ; ==> 6

(destructuring-bind (a . b) cns
  (+ a b))                      ; ==> 3

(destructuring-bind (a . b) lst
  (map (lambda (x) (+ a x)) b)) ; ==> (3 4)

#12: Intraword Scramble

posted on 2018-01-30

Wirte a fincuton wcihh teaks a snetnece as a srintg and sberalmcs the mlddie lretets of each word, keiepng the first and last ltretes of each word itnact. You can asmuse "ieadl" ipunt: no pntitcoauun, no nbuemrs, etc.

#11: C-style Loops

posted on 2018-01-30

Part 1

Implement a C-style for-loop without using another explicit imperative looping construct.

(for ((<var> <init>) <condition> <post-loop-thing>)

For example:

 (for ((i 0) (< i 10) (set! i (+ 1 i)))
  (display i)

which would print 0 through 9. Unlike C, i's scope is limited.

Part 2

Now extend for so you can do (for (<var> in <list>) …) to iterate over lists. This is (almost) equivalent to Common Lisp's dolist macro.

Part 3

Generalize the results of Part 2 so that the user can "program" the for-loop with iteration semantics of any data type. As an example of what this may mean, though you might do it differently, is to have a table of predicates, like so in Common Lisp:

(defvar *for-loop-extensions*
         ; predicate    ???
        '((listp        ???)
          (vectorp      ???)

;; for-loop should now work with at least
;; lists and vectors.
(for (i in #(1 2 3))
  (print i))

I've put ??? so as to not spoil what they could be.

#10: Using Degrees

posted on 2018-01-30

For better or for worse, some disciplines use degrees as a measure of angle. Write a macro with-degrees which causes the trigonometric functions sin, cos, and tan to use degrees and not radians within the lexical scope of with-degrees. For example,

  (+ (sin 30) (sin 90)))

should return 1.5.

Note: This is much less straightforward in Common Lisp than it is in Scheme due to Common Lisp's packaging rules.

#9: Cleaner `define*`

posted on 2018-01-30

In challenge #8, you wrote a define macro called define*. However, this can be awkward and even inefficient when we have a cond or a case. Consider:

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

Each time we compute a yet-uncomputed Fibonacci number, we have to check if it's 0 first, then 1, then we can proceed to compute.

In this challenge, we want to be allowed to define constant cases which add to the memoization table immediately. Let's call this definition procedure def. The syntax looks as follows:

(def fib
  (0) => 0
  (1) => 1
  (n) => (+ (fib (- n 1))
            (fib (- n 2))))

This will create a function fib which will have the results of (fib 0) and (fib 1) memoized, and allow for the general case. When we do call the general case for an unmemoized function, we no longer have to crawl the cond, because there is none. So we save comparisons each time it's called.

For multi-argument functions, it would be illegal to have clauses like (4 b c) => .... You can safely assume the last case will be the variable case.

This blog covers math, challenge

View content from 2018-01, 2018-02, 2018-03

Unless otherwise credited all material copyright © 2010–2018 by Robert Smith