[Haskell-beginners] Creating beautiful code: can you make this divide-and-conquer implementation of the "tails" function beautiful?

[KC]

Richard Bird in Chapter 2 "A Surpassing Problem" of "Pearls of
Functional Algorithm Design" creates a tails function that returns the
nonempty tails from a nonempty list in decreasing order of length; the
prelude (or Data.List) tails function returns the possibly empty tails
of a possibly empty list.

Bird defines tails as
tails [] = []
tails (x:xs) = (x : xs) : tails xs

Only to use the following property of the function

tails (xs ++ ys) = map (++ ys) (tails xs) ++ tails ys

to derive the final algorithm; which I believe doesn't use tails but
uses this idea of what Bird's tails function does.

He doesn't use a divide and conquer method for tails but the final
algorithm uses a divide and conquer algorithm for the surpassing
problem.


On Tue, Jun 28, 2011 at 6:30 AM, Costello, Roger L. <costello at mitre.org> wrote:
>> Why would you want to take such a complicated approach to such a trivial problem?
>
> I am dissecting Chapter 2 of Pearls of Functional Algorithm Design.  By implementing the "tails" function in this divide-and-conquer method, the author is able to create a fascinating algorithm.
>
> /Roger
>
> -----Original Message-----
> From: David Place [mailto:d at vidplace.com]
> Sent: Tuesday, June 28, 2011 9:26 AM
> To: Costello, Roger L.
> Cc: beginners at haskell.org
> Subject: Re: [Haskell-beginners] Creating beautiful code: can you make this divide-and-conquer implementation of the "tails" function beautiful?
>
> On Jun 28, 2011, at 7:43 AM, Costello, Roger L. wrote:
>
>> Note: I am trying to clean up this divide-and-conquer algorithm, not create a different algorithm. Sorry that I wasn't clear about this in my initial message.
>
> Perhaps the problem in the code is this choice of approach.  Why would you want to take such a complicated approach to such a trivial problem?  Especially since it's also less efficient.
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
--
Regards,
KC