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

[aditya siram]

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 <nemesisdesign at gmail.com> 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. <costello at mitre.org>
> 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
> --
> Michael Xavier
> http://www.michaelxavier.net
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>