[Haskell-beginners] Creating beautiful code: can you make this divide-and-conquer implementation of the "tails" function beautiful?
kc1956 at gmail.com
Tue Jun 28 16:42:34 CEST 2011
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
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.
> -----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
More information about the Beginners