Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 25 September 2012 16:51, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. If you have listTest :: [a] - Bool, then head . dropWhile (not . listTest) . inits ? How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. -- 竹密岂妨流水过 山高哪阻野云飞 And for G+, please use magiclouds#gmail.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
It also comes to my mind that you can use something similar to regular expressions and parsing, seeing your list as a word made of Int elements. I think you can achieve it using Parsec or attoparsec. One you define your basic combinators for 'odd', you can see your sublist as the minimal part of the list matching (even* odd)(even* odd)(even* odd)(even* odd) 2012/9/25 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com On 25 September 2012 16:51, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. If you have listTest :: [a] - Bool, then head . dropWhile (not . listTest) . inits ? How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. -- 竹密岂妨流水过 山高哪阻野云飞 And for G+, please use magiclouds#gmail.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ 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] How to take a minimum sub list that only contain certain number of elements of certain type?
Magicloud Magiclouds magicloud.magiclo...@gmail.com writes: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. Does f bound odds_so_far [] = [] f bound odds_so_far (x:xs) | odds_so_far == bound = [] | otherwise = x : f bound (odds_so_far + if odd x then 1 else 0) xs required_funciton = f 4 0 meet your criteria, or am I missing something? -- Jón Fairbairn jon.fairba...@cl.cam.ac.uk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
f x 0 = []f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] To: haskell-cafe@haskell.org From: jon.fairba...@cl.cam.ac.uk Date: Tue, 25 Sep 2012 10:16:52 +0100 Subject: Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type? Magicloud Magiclouds magicloud.magiclo...@gmail.com writes: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. Does f bound odds_so_far [] = [] f bound odds_so_far (x:xs) | odds_so_far == bound = [] | otherwise = x : f bound (odds_so_far + if odd x then 1 else 0) xs required_funciton = f 4 0 meet your criteria, or am I missing something? -- Jón Fairbairn jon.fairba...@cl.cam.ac.uk ___ 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] How to take a minimum sub list that only contain certain number of elements of certain type?
On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain rishab...@live.com wrote: f x 0 = [] f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] Tsk, tsk. So ugly. How's this: let f x = take x . filter odd f 4 [0..] ~ [1, 3, 5, 7] Notice that 0 is excluded, since 0 is *even*, not odd: http://en.wikipedia.org/wiki/Parity_of_zero If this is a serious problem, one can always just prepend zero: 0 : f 4 [1..] ~ [0, 1, 3, 5, 7] -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 26 September 2012 03:56, Gwern Branwen gwe...@gmail.com wrote: On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain rishab...@live.com wrote: f x 0 = [] f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] Tsk, tsk. So ugly. How's this: let f x = take x . filter odd f 4 [0..] ~ [1, 3, 5, 7] Notice that 0 is excluded, since 0 is *even*, not odd: http://en.wikipedia.org/wiki/Parity_of_zero If this is a serious problem, one can always just prepend zero: 0 : f 4 [1..] ~ [0, 1, 3, 5, 7] Except that your solution is incorrect, as Magicloud wanted the smallest _prefix_ that contained four odd numbers... -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
2012/9/25 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com On 25 September 2012 16:51, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. What do you actually *mean*? When you say you have an array, but actually display a *list*, do you really mean you have something fitting into Data.Array, or do you really mean you have a list? When you say sub list do you mean a *slice* (a contiguous chunk) or a *subsequence* (elements preserve their order but there may be gaps). Or looking at your example, do you mean a *prefix* (n `take` xs for some n)? When you say odds I presume you mean odd integer, although the even/odd concept applies to Gaussian integers too (m+ni is even if it is divisible by 1+i, which turns out to be equivalent to m+ni being even (odd) iff m and n have the same (different) parity). When you say is minimum result, what does that mean? Does it mean the sum of the elements is minimal? (If you consider the list [1,3,5,7,-2,-4,-6,-8,-10,...] it is clear that a minimum result in that sense could be infinitely long.) Let's take just one interpretation: - the array is a list - whose elements are Integers - the result must be a prefix of the input - which contains four odd Integers - and is otherwise as short as possible. We'll generalise `take`: it will have an integer n, a predicate p, and a list xs. ptake :: Int - (a - Bool) - [a] - [a] ptake n p (x:xs) | n 0 = x : ptake (if p x then n-1 else n) p xs ptake _ _ _ = [] answer :: [Integer] - [Integer] answer xs = ptake 4 odd xs Now this is pretty trivial (it's _exactly_ `take` except for only counting elements where p is true), so that interpretation of the problem cannot be the right one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 26/09/2012, at 5:56 AM, Gwern Branwen wrote: On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain rishab...@live.com wrote: f x 0 = [] f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] Tsk, tsk. So ugly. How's this: let f x = take x . filter odd Wrong. The original poster gave an explicit example in which even elements were *retained* in the output, they just weren't *counted*. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On Tue, Sep 25, 2012 at 8:17 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: Wrong. The original poster gave an explicit example in which even elements were *retained* in the output, they just weren't *counted*. You are at least the fourth person to email me now to point this out. I'm glad I could make four people's day better with the joy of correction... But I never said it was a full solution - please note that I did include the output of the function! One could consider it a partial solution, however: that gives you the _nth_ odd, so if you want a list of numbers up to the _nth_ odd, that gives you a stop condition - 'takeWhile =/ nth+1' etc. A 2N traverse (which laziness might fuse to just 1 traverse, dunno). -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 26/09/2012, at 12:28 PM, Gwern Branwen wrote: On Tue, Sep 25, 2012 at 8:17 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: Wrong. The original poster gave an explicit example in which even elements were *retained* in the output, they just weren't *counted*. You are at least the fourth person to email me now to point this out. I'm glad I could make four people's day better with the joy of correction... But I never said it was a full solution - please note that I did include the output of the function! The tsk tsk is probably what made people so keen to reply. One could consider it a partial solution, however: that gives you the _nth_ odd, so if you want a list of numbers up to the _nth_ odd, that gives you a stop condition - 'takeWhile =/ nth+1' etc. That doesn't work either. Consider the list [1,1,1,1,1]. The element just after the 5th odd number in the list is 1; takeWhile (/= 1) will thus return [] instead of [1,1,1,1]. |A 2N traverse (which laziness might fuse to just 1 traverse, dunno). Not in this case, for fairly obvious reasons. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On Tue, Sep 25, 2012 at 8:45 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: That doesn't work either. Consider the list [1,1,1,1,1]. The element just after the 5th odd number in the list is 1; takeWhile (/= 1) will thus return [] instead of [1,1,1,1]. I'm not sure that OP would prefer [1,1,1,1] to []. Another area of underspecification. -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
