I think using iterate expresses tails quite elegantly: tails = iterate tail But unfortunately "tail" is unsafe and throws an exception on a empty list: *Main> tails [1,2,3,4] [[1,2,3,4],[2,3,4],[3,4],[4],[],*** Exception: Prelude.tail: empty list To make this correct we can do something like: tails' l = take (length l) (iterate tail l) -- or the points free version -- import Control.Arrow -- tails' = uncurry take . (length &&& iterate tail) but that evaluates the entire list twice needlessly and is certainly not as elegant Seems to me that to do better than the Prelude definition what we really need is a exception safe tail function so "tails = iterate tail" works. -deech On Mon, Jun 27, 2011 at 8:16 PM, Michael Xavier wrote:

I'll bite. The source of tails is pretty elegant:

tails :: [a] -> [[a]] tails [] = [[]] tails xxs@(_:xs) = xxs : tails xs

On Mon, Jun 27, 2011 at 1:30 PM, Costello, Roger L. wrote:

...

Hi Folks,

Below is a divide-and-conquer implementation of the "tails" function.

Notice the two patterns (x:y:xs) and (x:[]). And notice that (x:y:xs) is used by the "length" function and again by the "splitAt" function. That doesn't seem elegant. Can the function be simplified and made beautiful?

/Roger

tails'               ::   [a] -> [[a]] tails' (x:y:xs)   =   map (++zs) (tails' ys) ++ tails' zs                           where m        =  length (x:y:xs)                                       n         =  m `div` 2                                      (ys,zs)  =  splitAt n (x:y:xs) tails' (x:[])      =    [[x]]

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Michael Xavier http://www.michaelxavier.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

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.

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. 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