Programming

Yesterday, I posted an 18-line solution to Lars' language problem. One problem with it was that it was not very memory-efficient (or time-efficient, for that matter). In other words, it was optimized for elegance.

Here is a 22-line solution that is much more memory-efficient and works well with his "huge" test case. Note to Planet readers: Planet seems to corrupt code examples at times; click on the original story to see the correct code.

import System.Environment
import Data.List
import Data.Char
import qualified Data.Map as Map

custwords = filter (/= "") . lines . map (conv . toLower)
    where iswordchar x = isAlphaNum x && isAscii x
          conv x = if iswordchar x then x else '\n'

wordfreq inp = Map.toList $ foldl' updmap (Map.empty::Map.Map String Int) inp
    where updmap nm word = case Map.lookup word nm of
                             Nothing -> Map.insert word 1 nm
                             Just x -> (Map.insert word $! x + 1) nm

freqsort (w1, c1) (w2, c2) = if c1 == c2
                                 then compare w1 w2
                                 else compare c2 c1

showit (word, count) = show count ++ " " ++ word
main = do args <- getArgs
          interact $ unlines . map showit . take (read . head $ args) .
                     sortBy freqsort . wordfreq . custwords

The main change from the previous example to this one is using a Map to keep track of the frequency of each word.

Thanks to a little glitch in planet, one of Lars' posts from 2004 came to my attention. In it, he proposes a test for language benchmarking:

Read text from the standard input and count the number of times each word occurs. Convert letters to lower case. Order the words according to frequency, words with the same frequency should be ordered in ascending lexicographic order according to character code. Print out the top N words, where N is a decimal number given on the command line. Each output line must contain the count, a space, and the word (in lower case), and end in an ASCII LINE FEED character. Output must contain exactly N such output lines and no other output lines.

A word contains only ASCII letters A through Z and a through z (convert upper case to lower case) and ASCII digits 0 through 9 and is not empty. All other characters separate words and are ignored except to notice word boundaries. Word boundaries only occur at the beginning and end of the file and at non-word characters. You may not assume a maximum length for the word, line, or input file.

He provides a tarball with sample implementations in C, Python, and Shell.

His C code is 183 lines long, Python 57, and Shell 11. The specs for this test seem particularly suited for shell.

I wrote a version in Haskell, commented and formatted approximately the same as his Python version, but using an algorithm more like the shell version. It comes in at 18 lines. Here it is:

import System.Environment
import Data.List
import Data.Char

custwords = filter (/= "") . lines . map (conv . toLower)
    where iswordchar x = isAlphaNum x && isAscii x
          conv x = if iswordchar x then x else '\n'

wordfreq = map (\x -> (head x, length x)) . group . sort

freqsort (w1, c1) (w2, c2) = if c1 == c2
                                 then compare w1 w2
                                 else compare c2 c1

showit (word, count) = show count ++ " " ++ word
main = do args <- getArgs
          interact $ unlines . map showit . take (read . head $ args) .
                     sortBy freqsort . wordfreq . custwords

Taking a look at this, one thing that might strike you is the function composition in main. This takes the output from one function and feeds it into the next -- and the Haskell syntactic sugar for this makes it look a lot like pipes in the shell version. The interact call takes, as a parameter, a function that takes a string and returns a string. interact supplies stdin as the input and prints the output to stdout. Note that, since Haskell is lazily, this does not mean buffering up the entire input or output -- it is read and written on demand.

The rest of the functions are also standard in Haskell, and you can find them in the index to the library reference if you want to learn more.

I understand and agree that short code doesn't necessarily mean good code, but I think that Haskell provides a very elegant and expressive solution to many problems -- one that also happens to be remarkably concise.

Updated 9/4: Changed isLower to isAlphaNum to fix a bug, and removed unnecessary Data.Map import

First, Evan has a host of interesting articles about Haskell, and I found his lazy big-O article particulary interesting.

Next, Eric Warmenhoven has recently taken up Haskell and posted some Haskell questions on his blog. Eric, here are some answers for you.

First, regarding shared libraries. While Haskell can be compiled to machine code, and GHC is a popular way to do that, a standard C way of representing information about a library (.h and .so files) is not really rich enough for Haskell. Consider, for instance, that functions may accept arguments of a wide range of types (or even things such as lists of any type). Haskell also performs type checking, and thus must know the type of arguments a function expects, as well as its return type, at compile time. So you do not generally compile Haskell code directly to .so files, but rather use the compiler's module or package support to do that. See Cabal for more information on packages. Through the FFI (Foreign Function Interface), it is possible to both call into C and be called from C with Haskell code, if that's where you want to go. It is actually easier in Haskell than in any other high-level language I've dealt with before.

Regarding circular module deps -- I've never used them and can't really comment. I can say, though, that the .boot files are internal files created by GHC.

Regarding practical stuff in tutorials -- I share your complaint there. I have found a few that are better than the others: Yet Another Haskell Tutorial, and Haskell: The Craft of Functional Programming, 2nd ed., by Simon Thompson. Several of us are working intermittently on a project called Haskell V8 -- take a look and darcs send me patches! I would say that Haskell's I/O system is the most powerful I've seen in many ways -- especially with regard to laziness -- and in the upcoming GHC 6.6 release, it will be both lazy *and* blazingly fast. Very nice.

There isn't much Debian-specific documentation, but there is a draft policy and a mailing list (link to it is in the policy doc).

Hope this helps!