[Haskell-cafe] Efficiency/Evaluation Question

Christopher Howard christopher.howard at frigidcode.com
Sun Jun 16 01:54:42 CEST 2013

I'm working through some beginner-level "keyboard problems" I found at
users.csc.calpoly.edu. One problem is the Saddle Points problem:

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:

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:

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?


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 555 bytes
Desc: OpenPGP digital signature
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130615/157d96f6/attachment.pgp>

More information about the Haskell-Cafe mailing list