Classic Puzzle: Listing List Prefixes

General
1

Recently I found an archive of the newsletter "LISP Pointers".
The following puzzle was in an article by Olivier Danvy.
Below is the introduction to the puzzle.
I'll post a solution in a week.
Send me a PM if you want a link to the article.

/Jens Axel

Abstract

The Lisp Puzzles feature in Lisp Pointers, Volume 1, Number 6 proposed the following exercise:

Given a list, compute the list of its prefixes.

Surprisingly, the solutions proposed in later issues all used intermediary copies and/or traversed the original list repeatedly.

This ​​note presents a higher-order solution that does not use copies and that traverses the original list only once. Further, this solution can be simply expressed by abstracting control procedurally.

Introduction

Listing list suffixes is a simple exercise in Lisp because it can be done by traversing the source list once [1]:

(maplist (lambda (x) x) '(a b c d))
=> ((a b c d) (b c d) (c d) (d))

The footnote [1] contains:

Given the functional maplist of:

(define maplist
  ;; (List(A) -> B) * List(A) -> List(B)
  (lambda (f l)
    (if (null? l)
        '()
        (cons (f l) (maplist f (cdr l))))))

End of footnote.

On the other hand, listing list prefixes:

(xpl '(a b c d))
=> ((a) (a b) (a b c) (a b c d))

is an interesting exercise because Lisp lists are singly-linked. This means that the beginnings of the source list cannot be shared, and thus successive prefixes must be physically copied.

Using maplist requires reversing the list to have it in the standard order, reversing all of its prefixes, and reversing the result. It seems that xpl was made to be programmed in Scheme:

(define xpl
  ;; List(A) -> List(List(A))
  (lambda (l)
    (reverse
      (maplist reverse
               (reverse l)))))

This solution is a bit luxurious since it wastes 2×length(l)2 \times \text{length}(l)2×length(l) cons-cells for reversing the argument and the result.

Since the tails of the prefixes cannot be shared, it is logical to wonder whether their construction could be shared. This note shows that such sharing is indeed possible.

1 Like
2

This is a fun puzzle! Thank you, @soegaard.

My attempt:

#lang racket/base

(define maplist
  (lambda (f l)
    (if (null? l)
        null
        (cons (f l) (maplist f (cdr l))))))

(define xpl
  (lambda (l)
    (reverse (maplist reverse (reverse l)))))

(xpl '(a b c d))
;=> '((a) (a b) (a b c) (a b c d))

(define ypl
  (lambda (l)
    (if (null? l)
        null
        (map (lambda (y) (cons (car l) y))
             (cons null (ypl (cdr l)))))))

(ypl '(a b c d))
;=> '((a) (a b) (a b c) (a b c d))

Interestingly, even for moderately large lists (~10,000), this solution is almost twice as slow as the maplist one.