[Haskell-cafe] Mapping over multiple values of a list at once?
Hi, Imagine you have a list with n-values. You are asked to iterate over the list and calculate the average value of each 3 neighbouring values. For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? The naive ansatz to use (!!) excessively sounds pretty inefficient. Bye, Lenny ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
transpose tails, I guess. hask...@kudling.de wrote: Hi, Imagine you have a list with n-values. You are asked to iterate over the list and calculate the average value of each 3 neighbouring values. For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? The naive ansatz to use (!!) excessively sounds pretty inefficient. Bye, Lenny ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
Right. How about: f = map ((`div` 3) . sum . take 3) . tails You probably want to do filter out some of the tails. Not sure where transpose comes into play, but tails is your friend here. Martijn. Miguel Mitrofanov wrote: transpose tails, I guess. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
Not sure where transpose comes into play, My original attempt was transpose . take 3 . tails. There's more than one way to do the job... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
My first approach would be to generate the list of sliding windows: [[4,3,2],[3,2,6],[2,6,7]] after importing Data.List: map (take 3) . tails $ [4,3,2,6,7] [[4,3,2],[3,2,6],[2,6,7],[6,7],[7],[]] Not quite what we want, but close: filter ((== 3) . length) . map (take 3) . tails $ [4,3,2,6,7] [[4,3,2],[3,2,6],[2,6,7]] So (filter ((== 3) . length) . map (take 3) . tails) seems to be the desired function. Now just map average. However, we don't really need the sliding windows themselves, just the sliding sum. There might be a slightly more efficient way to do that, but I'll leave it as an exercise for you or somebody else. --Max On Thu, Aug 27, 2009 at 10:19 AM, hask...@kudling.de wrote: Hi, Imagine you have a list with n-values. You are asked to iterate over the list and calculate the average value of each 3 neighbouring values. For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? The naive ansatz to use (!!) excessively sounds pretty inefficient. Bye, Lenny ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
tails seems to be the key. I haven't thought of this before. Thanks for pointing me in the right direction, guys. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
tails seems to be the key. I haven't thought of this before. Thanks for pointing me in the right direction, guys. For a more interesting solution: http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html I believe you can adapt his 'rule' function to your problem. It's probably overkill, but good learning material =) Have fun! -- Ariel J. Birnbaum ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? It's probably less elegant than tails, but very likely more efficient to keep track of running sums instead of summing the sublists over and over again. import Data.Ratio nsums n xs = map (% n) $ scanl (+) (sum (take n xs)) $ zipWith (-) (drop n xs) xs Gergely -- http://www.fastmail.fm - The professional email service ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
How about this one? Should be pretty efficient. let mavg n xs = let (sum - seed,rest) = splitAt n xs in map (%n) . scanl (\a (p,n) - a+n-p) seed $ xs `zip` rest 2009/8/27 Patai Gergely patai_gerg...@fastmail.fm: For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? It's probably less elegant than tails, but very likely more efficient to keep track of running sums instead of summing the sublists over and over again. import Data.Ratio nsums n xs = map (% n) $ scanl (+) (sum (take n xs)) $ zipWith (-) (drop n xs) xs Gergely -- http://www.fastmail.fm - The professional email service ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
Just wondering, what should be the expected output be of something like mavg 4 [1..3]? [3%2] or []? Patai's and Eugene's solutions assume the former. On Thu, Aug 27, 2009 at 10:19 AM, hask...@kudling.de wrote: Hi, Imagine you have a list with n-values. You are asked to iterate over the list and calculate the average value of each 3 neighbouring values. For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? The naive ansatz to use (!!) excessively sounds pretty inefficient. Bye, Lenny ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
Or, when the list is infinite, turn it into a some neat but cryptic State computation: avgs = (:) $ ((\d - sum d `div` 3) $ StateT (pure . splitAt 3)) * avgs test = evalState avgs [1,2..] -- Sebastiaan Visser On Aug 27, 2009, at 11:19 AM, Eugene Kirpichov wrote: How about this one? Should be pretty efficient. let mavg n xs = let (sum - seed,rest) = splitAt n xs in map (%n) . scanl (\a (p,n) - a+n-p) seed $ xs `zip` rest 2009/8/27 Patai Gergely patai_gerg...@fastmail.fm: For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? It's probably less elegant than tails, but very likely more efficient to keep track of running sums instead of summing the sublists over and over again. import Data.Ratio nsums n xs = map (% n) $ scanl (+) (sum (take n xs)) $ zipWith (-) (drop n xs) xs Gergely ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Mapping over multiple values of a list at once?
Hello Sebastiaan, Thursday, August 27, 2009, 3:49:48 PM, you wrote: you also need to replace (\d - sum d `div` 3) with (`div` 3) . sum in order to keep Haskell spirit :) Or, when the list is infinite, turn it into a some neat but cryptic State computation: avgs = (:) $ ((\d - sum d `div` 3) $ StateT (pure . splitAt 3)) * avgs test = evalState avgs [1,2..] -- Sebastiaan Visser On Aug 27, 2009, at 11:19 AM, Eugene Kirpichov wrote: How about this one? Should be pretty efficient. let mavg n xs = let (sum - seed,rest) = splitAt n xs in map (%n) . scanl (\a (p,n) - a+n-p) seed $ xs `zip` rest 2009/8/27 Patai Gergely patai_gerg...@fastmail.fm: For example, starting from [4,3,2,6,7] you need to find the averages of 4,3,2 and 3,2,6 and 2,6,7 resulting in [3,4,5] What is the most elegant way to do that? It's probably less elegant than tails, but very likely more efficient to keep track of running sums instead of summing the sublists over and over again. import Data.Ratio nsums n xs = map (% n) $ scanl (+) (sum (take n xs)) $ zipWith (-) (drop n xs) xs Gergely ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mapping over multiple values of a list at once?
Hi Max How about a paramorphism? slideAvg3 :: [Int] - [Int] slideAvg3 = para phi [] where phi x ((y:z:_),acc) = average3 x y z : acc phi x (_,acc) = acc -- helpers -- paramorphism (generalizes catamorphism (fold)) para :: (a - ([a], b) - b) - b - [a] - b para phi b [] = b para phi b (x:xs) = phi x (xs, para phi b xs) average3 :: Int - Int - Int - Int average3 a b c = round $ (fromIntegral $ a+b+c)/3 I haven't tested for efficiency though. Best wishes Stephen 2009/8/27 Max Rabkin max.rab...@gmail.com: However, we don't really need the sliding windows themselves, just the sliding sum. There might be a slightly more efficient way to do that, but I'll leave it as an exercise for you or somebody else. --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
