Creating beautiful code: can you make this divide-and-conquer implementation of the "tails" function beautiful?
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]]
On Jun 27, 2011, at 4:30 PM, Costello, Roger L. wrote:
Can the function be simplified and made beautiful?
Surely you're teasing us, Dr. Costello.
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@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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- Michael Xavier http://www.michaelxavier.net
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@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@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@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
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@gmail.com] Sent: Monday, June 27, 2011 9:17 PM 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? 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@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@haskell.org http://www.haskell.org/mailman/listinfo/beginners -- Michael Xavier http://www.michaelxavier.net
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.
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.
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
participants (5)
-
aditya siram -
Costello, Roger L. -
David Place -
KC -
Michael Xavier