Re: FP languages have a bottom-up bias?

[BrowserUk]

Yep! There are several possible explainations I guess.

I've been reading the wrong "worked examples".

I (still) haven't done enough Haskell to have extablished a good approach to programming with it.

Perhaps you could show me the steps you would take to tackling the sort of problem I have been trying to get to grips with?

For the purpose of the exercise, I decided to index the words in a bunch of files. To get a start on the exercise, in Perl, I decided to just count the words, here simply defined as whitespace delimited groups of characters, and write the results to a file. This allows me to get something going and I can then work on refining the definition of a "word" and and decide how I am going to store the index.

My first attempt at writing this program (from scratch, just now) was:

#! perl -slw
use strict;
use G; ## Expands wildcards arguments as would be done by most *nix sh
+ells.

our $INDEX ||= 'words.index';

my %index;
if( -e $INDEX ) {
    open INDEX, '<', $INDEX or die "$INDEX: $!";
    m[^([^:]+):(\d+)$] and $index{ $1 } = $2 while <INDEX>;
    close INDEX;
}

while( my $file = @ARGV ) {
    open FILE, '<', $file or warn "$file:$!" and next;
    while( <FILE> ) {
        $index{ $_ }++ for split ' ';
    }
    close $file;
}

my( $key, $val );
open INDEX, '>', $INDEX or die "$INDEX : $!";
print INDEX "$key:$val" while ( $key, $val ) = each %index;
close INDEX;

I then ran a quick sanity check:

P:\test>perl -c windex-1.pl
windex-1.pl syntax OK

So far, so good. Now try it out:

P:\test>windex-1.pl *.pl
710:No such file or directory at P:\test\windex-1.pl line 15.
710:No such file or directory at P:\test\windex-1.pl line 15.
710:No such file or directory at P:\test\windex-1.pl line 15.
710:No such file or directory at P:\test\windex-1.pl line 15.
...

Whoops! A quick look and I see I missed out the keyword pop in line 14:

while( my $file = pop @ARGV ) {

Try again:

P:\test>windex-1.pl *.pl
306836-trietest.pl:Permission denied at P:\test\windex-1.pl line 15, <
+FILE> line 83342.

Okay, I've got 1 file with bad permissions in the directory. And what ended up in words.index?

P:\test>type words.index
expletive:2
$midVal:30
9f:8
proven:2
AT:10
happpen:2
inconsequential:2
perverted:2
$x;:24
TTGGGTCAGCGAATGTCACATTTGGAATGGGAATCGGATGATGGGGGCGA:2
++$x):2
greif:2
yvvvvvvvvvvhvevwvvy:2
@exclude_keys:2
$hh2,:2
scrapped:2
classe:2
sod:2
$array[2]->set($_);:2
Cleaner,:2
$expand_ratio,:8
CACGTCTCCACCCGAAGACTGTGGAATGCTACTATTAAAATACTATTTTT:2
cdpr:2
BLANK_NODE:4
paws:6
"\n$_:2
...

Okay. The word definition is ecclectic, but is seems to be doing what I set out to do, now I can start to refine it. Not a bad start for 10 minutes coding.

[tmoertel]

Like I wrote in my earlier post, I almost always work top down. So, to take up your challenge, I will start with a top-level outline: read in the inputs, process them somehow, and then show the results. Since I don't know what it means (yet) to perform each of those tasks, I will use simple placeholders like id to represent each stage of the outline:

module Main where

main = interact $ showOutput . process . readInput

showOutput = id
process    = id
readInput  = id

This is legal Haskell that compiles and executes. It doesn't do much, however, merely echoing its input:

$ echo alpha beta | ghc -e main WordIndex.hs
alpha beta

Still, it shows how easy it is to start sketching a solution at a high level.

Next, working down, I will flesh out the outline. I won't worry about reading input from files or writing output to an index just yet. For now, I will focus on the core word-counting problem, adding logic to do just that:

module Main where

import qualified Data.Map as Map

main = interact $ showOutput . process . readInput

showOutput = unlines . Map.foldWithKey show1 []
process    = foldl accumulate Map.empty
readInput  = words

show1 key count = (unwords [key, show count] :)
accumulate hash key = Map.insertWith (+) key 1 hash

Notice that I did not need to alter the outline. All I did was add low-level detail to it. Now I have counts:

$ echo alpha beta | ghc -e main WordIndex.hs
alpha 1
beta 1

Continuing to refine the lower-level functionality, I will return to the I/O tasks. Like before, I will add lower-level functions, leaving the top-level outline largely unchanged:

module Main (main) where

import Control.Monad
import qualified Data.Map as Map
import System.Environment

main = control $ showOutput . process . readInput

showOutput = unlines . Map.foldWithKey show1 []
process    = foldl accumulate Map.empty
readInput  = words

show1 key count = (unwords [key, show count] :)
accumulate hash key = Map.insertWith (+) key 1 hash

control f  = readFiles >>= writeIndex . f
readFiles  = getArgs >>= liftM concat . mapM readFile
writeIndex = writeFile "words.index"

Let me recap. I started with a top-level, executable outline and worked down from there. With two simple iterations I was able to add the counting functionality and then the I/O functionality. Now I have a complete solution that is largely equivalent to your code (ignoring details that don't matter for our top-down coding discussion).

As a demonstration, I will compile the code and use it to index itself:

$ ghc -O2 --make -o WordIndex WordIndex.hs
$ ./WordIndex *.hs
$ cat words.index
"words.index" 1
$ 1
(+) 1
(main) 1
(unwords 1
. 5
1 1
:) 1
= 9
>>= 2
Control.Monad 1
Data.Map 1
Main 1
Map 1
Map.empty 1
...

There you have it: top-down functional programming, or at least the way I do it in Haskell. I hope you will trust me that it was quick and easy. (It took much longer to write this explanation than the code.)

Cheers,
Tom

[BrowserUk]

I hope you will trust me that it was quick and easy. (It took much longer to write this explanation than the code.)

Of course, and thankyou. This would make a really good addition to the GHC docs.

Actually, I think it could easily replace The User's Guide in it's entirety for the first 2 months after new users get their hands on it.

(It took much longer to write this explanation than the code.)

And it will probably take me much longer still to understand it :)

One question. In your first pass you use 'interact', which later gets dropped in favour of your own 'control'. Where does 'interact come from? It does not appear to be a part of prelude?

[tmoertel]

The interact function is indeed part of the Prelude. In Haskell 98 it is defined in the IO module, which the Prelude imports and then exports certain symbols from, including interact.