Scheme code kata

A list manipulation mini-challenge for those of you learning Scheme (or any other Lisp), posted by Jens Axel Søgaard in c.l.s:

Consider the problem of turning a list consisting
of a mix between symbols and non-symbols into a
list of lists of the symbol and its following
non-symbols. That is:

Input:    ({ *} ... ) 
Output:   (( (*)) ...) 
Example:     (a 1 2 3 b 4 5 c d 8 9 e) 
           -> ((a (1 2 3)) (b (4 5)) (c ()) (d (8 9)) (e ())) 

It is possible to do this in a variety of ways, but
I’d like to see an easy-to-read yet short solution.

There are some elegant solutions in the corresponding c.l.s news thread, but it will be a lot funnier if you try your hand at it first. Extra kudos for those of you posting your solution in the comments section :).


11 Responses to “Scheme code kata”

  1. mr_pengy Says:

    Well, for what it’s worth, here’s mine (I have a bad feeling that my comment won’t be formatted):

    (define (make-symb-list l)
        (define (make-number-list l)
                ((null? l) '())
                ((symbol? (car l)) '())
                (#t (cons (car l) (make-number-list (cdr l))))))
            ((null? l) '())
            ((number? (car l)) (make-symb-list (cdr l)))
            (#t (cons (list (car l) (make-number-list (cdr l)))
                (make-symb-list (cdr l))))))
  2. willyh Says:

    Okay, here’s mine:

    (define (segregate-list l)
      (let segregate ((key (car l))
                      (test-pred? number?)
                      (input-list (cdr l))
                      (key-list '())
                      (output-list '()))
        (if (null? input-list)
          (reverse (cons (cons key (list (reverse key-list))) output-list))
          (if (not (test-pred? (car input-list)))
              (segregate (car input-list)
                         (cdr input-list)
                         (cons (cons key (list (reverse key-list)))
              (segregate key
                         (cdr input-list)
                         (cons (car input-list) key-list)
  3. Andi Says:

    relatively new to scheme, judging by some c.l.s submissions i am not thinking functional enough just yet:

    (define (bucketize lis)
      (cond ((null? lis) '())
            ((not (symbol? (car lis))) (error "expected a symbol"))
             (let LOOP ((args '()) (lis2 (cdr lis)))
               (cond ((null? lis2) (list (list (car lis) (reverse args))))
                     ((symbol? (car lis2)) (cons (list (car lis) (reverse args)) (bucketize lis2)))
                     (else (LOOP (cons (car lis2) args) (cdr lis2))))))))
  4. Kevin Greer Says:

    Here’s my solution which is O(n) and doesn’t use any built-in list processing functions like reverse, append, map, fold, etc. Just cons, car, and cdr.

    (define (plist->alist l)
      (define (f l)
            (if (null? l)
               (let* ((rest (f (cdr l)))
                      (cur  (cons (cons (car l) (car rest)) (cdr rest))))
                          (if (symbol? (car l)) (cons '() cur) cur))))
      (cdr (f l)))
  5. Greg Buchholz Says:

    The Haskell language list library has an interesting function “groupBy”with a nice concise definition. You’d use it like…

    import Data.List

    data Sym = A | B | C | D | E deriving Show
    data Foo = S Sym | N Integer

    instance Show Foo where
    show (S x) = show x
    show (N x) = show x

    main = print $
    map (\x -> (head x, tail x))
    (groupBy nums [ S A, N 1, N 2, N 3,
    S B, N 4, N 5,
    S C,
    S D, N 8, N 9,
    S E ])

    nums (S _) (N _) = True --A symbol followed by a number is good group
    nums (N _) (N _) = True --A number followed by a number is good group
    nums _ _ = False --Anything else needs a new grouping

  6. Ian G Says:

    Okay, here’s a different take. Could be made shorter if you used let-values but this is the R5RS version.

    (define (plist->alist lst)
      (define (reduce l)
        (if (null? l)
            (values () ())
            (let ((head (car l))
                  (tail (cdr l)))
                  (lambda () (reduce tail))
                (lambda (non-symbols tail)
                  (if (symbol? head)
                      (values ()
                              (cons (list head non-symbols) tail))
                      (values (cons head non-symbols) tail)))))))
      (call-with-values (lambda () (reduce lst))
        (lambda (ignore result) result)))
  7. siktir a.q. Says:

    amınıza koyim sizin

  8. Anthony Says:

    Is there anybody that can give some tips in parogramming using scheme…
    This is my subject this schoolyear..

  9. msingh Says:

    ; i noticed that the reverse is nicer to work with:
    ; [4]> (reverse ‘(a 1 2 3 b 4 5 c d 8 9 e))
    ; (E 9 8 D C 5 4 B 3 2 1 A)

    (defun kata (list)
    (let ((list* (nreverse list))
    (dolist (x list* kata)
    (cond ((symbolp x)
    (push (list x block) kata)
    (setf block nil))
    (t (push x block))))))

    CL-USER> (kata ‘(a 1 2 3 b 4 5 c d 8 9 e))
    ((A (1 2 3)) (B (4 5)) (C NIL) (D (8 9)) (E NIL))

  10. A Scheme Code Kata « the logic grimoire Says:

    […] beware! This is a meta-creature, a post about a post about a post. By way of comp.lang.scheme, the musings of the great jao (who incidentally is the Wizard behind Geiser (which is the way to Scheme with Emacs these days)), […]

  11. Richard Loveland Says:

    Many years later, I’ve discovered this post. My solution (inspired by Brian Harvey’s from the abovementioned thread in c.l.s):

    (define (p->a p)
    (cond ((null? p) ‘())
    ((symbol? (car p))
    (cons (list (car p)
    (gather-next-batch number? (cdr p)))
    (p->a (cdr p))))
    (else (p->a (cdr p)))))

    (define (gather-next-batch pred seq)
    (cond ((null? seq) ‘())
    ((pred (car seq))
    (cons (car seq)
    (gather-next-batch pred (cdr seq))))
    (else ‘())))

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: