# Uses of improper lists?

**URL:** <https://racket.discourse.group/t/uses-of-improper-lists/712>\
**Category:** General\
**Created:** [February 21, 2022, 10:40am UTC](https://racket.discourse.group/t/uses-of-improper-lists/712 "2022-02-21T10:40:42Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Laurent.O](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/laurent.o/32/18_2.png) [@Laurent.O](https://racket.discourse.group/u/Laurent.O)\
**Post date:** [February 21, 2022, 10:40am UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/1 "2022-02-21T10:40:42Z")

</div>

This is likely a veeeery old question, but strangely I hadn't given much thought about it.

Do people use improper lists such as `(a b c . d)` with more than 2 elements? I don't remember ever seeing such a use case.

If not, wouldn't it be possible to just disallow constructing improper lists apart from pairs? That would make `list?` a constant-time check, and would avoid the need for many user-defined procedures to have to worry about improper lists.

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [February 21, 2022, 11:06am UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/2 "2022-02-21T11:06:13Z")

</div>

One boring answer is that it’s used for representing function definitions with a rest argument 😉

```scheme
> (eval '(define (f x . y) (append y (list x))))
> (f 1 2 3) 
'(2 3 1)

```

---

<div class="post-metadata">

**Author:** ![Laurent.O](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/laurent.o/32/18_2.png) [@Laurent.O](https://racket.discourse.group/u/Laurent.O)\
**Post date:** [February 21, 2022, 11:12am UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/3 "2022-02-21T11:12:29Z")

</div>

Right—I forgot that one indeed. I wish this was represented with a keyword instead  
`(define (f x #:rest y) (append y (list x)))`.

(edit) Oh but then that wouldn't work with `apply` so well I guess?

---

<div class="post-metadata">

**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\
**Post date:** [February 21, 2022, 11:32am UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/4 "2022-02-21T11:32:58Z")

</div>

Just to make it explicit: the time used for `list?` is O(1) today.

For BC it is O(1) and for CS it is amortized O(1).

In BC pairs have an `PAIR_IS_LIST` flag.

The beginning of `list?` for BC looks like this:

```scheme
int scheme_is_list(Scheme_Object *obj1)
{
  Scheme_Object *obj2;
  int flags;

  if (SCHEME_PAIRP(obj1)) {
    flags = SCHEME_PAIR_FLAGS(obj1);
    if (flags & PAIR_FLAG_MASK) {
      if (flags & PAIR_IS_LIST)
        return 1;
      else
        return 0;
    }
  } else if (SCHEME_NULLP(obj1))
    return 1;
  else
    return 0;
...

```

For CS you need to check the rumble layer:

> <https://github.com/racket/racket/blob/8679bf6b752eb3603eb1db227438c8590bf3a611/racket/src/cs/rumble/list.ss>

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [February 21, 2022, 12:03pm UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/5 "2022-02-21T12:03:41Z")

</div>

@Laurent.O: `#:rest` could work, but this would affect user-introducing keyword arguments — you would need to reserve `#:rest` to avoid ambiguity — which is fine, but kinda weird.

@soegaard: the actual logic for amortized constant time is no longer in the rumble layer (and the comments there probably should be removed). It's become a primitive in Chez Scheme: [https://github.com/racket/racket/commit/120082f3f922cf3a38756a8a3023ccaed6dfe894](https://github.com/racket/racket/commit/120082f3f922cf3a38756a8a3023ccaed6dfe894).

---

<div class="post-metadata">

**Author:** ![Laurent.O](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/laurent.o/32/18_2.png) [@Laurent.O](https://racket.discourse.group/u/Laurent.O)\
**Post date:** [February 21, 2022, 12:32pm UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/6 "2022-02-21T12:32:48Z")

</div>

@soegaard For a little bit more context, amortized O(1) can still be significant:

```scheme
#lang racket

(define N 100000000)

(let ()
  (define l (time (make-list N 'a)))

  (time (let loop ([l l])
          (if (empty? l) ; implies `list?`
            #true
            (loop (rest l))))))

(let ()
  (define l (time (make-list N 'a)))

  (time (let loop ([l l])
          (if (null? l)
            #true
            (loop (cdr l))))))

```

```scheme
cpu time: 4719 real time: 4719 gc time: 4565 <-- make-list
cpu time: 8929 real time: 8929 gc time: 2 
#t
cpu time: 4273 real time: 4273 gc time: 4119 <-- make-list
cpu time: 178 real time: 178 gc time: 0
#t

```

Possibly this is testing more than `list?`, but I suspect it's the biggest offender anyway.

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [February 21, 2022, 1:14pm UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/7 "2022-02-21T13:14:58Z")

</div>

[https://github.com/racket/racket/issues/3109](https://github.com/racket/racket/issues/3109) might be related?

I think `list?` probably won’t get any faster, but it might be possible to eliminate many calls of `list?` entirely with a smarter compiler optimization.

---

<div class="post-metadata">

**Author:** ![Laurent.O](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/laurent.o/32/18_2.png) [@Laurent.O](https://racket.discourse.group/u/Laurent.O)\
**Post date:** [February 21, 2022, 1:28pm UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/8 "2022-02-21T13:28:28Z")

</div>

Related indeed. In the program above, ideally, `list?` would be checked only once outside the loop. And indeed this would be fast:

```scheme
(let ()
  (define l (time (make-list N 'a)))

  (time (list? l))

  (time (let loop ([l l])
          (if (null? l)
            #true
            (loop (cdr l))))))

```

```scheme
cpu time: 4384 real time: 4385 gc time: 4224
cpu time: 286 real time: 286 gc time: 0
cpu time: 171 real time: 171 gc time: 0
#t

```

The compiler 'merely' needs to prove that `l` always remains a list after first testing the full list (which should follow from `make-list` in any case).

---

<div class="post-metadata">

**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\
**Post date:** [February 21, 2022, 9:35pm UTC](https://racket.discourse.group/t/uses-of-improper-lists/712/9 "2022-02-21T21:35:49Z")

</div>

I am surprised the difference is as large as it is.  
(I am assuming you are using a version newer than the one sorawee points to).

Maybe the contract of `rest` and `first` should be changed to `pair?` instead of `list?`.