[Haskell-beginners] Avoid Case Analyses
damodar kulkarni
kdamodar2000 at gmail.com
Sun Oct 7 15:58:05 CEST 2012
Hi Roger,
Thanks for sharing this.
You might then suggest: If x is negative, then truncate and subtract 1.
>
What do you say about the case analysis in "until"?
until p f x = if p x then x else until p f (f x)
Yes, the "until" gives us a higher order pattern and thus more abstraction,
but it still uses case analysis.
Damodar
On Sun, Oct 7, 2012 at 6:39 PM, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
> 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"
> >
> > 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 at haskell.org
> > http://www.haskell.org/mailman/listinfo/beginners
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121007/d96ece76/attachment-0001.htm>
More information about the Beginners
mailing list