I'm working through some beginner-level "keyboard problems" I found at users.csc.calpoly.edu. One problem is the Saddle Points problem:
quote:
--------
Write a program to search for the "saddle points" in a 5 by 5 array of
integers. A saddle point is a cell whose value is greater than or equal
to any in its row, and less than or equal to any in its column. There
may be more than one saddle point in the array. Print out the
coordinates of any saddle points your program finds. Print out "No
saddle points" if there are none.
--------
Let's say I use a simple list grid like so:
code:
--------
array = Grid 5 [ [1,5,3,6,4]
, [8,2,6,3,8]
, [3,8,7,2,9]
, [0,3,7,1,2]
, [7,2,7,4,5] ]
data Grid = Grid Int [[Int]]
--------
And let's say I take a brute force approach, moving through each cell,
checking to see if it is the greatest in its row and the least in its
column. And say I have functions like so for getting rows and columns:
code:
--------
row (Grid s l) n = if (n >= s) then [] else l !! n
col g@(Grid s l) n = if (n >= s) then [] else col_ g n 0
where col_ (Grid s l) n i = if (i >= s) then [] else (head l !! n) :
col_ (Grid s (tail l)) n (i + 1)
--------
My question: With the way Haskell works (thunks, lazy evaluation, and
all that mystery), is it actually worth the trouble of /precalculating/
the maximum row values and minimum column values, to compare cell values
against? Or will, for example, something like (smallest_list_value (col
array 1)) definitely only evaluate once?
--
frigidcode.com
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
