Take the 2-minute tour ×

How can I construct the function segs that returns a list of all contiguous segments in a list? For example, (segs '(l i s t)) should produce the following answer:

(() (t) (s) (s t) (i) (i s) (i s t) (l) (l i) (l i s) (l i s t))

I'm especially interested in how to solve this problem in accordance with the design principles described in HtDP (no, this is not the problem from the book, so please feel free to discuss it!) How to solve it? Which principles to use in program derivation?

share|improve this question
To ask for clarification, post a comment on the answer and/or amend your question, don't try edit the answer itself. –  Ryan Culpepper Jan 10 '12 at 19:21
add comment

2 Answers

up vote 5 down vote accepted

Start by building up a set of related examples, most trivial first:

(equal? (segs '())
        (list '()))
(equal? (segs '(z))
        (list '()
(equal? (segs '(y z))
        (list '() '(z)
              '(y) '(y z)))
(equal? (segs '(x y z))
        (list '() '(z) '(y) '(y z)
              '(x) '(x y) '(x y z)))

By looking at the examples you can make an observation (which I've used the formatting to highlight): the answer for each example includes the all of the elements from the answer for the previous example. In fact, the contiguous subsequences of a non-empty list are just the contiguous subsequences of its tail together with the non-empty prefixes of the list itself.

So put the main function on hold and write non-empty-prefixes

non-empty-prefixes : list -> (listof non-empty-list)

With that helper function, it's easy to write the main function.

(Optional) The resulting naive function has bad complexity, because it repeats calls to non-empty-prefixes. Consider (segs (cons head tail)). It calls (non-empty-prefixes tail) twice: once because it calls (segs tail) which calls (non-empty-prefixes tail), and again because it calls (non-empty-prefixes (cons head tail)) which calls (non-empty-prefixes tail) recursively. That means the naive function has unnecessarily bad complexity.

The problem is that (segs tail) computes (non-empty-prefixes tail) and then forgets it, so (segs (cons head tail)) has to redo the work. The solution is to hold on to that extra information by fusing segs and non-empty-prefixes into a single function that computes both answers:

segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))

Then define segs as an adapter function that just drops the second part. That fixes the main issue with the complexity.

(Edited to add) Regarding segs+ne-prefixes: here's one way to define non-empty-prefixes. (Note: the empty list has no non-empty prefixes. No need to raise an error.)

;; non-empty-prefixes : list -> (listof non-empty-list)
(define (non-empty-prefixes lst)
  (cond [(empty? lst)
        [(cons? lst)
         (map (lambda (p) (cons (first lst) p))
              (cons '() (non-empty-prefixes (rest lst))))]))

And segs looks like this:

;; segs : list -> (listof list)
(define (segs lst)
  (cond [(empty? lst) (list '())]
        [(cons? lst)
         (append (segs (rest lst))
                 (non-empty-prefixes lst))]))

You can fuse them like this:

;; Return both the contiguous subsequences and the non-empty prefixes of lst
(define (segs+ne-prefixes lst)
   (cond [(empty? lst)
          ;; Just give the base cases of each function, together
          (values (list '())
         [(cons? lst)
          (let-values ([(segs-of-rest ne-prefixes-of-rest)
                        ;; Do the recursion on combined function once!
                        (segs+ne-prefixes (rest lst))])
            (let ([ne-prefixes
                   ;; Here's the body of the non-empty-prefixes function
                   ;; (the cons? case)
                        (cons '() ne-prefixes-of-rest))])
              (values (append segs-of-rest ne-prefixes)

This function still follows the design recipe (or it would, if I had shown my tests): in particular, it uses the template for structural recursion on a list. HtDP doesn't talk about values and let-values, but you could do the same thing with an auxiliary structure to group the information.

HtDP talks about complexity a little bit, but this sort of regrouping of computation is usually discussed more in an algorithms course, under "dynamic programming and memoization". Note that an alternative to fusing the two functions would have been to memoize non-empty-prefixes; that also would have fixed the complexity.

One last thing: the arguments to append near the end should be reversed, to (append ne-prefixes segs-of-rest). (Of course, that means rewriting all of the tests to use the new order, or writing/finding an order-insensitive list comparison function.) Try benchmarking the two versions of the function on a large list (around 300-400 elements), see if you can tell a difference, and see if you can explain it. (This is more algorithms material, not design.)

share|improve this answer
Ryan, can you explain the mechanics I need to apply to obtain this "fused" segs+ne-prefixes function? –  Racket Noob Jan 10 '12 at 19:58
@Racket Noob, I've added an explanation to the end of my answer. –  Ryan Culpepper Jan 10 '12 at 20:11
add comment

There's 2 recursions going on: the first chops atoms off the left, and the second chops atoms off the right. Here's how I'd solve it recursively in 2 functions, in plain terms (since I'm not fluent in Scheme):

Start with the FullList variable in function A, 
accumulate right-chop results on FullList from recursive function B, 
then chop off the left character of FullList and call function A with it. 
Stop when an empty list is received. 

Accumulate all results, and you're golden.

share|improve this answer
add comment

Your Answer


