Haskell version of Norvig's spelling corrector

Minor nitpick: the first real line of code

  alphabet = "abcdefghijklmnopqrstuvwxyz"

is better written as

  alphabet = ['a'..'z']

This is really syntactic sugar for

  enumFromTo 'a' 'z'

using the function

  enumFromTo :: Enum a => a -> a -> [a]

from the typeclass Enum for enumerable types, and the fact that a string (type String) is just a list of characters (type [Char]).

> I wrote this code putting brevity over readability, which is something I usually never do

Shouldn't the point of such a post be to show interesting code? I'm having trouble reading through the densely packed source.

In addition to tromp's minor nitpick, I have several major ones.

- the code is full of redundant parentheses. HLint can detect those (and many other style errors) automatically. LPaste has HLint installed so you have a linting pastebin available online. http://lpaste.net/116871

- A lot of the functions are written in a non-idiomatic way. "m >>= return . f" is "fmap", "(.)" can combine functions much more readable than Lisp stacks of parentheses.

- ByteString.Char8 is usually a wrong choice, more on that here: https://github.com/quchen/articles/blob/master/fbut.md#bytes...

- If you count to "length x" then often there's a more elegant solution that avoids calculating the length altogether. For example "splits xs = zip (inits xs) (tails xs)".

- Brevity is never better than readability.

- No top-level definitions should lack a type signature. GHC even has warnings for that (I think they start firing with -W).

- A function should do one thing and then be composed with other functions. "lowerWords" converts to words and then maps them all to lower case, for example. These are two completely different operations in one long line.

- In order of increasing generality: foldr union empty = unions = mconcat = fold

- Use pattern matching, avoid "(!!)". transposes w = [ a ++ [b0,b1] ++ bs | (a, b0:b1:bs) https://github.com/quchen/articles/blob/master/fbut.md#head-...

- For large amounts of words that you split and concatenate again, String is probably not the right type. Text is good for dealing with such things.

- replaces w = [as ++ [c] ++ bs | (as, _:bs) ... and so on.

For reverse sorting, there's a type that does specifically that.

    sortBy (comparing (Down . snd))

See http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-Or...

all that, plus, re the question at the end of the article about chooseBest:

    chooseBest ch ws = maximumBy (compare `on` (\w -> M.findWithDefault 0 w ws))
       (S.toList ch)

this is closer to what's in Norvig's article - a single pass over the elements of 'ch', taking the one whose entry in the 'ws' set has the highest count - treating words not in the set as having a count of 0. No sort required. (maximumBy is from Data.List, on is from Data.Function)

Cool! Since we're suggesting changes, here's what I'd do. (Not that anything is wrong with the OP's code, just that it's good to point out all the different stylistic techniques you can adopt.)

    7. alphabet = ['a'..'z']
    8. nWords = B.readFile "big.txt" >>= return . train . lowerWords . B.unpack

or:

    8. nWords = train . lowerWords . B.unpack  B.readFile "big.txt"
    

Make `splits`, `deletes`, etc. values (not functions). `splits` has access to `w`, so there's no need to pass it as an argument 4 times (or even to pass `w` as an argument to the other functions).

    27. sortCandidates = (sortBy (flip (comparing snd))) . M.toList