Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Here you go: an example of top-down FP

by tmoertel (Chaplain)
on Jun 28, 2005 at 01:43 UTC ( #470445=note: print w/ replies, xml ) Need Help??


in reply to Re: FP languages have a bottom-up bias?
in thread TMTOWTDI... and most of them are wrong

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


Comment on Here you go: an example of top-down FP
Select or Download Code
Re: Here you go: an example of top-down FP
by BrowserUk (Pope) on Jun 28, 2005 at 02:50 UTC
    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?


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://470445]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (10)
As of 2014-09-16 22:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (51 votes), past polls