[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

For closure, quadratic-time and linear-time `flatten' in Typed Racket:

#lang typed/racket

(define-type (Listof* A) (Rec T (U A (Listof T))))

(: flatten-quadratic (All (A) ((Listof* A) ((Listof* A) -> Boolean : A)
                                            -> (Listof A))))
(define (flatten-quadratic lst pred?)
   (let loop ([lst lst])
     (cond [(pred? lst)  (list lst)]  ; must check this first!
           [else  (append* (map loop lst))])))

(: flatten (All (A) ((Listof* A) ((Listof* A) -> Boolean : A)
                                  -> (Listof A))))
(define (flatten lst pred?)
   (reverse
    (let loop ([lst lst] [#{acc : (Listof A)} empty])
      (cond [(pred? lst)  (cons lst acc)]
            [else  (for/fold ([acc acc]) ([x  (in-list lst)])
                     (loop x acc))]))))

 > (flatten 4 number?)
- : (Listof Complex)
'(4)
 > (flatten '(()) number?)
- : (Listof Complex)
'()
 > (flatten '(((1 2) (3 4)) ((5 6) (7 8))) number?)
- : (Listof Complex)
'(1 2 3 4 5 6 7 8)
 > (define-predicate listof-number? (Listof Number))
 > (flatten '(()) listof-number?)
- : (Listof (Listof Complex))
'(())
 > (flatten '() listof-number?)
- : (Listof (Listof Complex))
'(())
 > (flatten '((4 5) ((6 7) (8 9))) listof-number?)
- : (Listof (Listof Complex))
'((4 5) (6 7) (8 9))


The array library does something a little different. At the point where 
`flatten' is required, it knows the shape of the intended array (thus 
the size), so it allocates a vector and bangs the elements into it. I 
tried doing the same in `flatten', but it ended up a little slower.

Neil ⊥