[Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?

Richard O'Keefe ok at cs.otago.ac.nz
Wed Sep 26 00:09:03 CEST 2012

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

More information about the Haskell-Cafe mailing list