[Haskell-beginners] Avoid Case Analyses

[damodar kulkarni]

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>