#8: Memoized `define`

posted on 2018-01-30

Write a macro define* that looks like define but memoizes results, i.e., it'll save the value of the result so next time around, it just looks up the result.

Follow Up: Discuss some of the subtle decisions one has to make in writing define*.

Extra Credit: Do it without namespace pollution (except for the defined function name of course).

#7: Lisp's `setq`

posted on 2018-01-30

In Common Lisp, setq takes any number of argument pairs. For example,

(setq x 1 y 2 z 3)

will set the value of x to 1, y to 2, and z to 3. Implement this in Scheme.

Follow Up: Discuss which behavior was not defined in the above example, and what choices you made to define them.

#6: Bogosort

posted on 2018-01-30

Implement Bogosort. Bogosort is a sorting algorithm defined as so:

INPUT x: a finite sequence of numbers
OUTPUT: the input sequence in ascending order

Step 1. If x is in ascending order, return x.
Step 2. Shuffle the elements of x uniformly randomly. Go to Step 1.

#5: Standard ML's `ref`

posted on 2018-01-30

In Standard ML and similar languages, one is not able to mutate the bindings to values. It is not possible to do something like x = 1 followed by x = 2. Instead, a special purpose cell is allocated, called a ref, whose contents can be modified. In Standard ML, ref is defined by the following signature:

signature REF =
  sig
    type 'a ref

    (* create a ref containing a value*)
    val ref : 'a -> 'a ref

    (* retrieve the contents of this value *)
    val op ! : 'a ref -> 'a

    (* Change the value of the ref *)
    val op := : 'a ref * 'a -> unit
  end

Implement ref. In Scheme, the behavior of ref might be like so:

; create a
(define a (ref 9))
(set-ref! a 8)
(deref a) ; ==> 8

#4: Partitions of an Integer

posted on 2018-01-30

Similar in spirit to the counting change problem from SICP, write a function to compute the partitions of an integer. A partition of a non-negative integer $N$ is a non-increasing sequence of positive integers less than or equal to $N$ that they sum to $N$.

All of the partitions of $4$ are $(4)$, $(3, 1)$, $(2, 2)$, $(2, 1, 1)$, and $(1, 1, 1, 1)$.

#3: Friendlier `letrec`

posted on 2018-01-30

Write with-definitions, a version of letrec which allows one to use define-like syntax in Scheme. For instance, I should be able to do:

(define (example x)
  (with-definitions
   ((define (is-even? x) (zero? (remainder x 2)))
    (define rofl "rolling on the floor laughing"))
   (if (is-even? x)
       (display rofl)
       (display ":("))))

It's a little baroque and definitely not "minimal", but neither is being able to do

(define (f x) ...)

when you could also do (define f (lambda (x) ...))

#2: Conditional Mutation

posted on 2018-01-30

Create a procedure called set-if! such that

(set-if! <predicate> <symbol> <value>)

means that <symbol> is not set to <value> if <predicate> is not true.

Follow up questions:

Why can't this be a function in most languages?
What are the subtlties of the semantics of this? What behavior is not defined by the above?

#1: Delayed Evaluation

posted on 2018-01-30

Define a macro thunk which will wrap the body of the macro inside a lambda. That is, define

(thunk
  <body>)

so that we get

(lambda () <body>)

This can act as a primitive for delaying evaluation.

Update: See Challenge #32 for an extension of this challenge.

Introducing Watrophy

posted on 2018-01-29

For almost as long as I can remember, I've frequented sprawling online communities of programmers in order to learn more about the craft of writing code. This has given me the opportunity to meet many folks of many backgrounds, with the common thread that we (usually!) like to create software.

I've been particularly grateful for the fact that some of these individuals found me to be helpful in their pursuit to learn programming languages and the techniques they often come with. Around 10 years ago, I frequently mentored on Scheme and Standard ML, focusing on techniques from functional programming and meta-programming. Almost always, the techniques are more valuable than the languages themselves, since they pay dividends. One way to learn is through practice, and so I frequently posed small exercises to teach a concept.

With the help of @qu1j0t3, I've managed to unearth some of the exercises I wrote dating back almost a decade, which have been remastered and posted here.

This website is a log of challenges—old and new—to strengthen your programming muscle. If you're a programmer by occupation, maybe you say wat a lot at your ordinary stock of languages, projects, frameworks, and tools. Or maybe you're just bored. If you're a hobbyist, maybe you don't find a lot of practical material on these subjects without getting lost in the depths of academia. Whatever the reason you program, I think these exercises may be sufficiently interesting, short, and insightful.

These exercises differ from a few other kinds of exercises.

They're a little more difficult than the average set of "koans".
They're a little more biased toward statically and dynamically typed functional programming.
They're not as mathematically oriented as Project Euler.
They're usually not optimized for competitive programming, like TopCoder or HackerRank.
They have nothing to do with code golf, unless you want them to.

While there is currently no implemented ranking system, it wouldn't matter anyway, since good solutions typically characterized by their aesthetic and technique, not run time or memory consumption.

I hope to update this at least once a week. Feel free to subscribe to any of the following feeds:

RSS and Atom feeds for any and all posts.
RSS and Atom feeds of challenges only.

This blog covers math, challenge

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

Recent Content