[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