2012/9/25 Ivan Lazar Miljenovic On 25 September 2012 16:51, Magicloud Magiclouds 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.

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.fairbairn@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 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.Fairbairn@cl.cam.ac.uk

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 26 September 2012 03:56, Gwern Branwen wrote:

On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain 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.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

On Tue, Sep 25, 2012 at 8:17 PM, Richard O'Keefe 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

On Tue, Sep 25, 2012 at 8:45 PM, Richard O'Keefe 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