[racket-dev] Is it possible to write `flatten' in TR?

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Tue Aug 7 14:52:00 EDT 2012

Neil wrote:

> (define (flatten lst)
>    (cond [(list? lst)  (append* ((inst map (Listof A) (Listof* A))
>                                  flatten
>                                  lst))]
>          [else  (list lst)]))

This version of flatten has quadratic worst-case running time. Is that 
an issue? A linear-time implementation is possible. Eli has a nice post 
somewhere about this. That would probably run into the same type issues 
(no better, no worse). --PR

Posted on the dev mailing list.