Avoid Case Analyses

7 Oct 2012

      Hi Folks,

"Programs that avoid case analyses are clearer and simpler than those that use case analyses."

Richard Bird made that surprising statement in his book, Introduction to Functional Programming using Haskell. 

It is worthwhile to understand why he said that. In the process we will see a fabulous example of how to start with a specification and systematically develop an implementation.

An extreme example of case analyses is using it to implement an identity function: 

color c 	| c == "red"   	= "red"
             	| c == "green"  	= "green"
             	| c == "blue"  	= "blue"

It is read:

- In the case the color c is "red" then return "red"
- In the case the color c is "green" then return "green" 
- In the case the color c is "blue" then return "blue"

The program is more clearly and simply implemented without case analyses:

	color c   =  c

Let's take a less trivial example. We will implement the floor function. Although Haskell already has a built-in floor function, it will be instructive to see how floor :: Float -> Integer can be programmed. The program will be developed in a systematic manner, starting with a specification for floor. 

After implementing  floor without case analyses, we will then compare it against an implementation that uses cases analyses. 

Recall that the floor of x is the largest integer n satisfying n <= x. Here are a couple examples:

	floor 2.3      	returns 2
	floor (-2.3)  	returns  -3

Let us begin with a specification of floor:

	floor    		::     Float -> Integer
	floor x = n 	==   n <= x < n +1

floor maps a value of type Float to a value of type Integer. The floor of x is n, where x is between n and n +1.

It is tempting to plunge immediately into a case analysis, considering what to do if x is positive, what to do if x is negative, and, possibly, what to do if it is zero. But the specification does not mention cases and we should try not to mention cases either. 

How shall we find n, given an arbitrary x? 

You might respond: Simply truncate x's decimal point and its decimal digits, like so:

	truncate 2.3 	returns 2

But that approach produces the wrong answer for negative values:

	truncate (-2.3) 	returns (-2),  whereas the correct answer is -3

You might then suggest: If x is negative, then truncate and subtract 1.

But that is descending into a case analysis on the sign of x: if x is positive, then truncate; if x is negative, then truncate and subtract 1.

We do not need case analyses. The specification suggests an approach. 

The specification suggests that a search be conducted.

Search for an n that satisfies the condition n <= x, and then increase n until the condition x < n+1 holds:

- Start the search from some starting point, say, start n at 0.
- Lower n until n <= x
- Increase n until x < n+1

Example #1: find the floor of (-2.3):

- Start the search at n = 0
- Lower n until n <= x:  0, -1, -2, -3
- Increase n until x < n+1:  this terminates at once since -2.3 < (-3)+1

  	floor (-2.3) is -3

Example #2: find the floor of 2.3:

- Start the search at n = 0
- Lower n until n <= x:  this terminates at once since 0 < 2.3
- Increase n until x < n+1:  0, 1, 2

  	floor (2.3) is 2

The idea of searching until some condition holds can be encapsulated in a function until, defined by:

	until 		::  (a -> Bool) -> (a -> a) -> a -> a
	until p f x 	=  if p x then x else until p f (f x)

Function until takes 3 arguments p, f, and x:

- p is a Boolean function. Function p is given a value x and it returns True or False. 

Example: this p returns True if x is less than zero (observe that p is a partially applied function):  

    	p = (<0)

   	p (-2)  	returns True
   	p 2      	returns False

- f is a function that processes x.

Example: this f decreases x by one (observe that f is also a partially applied function):

   	f = (subtract 1)

   	f 5     	returns 4
   	f (-5)     returns (-6)

- x is the value operated on.

Read this use of function until:

	until (<0) (subtract 1) 5 		returns  -1

like so: starting n at 5, repeatedly subtract 1 until n is less than 0.

Function until is a built-in Haskell function, as is floor, but for learning purposes we will use our own implementation of them, so place this at the top of your file to hide the built-in version:

	import Prelude hiding (until, floor)

To search for an n satisfying the condition n <= x we will use this function lower:

	x = (-2.3)

	lower  =  until (<=x) decrease 
                 	   where decrease n  =  n - 1

Function lower decreases its argument n until the condition n <= x is satisfied:

	lower 5		returns  -3
	lower (-5)	returns  -5

Suppose we wish to find the floor of (5.3) and we start our search at n = 0. Function lower immediately returns because the condition 0 <= 5.3 is immediately satisfied:

	x = 5.3
	lower 0		returns 0

In this example, the result n found by the search is too small. We need a second search to increase n until the condition x < n+1 is satisfied. We will increase n in steps of 1 to ensure the condition n <= x is maintained. Actually, we will increase n until it just exceeds x and then decrease it by 1. We create a function upper for this:

	upper  =  until (>x) increase
                               where increase n  =  n + 1

	decrease n = n - 1

The output of function upper will be the input to function decrease, so we compose the two functions:

	decrease . upper

Further, we want the input of (decrease . upper) to be the output of function lower, so we compose them:

	decrease . upper . lower

Example: we wish to find the floor of (5.3) and we start our search at n=0. Function lower immediately returns 0 because the condition 0 <= 5.3 is satisfied. Function upper increases 0 to 6, at which point 6 > 5.3 is satisfied. Finally, 6 is decreased by 1 to the answer 5:

	x = 5.3
	(decrease . upper . lower) 0	returns 5

We now have all the ingredients needed to create function floor. The function takes one argument, x:

	floor x

It starts the search from some point, let's choose n=0 as the starting point:

	floor x  =  searchFrom 0

Function searchFrom lowers n=0 until the condition n <= x is satisfied and then raises n until the condition n > x is satisfied and then decreases n by 1: 

	floor x  =  searchFrom 0
		   where  searchFrom  =  decrease . upper . lower

Add the definitions for decrease, upper, and lower:

	floor x  =  searchFrom 0
                where 	searchFrom  	=  decrease . upper . lower
                            	lower              	=  until (<=x) decrease
                          	upper               	=  until (>x) increase
                          	decrease n  	=  n - 1
                          	increase n  	=  n + 1

Notice that this implementation of function floor does not use case analyses. The program is surprisingly short, owing mainly to the absence of a case analysis on the sign of x.

Compare that with a version that uses case analyses: 

floor x 	| x < 0   	=  lower 0
            	| x > 0   	=  (decrease . upper) 0
            	| x == 0  	=  0
               where  lower       	=  until (<=x) decrease
                            upper       	=  until (>x) increase
                            decrease n 	=  n - 1
                            increase n 	=  n + 1

Read as: if x is less than 0 then lower 0 until n <= x is satisfied. If x is greater than 0 then increase 0 until n > x is satisfied and then decrease n by 1. Lastly, if x equals 0 then return 0.

The case analysis version is longer and arguably more complex.

/Roger

Costello, Roger L.

Brent Yorgey

damodar kulkarni

Mike Meyer

Patrick Redmond

damodar kulkarni

Rustom Mody

tags

participants (6)