Magicloud Magiclouds | 25 Sep 08:51 2012
Picon

How to take a minimum sub list that only contain certain number of elements of certain type?

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.
--

-- 
竹密岂妨流水过
山高哪阻野云飞

And for G+, please use magiclouds#gmail.com.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Ivan Lazar Miljenovic | 25 Sep 09:11 2012
Picon

Re: 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.magiclouds <at> 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 <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic <at> gmail.com
http://IvanMiljenovic.wordpress.com

_______________________________________________
Haskell-Cafe mailing list
(Continue reading)

Alejandro Serrano Mena | 25 Sep 10:02 2012
Picon

Re: 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.miljenovic <at> gmail.com>
On 25 September 2012 16:51, Magicloud Magiclouds
<magicloud.magiclouds <at> 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 <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



--
Ivan Lazar Miljenovic
Ivan.Miljenovic <at> gmail.com
http://IvanMiljenovic.wordpress.com

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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Richard O'Keefe | 26 Sep 00:09 2012
Picon

Re: How to take a minimum sub list that only contain certain number of elements of certain type?

> 2012/9/25 Ivan Lazar Miljenovic <ivan.miljenovic <at> gmail.com>
> On 25 September 2012 16:51, Magicloud Magiclouds
> <magicloud.magiclouds <at> 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.
Jon Fairbairn | 25 Sep 11:16 2012
X-Face
Picon
Picon

Re: How to take a minimum sub list that only contain certain number of elements of certain type?

Magicloud Magiclouds <magicloud.magiclouds <at> 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.Fairbairn <at> cl.cam.ac.uk

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Rishabh Jain | 25 Sep 19:42 2012

Re: 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 <at> haskell.org
> From: jon.fairbairn <at> 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.magiclouds <at> 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.Fairbairn <at> cl.cam.ac.uk
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Gwern Branwen | 25 Sep 19:56 2012
Picon

Re: 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 <rishabh11 <at> 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
Ivan Lazar Miljenovic | 25 Sep 23:24 2012
Picon

Re: 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 <gwern0 <at> gmail.com> wrote:
> On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain <rishabh11 <at> 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 <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic <at> gmail.com
http://IvanMiljenovic.wordpress.com
Richard O'Keefe | 26 Sep 02:17 2012
Picon

Re: 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 <rishabh11 <at> 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*.
Gwern Branwen | 26 Sep 02:28 2012
Picon

Re: 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 <ok <at> 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
Richard O'Keefe | 26 Sep 02:45 2012
Picon

Re: 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 <ok <at> 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.
Gwern Branwen | 26 Sep 02:59 2012
Picon

Re: 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 <ok <at> 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

Gmane