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 ⊥
_________________________
Racket Developers list:
http://lists.racket-lang.org/dev
