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

[Costello, Roger L.]

Thanks Michael, using the as-pattern (@) makes the algorithm cleaner:

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

I tried using the specific patterns you provided:

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

Those patterns would make it even more elegant. However, that didn't work - the compiler went into an infinite loop. What am I missing?

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.

/Roger

From: Michael Xavier [mailto:nemesisdesign at gmail.com] 
Sent: Monday, June 27, 2011 9:17 PM
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?

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