Christopher Howard | 16 Jun 01:54 2013

Efficiency/Evaluation Question

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:

(Continue reading)

Tommy Thorn | 16 Jun 02:39 2013
Picon

Re: Efficiency/Evaluation Question

I expect you'll get many replies...

> row (Grid s l) n = if (n >= s) then [] else l !! n
> 
> col g <at> (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)

While such low-level approach (focus on the element) can certainly
be made to work, but Haskell encourages you to think in higher level
constructs.

I haven't seen this problem before but I would map the original array
from [[Int]] -> [(Int, (Int, Int), Int, Int)], that is: a list of tuples consisting
of the original element, its coordinate, the row maximum and the column
minimum. From there its a trivial filter to find your results. (I'm sure there's
a more elegant solution).

> 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?

There's not enough context to answer the specific question,
but lazy evaluation isn't magic and the answer is probably "no".

Tommy
Christopher Howard | 16 Jun 03:02 2013

Re: Efficiency/Evaluation Question

On 06/15/2013 04:39 PM, Tommy Thorn wrote:
> 
> 
> There's not enough context to answer the specific question,
> but lazy evaluation isn't magic and the answer is probably "no".
> 
> Tommy
> 

Perhaps to simplify the question somewhat with a simpler example.
Suppose you have

code:
--------
let f x = if (x > 4) then f 0 else (sin x + 2 * cos x) : f (x + 1)
--------

After calculating at x={0,1,2,3}, and the cycle repeats, are sin, cos,
etc. calculated anymore?

--

-- 
frigidcode.com

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
(Continue reading)

Christopher Howard | 16 Jun 03:05 2013

Re: Efficiency/Evaluation Question

On 06/15/2013 05:02 PM, Christopher Howard wrote:
> On 06/15/2013 04:39 PM, Tommy Thorn wrote:
> 
> Perhaps to simplify the question somewhat with a simpler example.
> Suppose you have
> 
> code:
> --------
> let f x = if (x > 4) then f 0 else (sin x + 2 * cos x) : f (x + 1)
> --------
> 
> After calculating at x={0,1,2,3}, and the cycle repeats, are sin, cos,
> etc. calculated anymore?

That might have been ambiguous. What I meant was:

code:
--------
let f x = if (x > 4) then f 0 else (sin x + 2 * cos x) : f (x + 1)
--------

If I calculate (f 0), and the cycle repeats after four values, are sin,
cos, etc. calculated anymore?

--

-- 
frigidcode.com

_______________________________________________
(Continue reading)

Clark Gaebel | 16 Jun 03:13 2013
Picon
Picon

Re: Efficiency/Evaluation Question

Yes. In general, GHC won't CSE for you.


  - Clark

On Saturday, June 15, 2013, Christopher Howard wrote:
On 06/15/2013 04:39 PM, Tommy Thorn wrote:
>
>
> There's not enough context to answer the specific question,
> but lazy evaluation isn't magic and the answer is probably "no".
>
> Tommy
>

Perhaps to simplify the question somewhat with a simpler example.
Suppose you have

code:
--------
let f x = if (x > 4) then f 0 else (sin x + 2 * cos x) : f (x + 1)
--------

After calculating at x={0,1,2,3}, and the cycle repeats, are sin, cos,
etc. calculated anymore?

--
frigidcode.com

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Tikhon Jelvis | 16 Jun 03:52 2013
Picon

Re: Efficiency/Evaluation Question

There's a very good StackOverflow question which covers this: "When is memoization automatic in GHC?"[1]. I found it really cleared up the issue for me.

[1]: http://stackoverflow.com/questions/3951012/when-is-memoization-automatic-in-ghc-haskell


On Sat, Jun 15, 2013 at 9:13 PM, Clark Gaebel <cgaebel <at> uwaterloo.ca> wrote:
Yes. In general, GHC won't CSE for you.

  - Clark


On Saturday, June 15, 2013, Christopher Howard wrote:
On 06/15/2013 04:39 PM, Tommy Thorn wrote:
>
>
> There's not enough context to answer the specific question,
> but lazy evaluation isn't magic and the answer is probably "no".
>
> Tommy
>

Perhaps to simplify the question somewhat with a simpler example.
Suppose you have

code:
--------
let f x = if (x > 4) then f 0 else (sin x + 2 * cos x) : f (x + 1)
--------

After calculating at x={0,1,2,3}, and the cycle repeats, are sin, cos,
etc. calculated anymore?

--
frigidcode.com


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane