Velocity Reviews > Code Explaination: Spelling correction code

# Code Explaination: Spelling correction code

Drew
Guest
Posts: n/a

 04-12-2007
I recently saw this website: http://www.norvig.com/spell-correct.html

All the code makes sense to me save one line:

def known_edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in
NWORDS)

I understand (from seeing a ruby version of the code) that the goal
here is to rerun the edits1 method on each member of the set returned
by running edits1 on the initial word. However, I'm confused how the
for within a for works. Can anyone help shed some light on this for me?

Steven Bethard
Guest
Posts: n/a

 04-12-2007
Drew wrote:
> I recently saw this website: http://www.norvig.com/spell-correct.html
>
> All the code makes sense to me save one line:
>
> def known_edits2(word):
> return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in
> NWORDS)

This is the same as:

result = set()
for e1 in edits1(word):
for e2 in edits1(e1):
if e2 in NWORDS:
return result

The thing between the ``set(`` and ``)`` is called a generator
comprehension if you'd like to look into it further.

STeVe

Drew
Guest
Posts: n/a

 04-12-2007
On Apr 11, 11:27 pm, Steven Bethard <(E-Mail Removed)> wrote:
> Drew wrote:
> > I recently saw this website:http://www.norvig.com/spell-correct.html

>
> > All the code makes sense to me save one line:

>
> > def known_edits2(word):
> > return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in
> > NWORDS)

>
> This is the same as:
>
> result = set()
> for e1 in edits1(word):
> for e2 in edits1(e1):
> if e2 in NWORDS:
> return result
>
> The thing between the ``set(`` and ``)`` is called a generator
> comprehension if you'd like to look into it further.
>
> STeVe

Steve -

Thanks for the response. I'm somewhat familiar with generator/list
comprehension but was unsure how multiple statements were evaluated
when chained together. From your explanation, I'm assuming they are
evaluated from the "inside out" rather than left to right or right to
left.

Does the mean that the comprehension on the inside is always evaluated
first?

Thanks,
Drew

Steven Bethard
Guest
Posts: n/a

 04-12-2007
Drew wrote:
> On Apr 11, 11:27 pm, Steven Bethard <(E-Mail Removed)> wrote:
>> Drew wrote:
>>> def known_edits2(word):
>>> return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in
>>> NWORDS)

>>
>> This is the same as:
>>
>> result = set()
>> for e1 in edits1(word):
>> for e2 in edits1(e1):
>> if e2 in NWORDS:
>> return result
>>
>> The thing between the ``set(`` and ``)`` is called a generator
>> comprehension if you'd like to look into it further.

>
> Thanks for the response. I'm somewhat familiar with generator/list
> comprehension but was unsure how multiple statements were evaluated
> when chained together. From your explanation, I'm assuming they are
> evaluated from the "inside out" rather than left to right or right to
> left.
>
> Does the mean that the comprehension on the inside is always evaluated
> first?

Not really (at least for the most literal interpretation of ``evaluated
first``). I find it easiest to think of translating them into regular
for loops by adding the appropriate indentation.

Starting with:

(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

(e2
for e1 in edits1(word)
for e2 in edits1(e1)
if e2 in NWORDS)

(e2
for e1 in edits1(word)
for e2 in edits1(e1)
if e2 in NWORDS)

Moving the add/append to the bottom:

for e1 in edits1(word)
for e2 in edits1(e1)
if e2 in NWORDS
e2

Adding the remaining boiler-plate:

result = set()
for e1 in edits1(word):
for e2 in edits1(e1):
if e2 in NWORDS:

So multiple for- and if-expressions are evaluated in the same order that
they would normally be in Python, assuming the proper whitespace was added.

HTH,

STeVe

Drew
Guest
Posts: n/a

 04-12-2007
On Apr 12, 10:28 am, Steven Bethard <(E-Mail Removed)> wrote:
> Drew wrote:
> > On Apr 11, 11:27 pm, Steven Bethard <(E-Mail Removed)> wrote:
> >> Drew wrote:
> >>> def known_edits2(word):
> >>> return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in
> >>> NWORDS)

>
> >> This is the same as:

>
> >> result = set()
> >> for e1 in edits1(word):
> >> for e2 in edits1(e1):
> >> if e2 in NWORDS:
> >> return result

>
> >> The thing between the ``set(`` and ``)`` is called a generator
> >> comprehension if you'd like to look into it further.

>
> > Thanks for the response. I'm somewhat familiar with generator/list
> > comprehension but was unsure how multiple statements were evaluated
> > when chained together. From your explanation, I'm assuming they are
> > evaluated from the "inside out" rather than left to right or right to
> > left.

>
> > Does the mean that the comprehension on the inside is always evaluated
> > first?

>
> Not really (at least for the most literal interpretation of ``evaluated
> first``). I find it easiest to think of translating them into regular
> for loops by adding the appropriate indentation.
>
> Starting with:
>
> (e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
>
>
> (e2
> for e1 in edits1(word)
> for e2 in edits1(e1)
> if e2 in NWORDS)
>
>
> (e2
> for e1 in edits1(word)
> for e2 in edits1(e1)
> if e2 in NWORDS)
>
> Moving the add/append to the bottom:
>
> for e1 in edits1(word)
> for e2 in edits1(e1)
> if e2 in NWORDS
> e2
>
> Adding the remaining boiler-plate:
>
> result = set()
> for e1 in edits1(word):
> for e2 in edits1(e1):
> if e2 in NWORDS:
>
> So multiple for- and if-expressions are evaluated in the same order that
> they would normally be in Python, assuming the proper whitespace was added.
>
> HTH,
>
> STeVe

Wow, thanks for having the patience to write that out. This makes
perfect sense now.

-Drew