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"
>
> 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
>
> _______________________________________________
> Beginners mailing list
>
Beginners@haskell.org
>
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners