Racket vs. Clojure

I've been asked by several people to explain why I use Clojure for my professional work rather than Racket.

ABOUT RACKET

I have been using Racket (a dialect of Scheme) for several years to teach kids how to program. Although Racket is a great first language, it's definitely not a "toy language". In fact, Racket offers a number of interesting features not found in other languages, making it an attractive option for real-world work. Racket puts into practice state-of-the-art research on macros, continuations, contracts, and interoperation between static and dynamically typed code. The integrated Scribble system makes it easy to provide high-quality documentation and/or write literate programs. It comes with a pleasant, lightweight IDE complete with an integrated debugger and profiler (as well as innovative features such as a specialized macro debugger).

I'm a fan of functional programming and dynamic typing. I know how to write and think in Racket from my many years teaching it, so with all these features, it should be a slam dunk for me to use it professionally, right?

Well, no....

IT'S ALL ABOUT THE DATA STRUCTURES

I have discovered that for me, the #1 factor that determines my programming productivity is the set of data structures that are built-in to the language and are easy to work with. For many years, Python set the standard for me, offering easy syntax to manipulate extensible arrays (called lists in Python), hash tables (called dictionaries in Python), tuples (an immutable collection that can serve as keys in a hash table), and in recent versions of Python, sets (mutable and immutable), heaps, and queues.

Racket, as a dialect of Scheme, places the greatest importance on singly-linked lists. OK, that's a reasonable starting point -- you can do a lot with linked lists. It also offers a vector, which is an old-fashioned non-extensible array that is fixed in length. (Who wants fixed-length arrays as a primary data structure any more? Even C++ STL offers an extensible vector...)

Vectors are mutable, which is both a plus and a minus. On the plus side, it allows you to efficiently write certain classes of algorithms that are hard to write with linked lists. It serves a purpose that is different from linked lists, so there is value to having both in the language. The huge minus is that Racket simply isn't oriented towards working conveniently with mutable vectors. Working with mutable data structures conveniently demands certain kinds of control structures, and certain kinds of syntaxes. You can write vector-based algorithms in Racket, but they look verbose and ugly. Which would you rather read:
a[i]+=3 or (vector-set! a i (+ (vector-ref a i) 3)) ?
But if you can get past the more verbose syntax, there's still the fundamental issue that all the patterns change when you move from using a list to a vector. The way of working with them is so fundamentally different that there is no easy way to change code from using one to another.

Racket goes further than most Scheme implementations in providing built-in data structures. It also offers, for example, hash tables (and recently sets were added). But the interface for interacting with hash tables is a total mess. The literals for expressing hash tables use dotted pairs. If you want to construct hash tables using the for/hash syntax, you need to use "values". If you want to iterate through all the key/value pairs of a hash table, it would be nice if there were an easy way to recursively process the sequence of key/value pairs the way you would process a list. Unfortunately, Racket provides no built-in lazy list/stream, so you'd need to realize the entire list. But even if that's what you'd want to do, Racket doesn't provide a built-in function to give you back the list of keys, values or pairs in a hash table. Instead, you're encouraged to iterate through the pairs using an idiosyncratic version of its for construct, using a specific deconstructing pattern match style to capture the sequence of key/value pairs that is used nowhere else in Racket. (Speaking of for loops, why on earth did they decide to make the parallel for loop the common behavior, and require a longer name (for*) for the more useful nested loop version?) Put simply, using hash tables in Racket is frequently awkward and filled with idiosyncracies that are hard to remember.

There are downloadable libraries that offer an assortment of other data structures, but since these libraries are made by a variety of individuals, and ported from a variety of other Scheme implementations, the interfaces for interacting with those data structures are even more inconsistent than the built-ins, which are already far from ideal.

I'm sure many programmers can live with the awkwardness of the built-in data structures to get the other cool features that Racket offers, but for me, it's a deal breaker.

ENTER CLOJURE

