Brent Yorgey byorgey at seas.upenn.edu
Sun Oct 7 15:09:02 CEST 2012

```Neat, thanks for sharing this, Roger.  For those worried about the
efficiency of 'lower' and 'upper', I suggest as a fun exercise
modifying them to do something like binary search: first jump by
increasing powers of two until the predicate is true, then do a binary
search to find the exact point where the predicate goes from false to
true.

-Brent

On Sun, Oct 07, 2012 at 09:47:32AM +0000, Costello, Roger L. wrote:
> 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"
>
>
> - 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
>
> _______________________________________________
> Beginners mailing list