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.
