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@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@vidplace.com] Sent: Tuesday, June 28, 2011 9:26 AM To: Costello, Roger L. Cc: beginners@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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- -- Regards, KC