# Difference Lists and Racket

**URL:** <https://racket.discourse.group/t/difference-lists-and-racket/3184>\
**Category:** Show & Tell\
**Tags:** data-structures\
**Created:** [September 28, 2024, 1:25am UTC](https://racket.discourse.group/t/difference-lists-and-racket/3184 "2024-09-28T01:25:07Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [September 28, 2024, 1:25am UTC](https://racket.discourse.group/t/difference-lists-and-racket/3184/1 "2024-09-28T01:25:07Z")

</div>

Something I've been playing with and wanted to share.

If you're building up a final list by appending intermediate ones together, it's easy to get quadratic behavior if you're not careful - appending to the end of a constantly growing list in a loop, for example:

```scheme
;;; Trivial example for demonstration purposes
;;; Tail-recursive but O(N^2)
(define (repeat-list lst n)
  (let loop ([results '()]
             [n n])
    (if (= n 0)
        results
        (loop (append results lst) (sub1 n)))))

(repeat-list '(a b c) 3)

```

A [difference list](https://en.wikipedia.org/wiki/Difference_list) is a purely functional data structure intended to help avert this - it offers **O(1)** append and **O(N)** conversion to a normal list. They're popular in Haskell, and apparently Prolog. [This blog post](https://h2.jaguarpaw.co.uk/posts/demystifying-dlist/) goes into more details about them. You can implement them like a tree, with internal node and leaf structs, but the [original paper](https://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf) describing them used partial function application and function composition to build them up - a data structure made of closures, basically. It reminds me of the some of the things in SICP where they show how to make `cons`, `car`, and `cdr` out of nothing but function applications. And it all easily translates to Racket:

```scheme
(define ((list->dlist list-a) list-b) (append list-a list-b))
(define (dlist-append f g) (compose1 f g))
(define (dlist->list dlst [tail '()]) (dlst tail))

;;; Tail-recursive O(N)
(define (repeat-list lst n)
  (let loop ([results (list->dlist '())]
             [n n])
    (if (= n 0)
        (dlist->list results)
        (loop (dlist-append results (list->dlist lst)) (sub1 n)))))

```

(If you're not familiar with the syntax used in that definition of `list->dlist`, see the [relevant Racket Guide section](https://docs.racket-lang.org/guide/define.html#%28part._.Curried_.Function_.Shorthand%29).)

However...

While it's an interesting and sometimes handy technique, it's not as useful in Racket as it can be in languages like Haskell where appending lists is a binary operation that works on 2 at a time - with Lisp-family languages, `append` can combine any number of lists in time proportional to the sum of their lengths; the bad cases like the first example in the above-mentioned blog post just don't happen unless you're writing really poor code. And with Racket, since [stack overflows from too deep of recursion aren't a thing](https://docs.racket-lang.org/guide/Lists __Iteration__ and_Recursion.html#%28part._.Recursion_versus_.Iteration%29), you can just write a non-tail-recursive function with repeated `appends` that's still linear (Since the final list is built from end to start as the call stack unwinds, just like with difference lists):

```scheme
(define (repeat-list lst n)
  (if (= n 0)
      '()
      (append lst (repeat-list lst (sub1 n)))))

```

So in conclusion, nifty but not really of significance.

---

<div class="post-metadata">

**Author:** ![gus-massa](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/gus-massa/32/507_2.png) [@gus-massa](https://racket.discourse.group/u/gus-massa)\
**Post date:** [September 30, 2024, 7:39pm UTC](https://racket.discourse.group/t/difference-lists-and-racket/3184/2 "2024-09-30T19:39:33Z")

</div>

I think you can also use the new [4.16&nbsp;Treelists](https://docs.racket-lang.org/reference/treelist.html) , `treelist-append` is not O(1), but at least you avoid the O(N^2) time.

> (treelist-append tl ...)  
> Appends the elements of the given tls into a single treelist. If M treelists are given and the resulting treelist’s length is N, then appending takes O(M log N) time.

---

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [October 1, 2024, 11:46pm UTC](https://racket.discourse.group/t/difference-lists-and-racket/3184/3 "2024-10-01T23:46:46Z")

</div>

Yeah, there's other alternatives that can be used. I just thought that difference lists were interesting because of how they're built out of function calls.

---

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [October 6, 2024, 10:07pm UTC](https://racket.discourse.group/t/difference-lists-and-racket/3184/4 "2024-10-06T22:07:11Z")

</div>

Today at RacketCon during his talk, @samth brought up the new treelists and gave a toy benchmark comparing a naive append-happy O(N^2) list reversal function to the equivalent using treelists (Unsurprisingly, the latter won handily). I took notes, and added a version using difference lists.

Results on my laptop:

```none
$ racket dlist-benchmark.rkt
Standard reverse
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 3 gc time: 0
Naive reverse
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 57 gc time: 0
cpu time: 765 real time: 8045 gc time: 62
Treelist reverse
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 1 gc time: 0
cpu time: 0 real time: 18 gc time: 0
cpu time: 15 real time: 230 gc time: 15
Difference list reverse
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 2 gc time: 0
cpu time: 0 real time: 52 gc time: 0

```

Takeaways: `reverse` is screaming fast, even on a list of a half million elements. Difference lists (AKA function composition) are very respectable. Treelists are pretty decent too, despite their more complicated internals.

* * *

Code:

```scheme
#lang racket/base

(require racket/treelist)

;;; Naive reverse
(define (lreverse l)
  (if (null? l)
      '()
      (append (lreverse (cdr l)) (list (car l)))))

(define (tlreverse l)
  (if (null? l)
      (treelist)
      (treelist-append (tlreverse (cdr l)) (treelist (car l)))))

(define (dlist . elems) (list->dlist elems))
(define ((list->dlist list-a) list-b) (append list-a list-b))
(define (dlist-append f g) (compose1 f g))
(define (dlist->list dlst [tail '()]) (dlst tail))
(define (dlreverse l)
  (if (null? l)
      (dlist)
      (dlist-append (dlreverse (cdr l)) (dlist (car l)))))

(define-values (list50 list500 list5k list50k list500k)
  (apply values (map (lambda (n) (build-list n values)) '(50 500 5000 50000 500000))))

(define (run-benchmarks title to-list rev test-cases)
  (collect-garbage)
  (displayln title)
  (for ([test (in-list test-cases)])
    (time (void (to-list (rev test))))))

(run-benchmarks "Standard reverse" values reverse (list list50 list500 list5k list50k list500k))
(run-benchmarks "Naive reverse" values lreverse (list list50 list500 list5k list50k))
(run-benchmarks "Treelist reverse" treelist->list tlreverse (list list50 list500 list5k list50k list500k))
(run-benchmarks "Difference list reverse" dlist->list dlreverse (list list50 list500 list5k list50k list500k))

```