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 :).
Tags: scheme
February 7, 2006 at 4:19 am
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) (cond ((null? l) '()) ((symbol? (car l)) '()) (#t (cons (car l) (make-number-list (cdr l)))))) (cond ((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))))))February 7, 2006 at 9:23 pm
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) test-pred? (cdr input-list) '() (cons (cons key (list (reverse key-list))) output-list)) (segregate key test-pred? (cdr input-list) (cons (car input-list) key-list) output-list)))))February 9, 2006 at 9:51 pm
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")) (else (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))))))))February 13, 2006 at 4:18 pm
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)))February 13, 2006 at 9:57 pm
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
February 28, 2006 at 3:36 pm
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))) (call-with-values (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)))March 16, 2006 at 5:13 pm
amınıza koyim sizin
November 25, 2006 at 3:27 pm
Hey!!!
Everybody..
Is there anybody that can give some tips in parogramming using scheme…
This is my subject this schoolyear..
Please!!!1
May 23, 2007 at 8:16 am
; 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))
(block)
(kata))
(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))