Splitting a list in Racket

Question

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 (< 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.

Answer 1

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:

1. You check whether the list is empty. If so, do the base case.
2. 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)))))

1. Base case: if the list is empty, the sum is 0.
2. 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)))))

1. Base case: If the list is empty, return an empty list.
2. Recursive case: If the list is not empty, return a new list where:
   1. the first element of the new list is the square of the first element of the old list, and
   2. 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)))))

1. Base case: If the list is empty, return an empty list.
2. Recursive case: If the list is not empty, then:
   1. If the first element of the old list is a number, return a new list where:
      1. the first element of the new list is the first element of the old list, and
      2. the rest of the new list is only the numbers from the rest of the old list.
   2. 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:

1. Base case: If the incoming list is empty, return a list with an empty sublist inside.
2. Recursive case: If the incoming list is not empty, consider the first element:
   1. If that element is equivalent (eqv?) to the splitter, then prepend an empty sublist to the next result.
   2. 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.

Answer 2

Style

Format

Racket tends to use two space indentation rather than Python's four spaces. This keeps code from indenting too far to the right and because Lisps allow multiple expressions on a single line, reduces the issues with lines becoming uncomfortably long. Keep in mind that "left banana"s [ ( ] are also there to help the reader.

Names

The big ambiguous name is split. What does it split? How do I know that it it can't be used on vectors?

The naming is inconsistent: nextpos should be next-pos per Lisp's conventions. However, next-position would be more descriptive. Personally, I'm not a fan lst because it looks like 1st in many typefaces. More importantly I have no idea what a del is other than a key on my keyboard. Please give the reader something like list-of-any and delimiter.

Generally, I find that first and rest are more readable than car and cdr. The advantage of the latter pair is their composibility into caaddr etc. And if I find myself using that, I consider giving it a name that describes what it represents in the program's business logic, e.g. (define customer-address caaddr).

In the same vein, I agree with your intuition about (let loop... using (define (some-loop-function foo bar baz) ...) is more clear.

Code Smell

Treating a list as a vector

Your intuition about list-tail is also sound.

Lists are ideal for providing sequential access. They are poor for random access with indices because reaching the kth element requires following a sequence of pointers from the first element until k elements have been visited. Likewise, determining the length of an n element list requires traversing n pointers. This can quickly put operations into O(n^2) time complexity or worse.

Inline Logic

(loop (let ((...)) (if (...))) is a hint that (let loop...) isn't a particularly clear way to express simple logic.

An Illustrative alternative

The basic structure of the procedure split-list is similar to Racket's built in (let loop...) in that there is a recursive call to an inner procedure my-split that does the heavy lifting and is initialized with the values from the command line.

Note that my-split still takes target as an argument. This allowed building it up and testing it before wrapping it between (define (split-list..) and the trampoline (my-split list-of-x target null).

#lang racket

(define (split-list list-of-x target)

  ;; A predicate to determine to split the list
  (define (split-at? value)
    (not (equal? value target)))

  ;; Inner function to pass around state as accumulator
  (define (my-split list-of-x target accumulator)
    (cond
     ;; Input exhausted
     [(null? list-of-x)
      accumulator]
     [else
      (let-values
        ([(front-list back-list)
          (splitf-at list-of-x split-at?)])    
        (cond
          ;; Input exhausted
          [(null? back-list)
           (append accumulator (list front-list))]
          [else
            (my-split (rest back-list)
                      target
                      (append accumulator (list front-list)))]))]))
  ;; trampoline
  (my-split list-of-x target null))

The key element is the use of the library function splitf-at in conjuction with let-values. Splitf-at performs the task of dividing the list into the part we want to return and the rest of the list which we want to search.

The overall design of the procedure is simplified by a structure based on case analysis and a recursive definition of the inner function.

Final Thoughts

Finding and working with splitf-at and let-values is, in my opinion, not something a new racketeer without Lisp experience is likely to do. The only way to see them is to be familiar with Racket's documentation and that takes time.

Answer 3

Your (if (cond) '() (...)) pattern can be replaced by (unless (cond) (...))

The first solution that comes to mind is a recursive one with an accumulator:

(define (split lst delim)
  (let loop ([lst lst]
             [accum '(())])
    (if (empty? lst)
      (reverse (map reverse accum))
      (if (equal? delim (first lst))
        (loop (rest lst) (cons '() accum))
        (loop (rest lst) (cons (cons (first lst) (first accum))
                               (rest accum)))))))

I'm not very fluent with racket's vocabulary, but looking at http://docs.racket-lang.org/reference/pairs.html there seems enough for a solution in index space if you assume a method called index-of (https://stackoverflow.com/questions/15871042/how-do-i-find-the-index-of-an-element-in-a-list-in-racket)

(define (split lst delim)
  (let ([pivot (index-of lst delim)])
    (if (not pivot)
      (list lst)
      (cons (take lst pivot)
            (split (drop lst (+ pivot 1)) delim)))))

member is another tantalizing method, but I can't see an elegant solution using it.

Answer 4

Following function may have some ideas:

(define (split2 lst del)
  (let loop ((lst lst)(outl '()))        ; start a loop with empty outlist
    (cond
      [(null? lst) (reverse outl)]       ; return outlist if list is empty
      [else (define templist             ; create a list till delimiter
              (for/list ((i lst) 
                         #:break (equal? i del))   ; break on delimiter
                i))
            (loop (drop lst              ; remove initial items from original list
                        (if (>  (length lst) (length templist))   
                            (+ 1(length templist))
                            (length lst)))
                  (cons templist outl)       ; combine templist with outlist
                  )])))                      ; start loop again

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

Ouput:

'((a b c) (d) (e) (f))
'(() (1 2) (2) (3))

Please see my comments in the code above.

Edit: The advantages of above function are:

This method uses relatively simple built-in functions: for/list (along with #:break clause) and drop function.

It follows the task to be done in an iterative manner within the loop:

1. It uses for/list to get items one by one into a list till delimiter is reached. This list is added to final outlist.

2. Drop from initial list those number of initial items (+ 1 for delimiter) and start loop again.

All this results in a relatively small and simple to understand single function program.