[Haskell-beginners] Avoid Case Analyses

[Patrick Redmond]

Without speaking to the point of whether case analysis introduces
unnecessary complication, I think truncate is a poor choice of example to
demonstrate this idea. As Mike deftly demonstrated we can write a simple
constant-time function which implements floor, while Roger's final version
is a non-intuitive time-inefficient linear search over the integers.

Perhaps a more complicated problem would better demonstrate Richard Bird's
quotation, however, in general I think case analysis is a very useful tool
when it illuminates the problem (as in a function over a recursive data
structure (see treeInsert on
http://learnyouahaskell.com/making-our-own-types-and-typeclasses)).

-- Patrick


On Mon, Oct 8, 2012 at 6:30 AM, Mike Meyer <mwm at mired.org> wrote:

> On Sun, 7 Oct 2012 09:47:32 +0000
> "Costello, Roger L." <costello at mitre.org> wrote:
>
> > Hi Folks,
> >
> > "Programs that avoid case analyses are clearer and simpler than those
> that use case analyses."
>
> I'm not convinced. Here's the critical bits:
>
> > 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.
>
> A nice straw man implementation.
>
> > 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.
>
> Right, this is the natural way to do it with case analysis.
>
> > 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
> >[...]
> > The case analysis version is longer and arguably more complex.
>
> Let's see - you constructed a set of primitives specifically designed
> to avoid case analysis, and when you use those to create a solution
> that is only "arguably more complex". Would you let me get away with
> arguing that an imperative solution was better if I forced you to use
> imperative primitives in a functional version?
>
> If you follow that original case analysis urge, you get this version:
>
> floor x = truncate x - if x < 0 then 1 else 0
>
> Clearly shorter and less complex than any either of your two
> versions. Further, it actually, doesn't include any more case
> analysis, as it has the same "if" that is hidden in the "until"
> primitive in the version without case analysis.
>
>       <mike
> --
> Mike Meyer <mwm at mired.org>              http://www.mired.org/
> Independent Software developer/SCM consultant, email for more information.
>
> O< ascii ribbon campaign - stop html mail - www.asciiribbon.org
>
> _______________________________________________
> 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/20121008/fa541134/attachment.htm>