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

On 08/07/2012 12:52 PM, Prabhakar Ragde wrote:
> 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

Ah! I'll have to have a look at my `list-flatten' and `vector-flatten' 
that use a predicate to distinguish elements, to make sure they don't 
have this problem. Thanks for pointing it out!

Neil ⊥