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

Re: FP languages have a bottom-up bias?

by BrowserUk (Pope)
on Jun 27, 2005 at 22:59 UTC ( #470412=note: print w/ replies, xml ) Need Help??


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

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.


    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.


  • Comment on Re: FP languages have a bottom-up bias?
    Select or Download Code
    Here you go: an example of top-down FP
    by tmoertel (Chaplain) on Jun 28, 2005 at 01:43 UTC
      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

        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://470412]
    help
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others about the Monastery: (9)
    As of 2014-12-21 02:46 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (101 votes), past polls