[racket] Fwd: Performance help

2015-01-02 13:23 GMT+01:00 Daniel Prager <daniel.a.prager at gmail.com>:
> Slightly off-topic:
>
> Norvig's code is both concise and -- to my eye -- highly readable. E.g.
>
> def edits1(word):
>    splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
>    deletes    = [a + b[1:] for a, b in splits if b]
>    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
>    replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
>    inserts    = [a + c + b     for a, b in splits for c in alphabet]
>    return set(deletes + transposes + replaces + inserts)
>
> Python's concise list comprehensions, destructuring, string slice operators,
> and operator overloading slot together nicely to make this kind of thing
> easy to knock out.
>
> I was able to achieve the following in Racket, but it's a fair bit of extra
> for a lesser result:
>
>> (define (edits1 word)
>>   (define sub substring)
>>   (define nth string-ref)
>>   (define splits (for/list ([i (range (add1 (string-length word)))])
>>                    (cons (sub word 0 i) (sub word i))))
>>
>>   (define (map-splits min-b f [chars '(dummy)])
>>     (for*/list ([split splits]
>>                 [a (in-value (car split))]
>>                 [b (in-value (cdr split))]
>>                 #:when (>= (string-length b) min-b)
>>                 [ch chars])
>>       (f a b ch)))
>>
>>   (let ([deletes    (map-splits 1 (λ (a b _)  (~a a (sub b 1))))]
>>         [transposes (map-splits 2 (λ (a b _)  (~a a (nth b 1) (nth b 0)
>> (sub b 2))))]
>>         [replaces   (map-splits 1 (λ (a b ch) (~a a ch (sub b 1)))
>> alphabet)]
>>         [inserts    (map-splits 0 (λ (a b ch) (~a a ch b)) alphabet)])
>>     (append deletes transposes replaces inserts)))
>
>
> Comments? Suggestions?

A DSL to make string manipulations more concise would be nice to have.
An ad hoc attempt can be seen here (the concat macro):

http://scheme.dk/blog/2007/04/writing-spelling-corrector-in-plt.html

The blog post was written before  for  and friends arrived in Racket,
so the code uses srfi 42 instead.

--
Jens Axel Søgaard