[erlang-questions] Suggestion for a spell corrector implementation

[ok]

On 15 May 2007, at 10:18 pm, Joe Armstrong wrote:
>  You could write deletions like this:
>
> deletions(Word) ->
>     [Word -- [I] || I <- Word]
>
> -- is the list subtraction operator

Unfortunately, this gives the wrong answers.

deletions("suggest") =
   ["uggest","sggest","sugest","sugest","uggest","sugges"]
     ok       ok       ok       ok*      wrong    ok
The second "sugest" happens to be a good answer, but for the
wrong reason.  It should be there because the second "g" was
deleted, but it's there because the first one was deleted again.
We see this clearly in the fact that "uggest" was reported a
second time, when the right answer there was "sugget".

deletions("mama") =
   ["ama","mma","ama","mma"]
where we are now missing two of the right answers.

deletions([]) ->
     [];
deletions([C|Cs]) ->
     [Cs | [[C|Ds] || Ds <- deletions(Cs)]].

seems to be the simplest way to get the right answer.
With this definition,
deletions("suggest") =
     ["uugest","sggest","sugest","sugest","suggst","sugget","sugges"]
deletions("mama") =
     ["ama","mma","maa","mam"]