Clojure gets data structures right. There's a good assortment of collection types built in: lists, lazy lists, vectors, hash tables, sets, sorted hash tables, sorted sets, and queues. ALL the built-in data structures are persistent/immutable. That's right, even the *vectors* are persistent. For my work, persistent vectors are a huge asset, and now that I've experienced them in Clojure, I'm frustrated with any language that doesn't offer a similar data structure (and very few do). The consistency of working only with persistent structures is a big deal -- it means you use the exact same patterns and idioms to work with all the structures. Vectors are just as easy to work with as lists. Equality is simplified. Everything can be used as a key in a hash table.

Data structures in Clojure get a little bit of syntactic support. Not a tremendous amount, but every little bit helps. Code is a little easier to read when [1 2 3] stands out as a vector, or {:a 1, :b 2, :c 3} stands out as a hash table. Lookups are a bit more terse than in Racket -- (v 0) instead of (vector-ref v 0). Hash tables are sufficiently lightweight in Clojure that you can use them where you'd use Racket's structs defined with define-struct, and then use one consistent lookup syntax rather than type-specific accessors (e.g., (:age person) rather than (person-age person)). This gets to be more important as you deal with structures within structures, which can quickly get unwieldy in Racket, but is easy enough in Clojure using -> or get-in. Also, by representing structured data in Clojure as a hash table, you can easily create non-destructive updates of your "objects" with certain fields changed. Again, this works just as well with nested data. (Racket structs may offer immutable updates in future versions, but none of the proposals I've seen address the issue of updating nested structured data.) Furthermore, Clojure's associative update function (assoc) can handle multiple updates in one function call -- contrast (assoc h :a 1 :b 2) with (hash-set (hash-set h 'a 1) 'b 2).

Even better, the process for iterating through any of these collections is consistent. All of Clojure's collections can be treated as if they were a list, and you can write algorithms to traverse them using the same pattern of empty?/first/rest that you'd use on a list. This means that all the powerful higher-order functions like map/filter/reduce work just as well on a vector as a list. You can also create a new collection type, and hook into the built-in sequence interface, and all the built-in sequencing functions will automatically work just as well for your collection.

Although the sequencing functions work on any collection, they generally produce lazy lists, which means you can use good old recursion to solve many of the same problems you'd tackle with for/break or while/break in other languages. For example, (first (filter even? coll)) will give you the first even number in your collection (whether a list, vector, set, etc.) and it will do so in a space-efficient manner -- it doesn't need to generate an intermediate list of *all* the even numbers in your collection. Some garbage is generated along the way, but it can be garbage collected immediately and with relatively little overhead. Clojure also makes it easy to "pour" these lazy sequences into the collection of your choice via into. Racket's lack of a built-in lazy list makes it difficult to use map/filter/etc. for general processing of collections. If you use map/filter/etc., you potentially generate a lot of intermediate lists. You can use a stream library, but it was probably designed for other Scheme dialects with a naming scheme for the API that doesn't match Racket's built-in list functions or integrate well with Racket's other sequencing constructs. So often you end up writing the function you need from scratch (e.g., find-first-even-number) rather than composing existing building blocks. In some special cases, you can use one of the new for constructs, like in this case, for/first.

A polymorphic approach is applied through most of Clojure's design. assoc works on vectors, hash tables, sorted hash tables, and any other "associative" collection. And again, you can hook into this with custom collections. This is far easier to remember (and more concise to write) than the proliferation of vector-set, hash-set, etc. you'd find in Racket. It also makes the various collections more interchangeable in Clojure, making it easier to test different alternatives for performance implications with fewer, more localized changes to one's code.

Summary:

• Clojure provides a full complement of (immutable!) data structures you need for everyday programming and a bit of syntactic support for making those manipulations more concise and pleasant.
  
• All of the collections are manipulated by a small number of polymorphic functions that are easy to remember and use.
  
• Traversals over all collections are uniformly accomplished by a sequence abstraction that works like a lazy list, which means that Clojure's higher order sequence functions also apply to all collections.
  

CLOJURE'S NOT PERFECT

The IDEs available for Clojure all have significant drawbacks. You can get work done in them, but any of the IDEs will probably be a disappointment relative to what you're used to from other languages (including Racket).

Debugging is difficult -- every error generates a ridiculously long stack trace that lists 500 Java functions along with (maybe, if you're lucky) the actual Clojure function where things went awry. Many of Clojure's core functions are written with a philosophy that they make no guarantees what they do with bad input. They might error, or they might just return some spurious answer that causes something to blow up far far away from the true origin of the problem.

Clojure inherits numerous limitations and idiosyncracies from Java. No tail-call optimization, no continuations. Methods are not true closures, and can't be passed directly to higher-order functions. Proliferation of nil and null pointer exceptions. Slow numeric performance. Compromises with the way hashing and equality works for certain things to achieve Java compatibility. Slow startup time.

Some people love Clojure specifically because it sits on top of Java and gives them access to their favorite Java libraries. Frankly, I have yet to find a Java library I'd actually want to use. Something about Java seems to turn every library into an insanely complex explosion of classes, and Java programmers mistakenly seem to think that JavaDoc-produced lists of every single class and method constitutes "good documentation". So for me, the Java interop is more of a nuisance than a help.

Clojure has a number of cool new ideas, but many of them are unproven, and only time will tell whether they are truly valuable. Some people get excited about these features, but I feel fairly neutral about them until they are more road-tested. For example:

• Clojure's STM implementation - seems promising, but some reports suggest that under certain contention scenarios, longer transactions never complete because they keep getting preempted by shorter transactions.
  
• agents - if the agent can't keep up with the requests demanded of it, the agent's "mailbox" will eventually exhaust all resources. Perhaps this approach is too brittle for real-world development?
  
• vars - provides thread isolation, but interacts poorly with the whole lazy sequence paradigm that Clojure is built around.
  
• multimethods - Clojure provides a multimethod system that is far simpler than, say CLOS, but it requires you to explicitly choose preferences when there are inheritance conflicts, and early reports suggest that this limits extensibility.
  
• protocols - This is an interesting variation on "interfaces", but it's not clear how easy it will be to compose implementations out of partial, default implementations.
  
• transients - Nice idea for speeding up single-threaded use of persistent data structures. Transients don't respond to all the same interfaces as their persistent counterparts, though, limiting their usefulness. Transients are already being rethought and are likely to be reworked into something new.
  

So it's hard for me to get excited about these aspects of Clojure when it remains to be seen how well these features will hold up under real-world use.

I'm sure that for many programmers, Clojure's drawbacks or unproven ideas would be a deal breaker. We all care about different things. But for me, Clojure's clean coherent design of the API for working with the built-in data structures is so good, that overall, I prefer working in Clojure to working in Racket.

Translating Code from Python and Scheme to Clojure

When coming to Clojure from another language, it takes a while before you start "thinking in Clojure". While ramping up, it helps to understand how to solve a problem in a language you're already familiar with, and then translate the code in some methodical fashion into Clojure.

This article will look at a simple function, remove-first, and look at how you would implement that function in Python and Scheme, and then how to methodically transform those implementations into Clojure. In all of these implementations, I'm going to ignore ways to write the function using shortcuts provided by the standard library, and focus on the implementations using standard iteration and/or recursive techniques. This will provide the clearest example of how the translation process works and can generalize to other types of functions.

Problem Statement: remove-first takes an item and a collection, and returns a new collection which is identical to the original, except the first instance of item (if any) has been removed from the collection. If item is not in the collection, the new collection should be identical to the original (since nothing needs to be removed).

First, let's look at the Python implementation. Python's primary collection data structure is called a "list", but this is a bit of a misnomer, because in most languages, the term "list" is used to describe some sort of linked or doubly-linked list. Python's list is nothing of the sort. Python's list allows fast (destructive) insertion and removal at the back end of the list, and fast lookup by index. In most languages, this would be called an extensible array or extensible vector (in Java, it's called an ArrayList).

The problem statement for remove-first calls for returning a new copy of the collection with the first instance of item removed. Is this really idiomatic for Python? It is certainly possible to write remove-first as a destructive function that actually modifies the original collection by removing the first instance of item. In fact, such a destructive method is built-in to the list class (list.remove(item)). But removing from the middle of a Python list is not an especially efficient operation, and Python has a culture of slices, comprehensions, and many other list operations that return fresh copies. So yes, I think it is reasonable to talk about how to write a non-destructive removal in Python.

Now remember, for the purposes of this article, we're trying to look at how to translate iterative algorithms, so it's a cheat to use built-in constructs that work around this.

So this doesn't count, because it uses the built-in destructive removal:

def removeFirst(itemToRemove, coll):
    newColl = coll[:]  # copies the collection
    try:
        newColl.remove(itemToRemove)  # throws an error if item is not present
        return newColl
    except:
        return newColl

Nor does this, although this is arguably the most idiomatic Python version of removeFirst, because it uses the built in index function which handles the iteration behind the scenes:

def removeFirst(itemToRemove, coll):
    try:
        i = coll.index(itemToRemove)
        return coll[:i] + coll[i+1:]
    except:
        return coll[:]

In Python, the standard practice for writing such a function in an iterative fashion is to create a new list, and then iterate over the items of the initial list, adding the appropriate ones to the new list, and then returning the new list at the end. This pattern of setting up an accumulator, and then using a for loop to add things to the accumulator, is a common one in Python. For this particular problem, in English you might say, "I'm going to go through the items, adding them one at a time to the new collection. If I hit one that matches the item to remove, I skip it and add the rest of the items directly to the new collection."

But is it better to iterate directly over the items, or is it better to iterate over the indices and access the items through the indices? When possible, it's preferred to iterate directly over the items, but unfortunately, Python has no good way to express "the rest of the items" once you hit an item that matches the one to remove. You can only get at "the rest of the items" if you know the index in order to take a slice from there to the end. So iterating through items versus iterating through indices yield slightly different strategies for this particular problem.

If you really wanted to iterate directly over the items, you'd probably need to use a flag to track whether you've already removed the first occurrence of the item:

def removeFirst(itemToRemove, coll):
    newCollection = []
    alreadyRemovedItem = False
    for item in coll:
        if (alreadyRemovedItem):
            # We've already removed the first instance of item
            # so we're just in "copy" mode
            newCollection.append(item)
        else:
            # We need to test whether the item matches itemToRemove
            if (item == itemToRemove):
                # don't copy this item over, but set alreadyRemovedItem flag
                alreadyRemovedItem = True
            else:
                newCollection.append(item)
    return newCollection

which could be refactored by reorganizing the if/else branches into the shorter:

def removeFirst(itemToRemove, coll):
    newCollection = []
    alreadyRemovedItem = False
    for item in coll:
        if (alreadyRemovedItem or item != itemToRemove):
            newCollection.append(item)
        else:
            alreadyRemovedItem = True
    return newCollection

Alternatively, if you iterate through the indices, then you can use a list slice to capture the notion of "the rest of the list".

def removeFirst(itemToRemove, coll):
    newCollection = []
    for index in range(len(coll)):
        item = coll[index]
        if (item == itemToRemove):
            # skip this item and rather than add the rest of the items
            # one by one, we can just add the rest to newCollection
            # all in one step
            newCollection.extend(coll[index+1:])
            # We're done now
            return newCollection
        else:
            newCollection.append(item)
    return newCollection

Admittedly, this last version is a bit of a cheat by my own definition of avoiding built-ins that bypass iteration, since that's effectively what extend is doing. But I don't mind it as much since we at least had to iterate until we found the item to remove, so it sufficiently demonstrates iteration techniques.

I think either of these versions (iterating through items or iterating through indices) are good examples of common patterns that occur in Python, and are worth knowing how to translate to Clojure.

Let's begin by translating the version that iterates through items.

Clojure has a built-in datastructure that corresponds very closely to Python's lists. In Clojure, it is called a vector. Like Python lists, it allows fast access to an element by index, and allows fast insertion and removal at the back end of the collection. The main difference is that a Clojure vector, like all built-in Clojure data structures, is persistent and immutable. That means that any operation on a Clojure vector returns some sort of fresh copy -- the original remains unchanged. At first, this might sound wildly inefficient, but altered Clojure vectors can share a lot of internal structure with their source, precisely because of this guarantee of immutability, so it's actually pretty fast.

But this requires a different way of thinking about algorithms. We can't just create a new empty vector and destructively add things to it and return it, as we do with Python. (Well, of course, since Clojure sits on top of Java, you can easily use Clojure to create a Java ArrayList and use exactly the same pattern as Python, but you're here to learn "the Clojure way", right?)

Perhaps the most naive way to translate the code is to simulate a mutable vector in Clojure by wrapping a vector in some sort of mutable reference type (e.g., an atom). You'd need to do the same thing to the already-removed-flag. The @ sign is then used to look at the current contents of the mutable reference. This is very bad form for this kind of algorithm, and not particularly efficient, but it works, and has an almost exact parallel to the Python code:

; This is bad style, don't do this!!!
(defn remove-first [item-to-remove coll]
  (let [new-collection (atom []),
        already-removed-item (atom false)]
    ; doseq is just like Python's for loop
    (doseq [item coll]
      (if (or @already-removed-item (not= item item-to-remove))
        (swap! new-collection conj item)  ; just like append
        (reset! already-removed-item true)))  ; sets flag to true
    @new-collection))

The better way to tackle this translation is to closely analyze the original, and identify any accumulator or variable that changes as you loop, and then thread those through the loop. I'll explain shortly what I mean by threading values through the loop, but there's one other issue that needs to be considered. You've already seen Clojure's doseq construct in action as a counterpart to Python's for loop, but it's only relevant for triggering destructive or side-effect-filled actions -- it's not the right tool for the job when trying to build up a persistent Clojure vector. Clojure has a for construct but it's not a general looping construct, rather, it corresponds to Python's list and generator comprehensions.

Clojure really only has one general-purpose looping construct, known as loop/recur. In time, you'll be able to see how to go directly from a Python-style for loop to a Clojure loop/recur, but initially, it's far easier to see how to go from a Python-style while loop to a Clojure loop/recur. So as an intermediary step in translating our Python code to Clojure, let's begin by rewriting the Python for loop into a while loop. Here is one way to do that rewrite:

def removeFirst(itemToRemove, coll):
    newCollection = []
    alreadyRemovedItem = False
    collIterator = iter(coll)
    while(True):
        try:
            item = collIterator.next()
            if (alreadyRemovedItem or item != itemToRemove):
                newCollection.append(item)
            else:
                alreadyRemovedItem = True
        except:
            # next() triggers an error when the end of the list is reached
            # so we're done
            return newCollection

The advantage of rewriting as a while loop is that it helps us identify a couple of very important things. First, it let's us see the exit condition. The exit condition occurs when you've reached the end of the list, at which point newCollection holds the answer and can be returned. Second, it makes it a tad easier to analyze which things from outside the loop are being updated while inside the loop. The assignment to item is just creating a local variable within a given iteration of the loop, so that's not really the kind of thing we're looking for. But we should take note that newCollection, initialized outside the loop, is destructively extended within the loop, and the flag alreadyRemovedItem can also change from within the loop. Furthermore, it's now quite obvious that something needs to track the iteration through coll; this is done by collIterator which is updated each time through the while loop by the call to its next() method. So collIterator, newCollection and alreadyRemovedItem are the things we're going to need to thread through our Clojure loop/recur structure.

Once these things have been identified, we're ready to tackle the Clojure translation. Iterators in Clojure work quite differently than in Python. Almost any collection in Clojure can be converted to a "seq" (short for sequence) by calling a function called, you guessed it, seq. For the moment, go ahead and think of it as an iterator. The iterator will be nil when the collection is exhausted. You call first to get the item the iterator is pointing at, and next to (non-destructively) advance the iterator.

(defn remove-first [item-to-remove coll]
; Start a loop, identifying and initializing the things that will change in the loop
  (loop [coll-iterator (seq coll),
         new-collection [],
         already-removed-item false]
    ; coll-iterator is nil when you're at the end of the collection.
    ; Clojure treats all non-nil, non-false values as true.
    (if coll-iterator
      ; We haven't reached the end of the collection
      (let [item (first coll-iterator)]
        (if (or already-removed-item (not= item item-to-remove))
          ; update new-collection and advance coll-iterator.  We do this using recur
          ; to jump back to loop, rebinding coll-iterator to (next coll-iterator),
          ; new-collection to (conj new-collection item), and
          ; leaving already-removed-item unchanged
          (recur (next coll-iterator) (conj new-collection item) already-removed-item)

          ; else, advance iterator, leave new-collection unchanged,
          ; and set already-removed-item to true
          (recur (next coll-iterator) new-collection true)))
      ; We have reached the end of collection, so new-collection is the answer
      new-collection)))

Note that nothing destructive is happening here; it's all mutation-free. (next coll-iterator) actually returns a new iterator object, (conj new-collection item) actually creates a new vector with item appended to the end. Clojure makes these operations cheap, and recur lets us pass the new objects back to the top of the loop and reuse the names given in the loop construct.

Now I'll let you in on a little secret. Rather than thinking of (seq coll) as returning an iterator, you can think of it as returning a linked-list-style view of the collection. Better yet, virtually all sequential-style functions in Clojure call seq implicitly, so that means, for all practical purposes, you can pretend that any Clojure collection is a linked list. Lists are able to answer three important questions: are you empty, what is your first element, and what are the rest of your elements? These correspond to empty?, first, and rest in Clojure. So just by thinking of our collection as a list, we have an extremely powerful way to iterate through it using recursion. We can rewrite the above Clojure code with this in mind:

(defn remove-first [item-to-remove coll]
  (loop [coll coll,  ; no explicit call to seq is needed, 
                     ; we can reuse the name coll for clarity
         new-collection [],
         already-removed-item false]
    (if (empty? coll)
      new-collection
      (let [item (first coll)]
        (if (or already-removed-item (not= item item-to-remove))
          (recur (rest coll) (conj new-collection item) already-removed-item)
          (recur (rest coll) new-collection true))))))

This concludes our mechanical translation of the iterate-through-items Python version. It may look odd to you if you've never seen this kind of looping before. Some programmers actively prefer this style of looping because it makes it abundantly clear which things are changing each time through the loop, and how, and precisely what the exit condition is and what value you exit with. In other words, it's arguably more explicit and easier to analyze a loop/recur structure than a for loop that's mucking around with mutable objects located outside the loop. There's truth to this, but I also sympathize with those who find loop/recur to be less readable. For loops nest well and allow for some pretty intricate control flow with judicious use of continue and break; complex nested for loops like that can be hard to analyze, but the equivalent loop/recur can be even worse. Nevertheless, loop/recur is the way general looping is done in Clojure, so for now, we'll just accept it along with its advantages and disadvantages and move on.

Now it's time to look at the iterate-through-indices version. Again, we begin by converting the Python for loop to a Python while loop.

def removeFirst(itemToRemove, coll):
  newCollection = []
  index = 0
  while (True):
    if (index == len(coll)):
      # We're done now
      return newCollection
    else:
      item = coll[index]
      if (item == itemToRemove):
        # Add the rest of the elements all at once and we're done.
        newCollection.extend(coll[index+1:])
        return newCollection
      else:
        newCollection.append(item)
        index += 1

This time, we see the things that change while looping are newCollection and index. The above code can now be mechanically translated to:

(defn remove-first [item-to-remove coll]
  (loop [new-collection [],
         index 0]
    (if (= index (count coll))
      new-collection
      (let [item (coll index)]
        (if (= item item-to-remove)
          ; into is like Python's extend, subvec is like Python's slice
          (into new-collection (subvec coll (inc index)))
          (recur (conj new-collection item) (inc index)))))))

Notice how in Clojure code, we don't need to explicitly call return, return is implied.

In Python we had two basic strategies, iterate by items and iterate by indices, and both had an analog in Clojure. But remember, the reason why we needed two strategies in Python was that there was no way to capture the "add the rest of the items to the collection" concept in the version that iterated through items, so we were forced to choose between iterating through items and use a flag to go into "copy items until reaching the end of the list"-mode, or use indices so we could take a slice.

But Clojure offers us a way to fuse these two strategies together, because its basic iteration mechanism (the linked-list-style view) DOES make it extremely easy to work with the notion of "the rest of the items" without any index manipulation or slicing.

Fusing the two Python strategies in Clojure, we get this:

(defn remove-first [item-to-remove coll]
  (loop [coll coll,
         new-collection []]
    (if (empty? coll)
      new-collection
      (let [item (first coll)]
        (if (= item item-to-remove)
          ; Extend new-collection with rest of coll and return in one step
          (into new-collection (rest coll))
          (recur (rest coll) (conj new-collection item)))))))

There's one downside to this implementation, namely, we're paying a performance penalty for gradually building up this vector by extending an immutable object one item at a time, when we don't care about and will never use the intervening steps between the empty vector and the final new collection. It's not a huge penalty, but it's real. Fortunately, Clojure offers a "recipe" to convert such functions. Upon entering the loop, you initialize the thing you're building to a transient (somewhat more mutable) vector. Then you append to it using conj! rather than conj, and finally you convert it back to immutable at the end using persistent!. The result looks like this:

(defn remove-first [item-to-remove coll]
  (loop [coll coll,
         new-collection (transient [])]
    (if (empty? coll)
      (persistent! new-collection)
      (let [item (first coll)]
        (if (= item item-to-remove)
          (into (persistent! new-collection) (rest coll))
          (recur (rest coll) (conj! new-collection item)))))))

Note that the overall shape of the code has not changed, we've just added a few annotations that improve performance. But remember this step is optional, the previous version is perfectly fine for most purposes.

Although we were mainly trying to mimic the Python code, it's worth noting that Clojure code is highly polymorphic. Whereas the Python code only takes Python lists (and maybe some of the above versions would take strings), this Clojure algorithm will work on any collection (arrays, lists, lazy lists, vectors, sets, maps, strings, etc.) because all have that wonderful property of being viewable as lists. However, the returned collection is specifically a vector, no matter the input, so depending on the context, the polymorphism of the input may have limited utility.

Now it's time to move on to Scheme. We'll look at a standard Scheme implementation of remove-first, and see how to translate that into Clojure. These examples have been tested in the Racket dialect of Scheme.

In Scheme, the most basic, native collection type is the linked list. The three fundamental operations on a Scheme list are empty?, first, and rest (sound familiar?) and you can also non-destructively add an item to the front of the list with (cons item list). Adding to the back of a list is a slow operation, so the strategy of building up a new collection by adding to the back is not a particularly desirable one in Scheme. Instead, the strategy is to use recursion, essentially allowing the call stack to build the sequence of items that need to be added, eventually, to the front of an empty list. It sounds confusing, but once you have your head wrapped around recursion, it all makes perfect sense (and if you don't understand recursion, head directly to htdp.org).

In any case, a typical Scheme implementation looks like this:

(define (remove-first item-to-remove coll)
 (if (empty? coll)
   empty
   (let ([item (first coll)])
     (if (equal? item item-to-remove)
         (rest coll)
         (cons (first coll) (remove-first item-to-remove (rest coll)))))))

Clojure also has a list collection, and the translation is about as straightforward as it could possibly be, requiring only a couple syntactic changes:

(defn remove-first [item-to-remove coll]
  (if (empty? coll)
    ()  ; literal name for empty list
    (let [item (first coll)]
      (if (= item item-to-remove)
        (rest coll)
        (cons (first coll) (remove-first item-to-remove (rest coll)))))))

But there's a catch. Because Scheme relies on this kind of programming style, Scheme implementations are designed in such a way so that the stack has rather huge limits, basically being limited by your overall memory rather than some specific call-stack memory limitation. In other words, if the resulting list is small enough to fit in your computer's memory, than in all likelihood the call stack necessary to process it with recursion will fit as well. So call stack limitations are mostly a non-issue in Scheme.

However, Clojure is limited to Java stack limits, so this style of writing will definitely place a limit on the size of collection that can be processed by this function. Fortunately, there is a rather simple solution. Clojure offers seamless interoperation between lazy lists and regular lists. Lazy lists solve the stack problem by avoiding the recursive step, returning immediately with a list-like object that can be probed on-demand for first and rest information by the consumer. Further elements will be computed as needed, and will be driven by the consumer's looping process.

This is accomplished by wrapping a call to lazy-seq around some part of the computation. There are at least three reasonable places to place the call to lazy-seq. You can put lazy-seq around the full body of the function.

(defn remove-first [item-to-remove coll]
  (lazy-seq (if (empty? coll)
              ()
              (let [item (first coll)]
                (if (= item item-to-remove)
                  (rest coll)
                  (cons (first coll) (remove-first item-to-remove (rest coll))))))))

You can place it around the cons.

(defn remove-first [item-to-remove coll]
  (if (empty? coll)
    ()
    (let [item (first coll)]
      (if (= item item-to-remove)
        (rest coll)
        (lazy-seq (cons (first coll) (remove-first item-to-remove (rest coll))))))))

You can place it around the recursive call to remove-first.

(defn remove-first [item-to-remove coll]
  (if (empty? coll)
    ()  ; literal name for empty list
    (let [item (first coll)]
      (if (= item item-to-remove)
        (rest coll)
        (cons (first coll) (lazy-seq (remove-first item-to-remove (rest coll))))))))

Each choice results in slightly different laziness behavior, i.e., when various elements are computed, but the overall semantics of the sequence remains the same and stack overflows will be avoided. Placing the lazy-seq around the recursive function call will cause remove-first to compute the first element right away, and delay the rest. Placing the lazy-seq around the full body will prevent any computation until it is asked for by a consumer. Placing the lazy-seq around the cons results in in immediate behavior for the nil and removable-item-at-front-of-list case, and delayed behavior otherwise.

All are acceptable choices, but preferences vary. Probably placing lazy-seq around the full body is the most common style you'll see in Clojure, although I tend to place it where the laziness is actually required (like around the recursive call, or around the cons).

Converting remove-first so that it returns lazy lists definitely generates some additional overhead than a strict list. However, this overhead pays for itself if you ever end up using just part of the list, because no time is spent generating the parts you don't need. There's something very refreshing, freeing, and efficient about writing functions that find the first object with some particular property by using the strategy of taking the first item from the list of ALL objects with that particular property, knowing full well that the complete list will never be generated. Lazy lists can be used as an alternative to many traditional control structures (the above example of taking the first item from a lazy-list of objects satisfying a given description is an elegant substitute for something that would require a for-loop-break iteration in a traditional language). Generally speaking, lazy lists are more useful than strict lists, and for that reason, lazy lists are the norm in Clojure rather than the exception.

Since Clojure offers both vectors (similar to Python's lists) and lists (similar to Scheme's lists), we have seen that it is possible to convert both algorithmic styles into Clojure. With Python, the main thing that needed to be dealt with was adapting the algorithm to build an immutable, rather than a mutable, vector. This was further complicated by the fact that Clojure's general loop/recur looping construct doesn't exactly match up with Python's for loop construct and a conversion process is needed. But the final result captured the spirit of the Python code well. Coming from Scheme was easier, and the only real modification that was necessary was to output a lazy list rather than a strict list. Both versions can take any collection as an input, but one produces vectors and the other produces lazy lists. Both implementations are legitimate choices, depending on the desired usage.