16 Jun 2013 01:54

## 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
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:

```

16 Jun 2013 02:39

### 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
```
16 Jun 2013 03:02

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

```
```_______________________________________________
```

16 Jun 2013 03:05

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

```
```_______________________________________________
```

16 Jun 2013 03:13

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

```_______________________________________________
```
16 Jun 2013 03:52

### 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.

On Sat, Jun 15, 2013 at 9:13 PM, Clark Gaebel 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

_______________________________________________
```_______________________________________________