Splitting a list in Racket I am working my way into learning a bit of Scheme (actually, Racket) with the help of a few practical problems to solve. In this case, I want to split a flat list of symbols at a certain delimiter symbol, discarding it and returning the list of split chunks.

#! /usr/bin/racket

#lang racket

(define (split lst del)
    (define (split-one lst)
        (if (or (empty? lst) (equal? (car lst) del))
            '()
            (cons (car lst) (split-one (cdr lst)))))
    (let loop ((next lst))
        (if (empty? next)
            '()
            (let ((cur (split-one next)))
                (cons
                    cur
                    (loop (let ((nextpos (+ 1 (length cur))))
                        (if (&lt; nextpos (length next))
                            (list-tail next nextpos)
                            '()))))))))

(split '(a b c x d x e x f) 'x) ; '((a b c) (d) (e) (f))
(split '(0 1 2 0 2 0 3 0) 0) ; '(() (1 2) (2) (3))


It does work, but I feel it's not the best way to accomplish the task, for a couple of reasons:


The (loop (let (... part seems a bit clunky, maybe even unnecessary.
The (list-tail ... clause entails rescanning the list for nextpos elements, which obviously is not optimal. In Python, I would have split-one return the current chunk and a reference to the head of the following, i.e. the cdr of the last element considered, and keep iterating from that. Here I'm uncertain at what to do.


In addition to that, I've start using the (if (cond) '() (...)) pattern quite a lot for recurring, so I would be grateful if any seasoned LISPer could comment on how much this is idiomatic and if there are better ways of expressing the same.

Also, the whole point of this exercise is learning, so please don't tell me I should use string-split or regex-split or the like. I am aware of their existence.
tl;dr: See the bottom of the post for my implementation of the function.

As mentioned in Ben Rudgers's answer, lists should not be treated as vectors, as they are not random-access. That means you should not be using numeric indices, list lengths, etc.

Lists are recursive data structures

Lists are recursive data structures: a list is either an empty list, or else it's a non-empty list which conceptually has a first element and a rest of the list. For example:


() is an empty list
(1) is a non-empty list with a first of 1 and a rest of ()
(1 2) is a non-empty list with a first of 1 and a rest of (2)


To perform an operation across all elements of a list, you make use of this recursive structure:


You check whether the list is empty. If so, do the base case.
Otherwise, do something with the first element, then call the same function with the rest of the list. This is the recursive case.


Examples of list-processing functions

Here's a simple example, that calculates the sum of a list of numbers:

(define (sum lst)
  (if (empty? lst)
      0
      (+ (first lst) (sum (rest lst)))))



Base case: if the list is empty, the sum is 0.
Recursive case: if the list is not empty, the sum is the first element plus the sum of the rest of the list. (Recursive case.)


Another example. Suppose you want to write a function that takes a list of numbers, and returns the square of all of the numbers:

(define (square-all lst)
  (if (empty? lst)
      empty
      (cons (expt (first lst) 2) (square-all (rest lst)))))



Base case: If the list is empty, return an empty list.
Recursive case: If the list is not empty, return a new list where:

the first element of the new list is the square of the first element of the old list, and
the rest of the new list is the "square of all the numbers" of the rest of the old list.



As a third example, consider a function where you want to take a list and return all the elements that are numbers:

(define (only-numbers lst)
  (if (empty? lst)
      empty
      (if (number? (first lst))
          (cons (first lst) (only-numbers (rest lst)))
          (only-numbers (rest lst)))))



Base case: If the list is empty, return an empty list.
Recursive case: If the list is not empty, then:

If the first element of the old list is a number, return a new list where:

the first element of the new list is the first element of the old list, and
the rest of the new list is only the numbers from the rest of the old list.

If the first element of the old list is not a number, discard it and return only the numbers from the rest of the old list.



Generalising the above examples

Do you see a pattern? You always check the list for empty, and handle the base case if so, and otherwise handle the first element along with calling itself with the rest of the list. In fact, all three of the functions above fit this pattern:

(define (FUNCTION lst)
  (if (empty? lst)
      BASE-CASE
      (SOMETHING (first lst) (FUNCTION (rest lst)))))


This pattern is called a right-fold, or foldr as it's called in Racket. All three of the functions above can be written using foldr (I use the parameter name next to refer to the result of the recursive call, (FUNCTION (rest lst))):

(define (sum lst)
  (foldr (lambda (element next)
           (+ element next))
         0 lst))

(define (square-all lst)
  (foldr (lambda (element next)
           (cons (expt element 2) next))
         empty lst))

(define (only-numbers lst)
  (foldr (lambda (element next)
           (if (number? element)
               (cons element next)
               next))
         empty lst))


This pattern can be used whenever you are writing a function that processes all the elements of a list, one by one. Usually, you would use the element's value to compute the result, but it's not always necessary; for example, you can implement length like this:

(define (length lst)
  (foldr (lambda (element next)
           (+ next 1))
         0 lst))


Putting all this together

All the above is a very roundabout way to say that the splitting function you're trying to write is also a right-fold operation. It looks like this:

(define (split-by lst x)
  (foldr (lambda (element next)
           (if (eqv? element x)
               (cons empty next)
               (cons (cons element (first next)) (rest next))))
         (list empty) lst))


Let's break this down:


Base case: If the incoming list is empty, return a list with an empty sublist inside.
Recursive case: If the incoming list is not empty, consider the first element:

If that element is equivalent (eqv?) to the splitter, then prepend an empty sublist to the next result.
Otherwise, prepend the element to the frontmost sublist of the next result.



The code is quite dense, but I intentionally wrote it the way a seasoned Schemer would write it (except that it's more common to write car, cdr, null?, and '() instead of first, rest, empty?, and empty). It may take you a while to unpack all this information, if you're new to Scheme. Please feel free to ask for any clarifications.