Haskell version of Norvig's spelling corrector (opens in new tab)

> 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) <- splits w] - also see 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) <- splits w , c <- alphabet]

... and so on.

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]).

Interesting read for a Haskell newcomer like me!

Regarding the original webpage of Norvig's spelling corrector, I think it is not up to date as I remember browsing the web and finding some shorter versions in other languages.

I've shortened the Python version to 14/15 lines using some features of Python3.

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

Not to make any particular point, but mainly just because I fancied a bit of procrastination this afternoon, here's a CoffeeScript version (heavily leaning on Underscore): https://gist.github.com/benshimmin/2ee78c932797faadfc89

Which "proves" again that programming is neither about OO nor about purity..)