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:

```
;;; 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 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 goes into more details about them. You can implement them like a tree, with internal node and leaf structs, but the original paper 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:

```
(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.)

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, 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):

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

So in conclusion, nifty but not really of significance.