Haskell get a filtered List of integers

Question

Scenario: If there is an array of integers and I want to get array of integers in return that their total should not exceed 10.

I am a beginner in Haskell and tried below. If any one could correct me, would be greatly appreciated.

numbers :: [Int]
numbers = [1,2,3,4,5,6,7,8,9,10, 11, 12]

getUpTo :: [Int] -> Int -> [Int]
getUpTo (x:xs) max =
    if max <= 10
    then
            max = max + x
            getUpTo xs max
    else
            x

Input

getUpTo numbers 0

Output Expected

[1,2,3,4]

Answer 1

I am fairly new to Haskell. I just started with it a few hours ago and as such I see in every question a challenge that helps me get out of the imperative way of thinking and a opportunity to practice my recursion thinking :)

I gave some thought to the question and I came up with this, perhaps, naive solution:

upToBound :: (Integral a) => [a] -> a -> [a]
upToBound (x:xs) bound = 
        let
                summation _ []  = []
                summation n (m:ms)  
                        | n + m <= bound = m:summation (n + m) ms 
                        | otherwise = []
        in
                summation 0 (x:xs)                

I know there is already a better answer, I just did it for the fun of it.

I have the impression that I changed the signature of the original invocation, because I thought it was pointless to provide an initial zero to the outer function invocation, since I can only assume it can only be zero at first. As such, in my implementation I hid the seed from the caller and provided, instead, the maximum bound, which is more likely to change.

upToBound [1,2,3,4,5,6,7,8,9,0] 10

Which outputs: [1,2,3,4]

Answer 2

For educational purposes (and since I felt like explaining something :-), here's a different version, which uses more standard functions. As written it is slower, because it computes a number of sums, and doesn't keep a running total. On the other hand, I think it expresses quite well how to break the problem down.

getUpTo :: [Int] -> [Int]
getUpTo = last . filter (\xs -> sum xs <= 10) . Data.List.inits

I've written the solution as a 'pipeline' of functions; if you apply getUpTo to a list of numbers, Data.List.inits gets applied to the list first, then filter (\xs -> sum xs <= 10) gets applied to the result, and finally last gets applied to the result of that.

So, let's see what each of those three functions do. First off, Data.List.inits returns the initial segments of a list, in increasing order of length. For example, Data.List.inits [2,3,4,5,6] returns [[],[2],[2,3],[2,3,4],[2,3,4,5],[2,3,4,5,6]]. As you can see, this is a list of lists of integers.

Next up, filter (\xs -> sum xs <= 10) goes through these lists of integer in order, keeping them if their sum is less than 10, and discarding them otherwise. The first argument of filter is a predicate which given a list xs returns True if the sum of xs is less than 10. This may be a bit confusing at first, so an example with a simpler predicate is in order, I think. filter even [1,2,3,4,5,6,7] returns [2,4,6] because that are the even values in the original list. In the earlier example, the lists [], [2], [2,3], and [2,3,4] all have a sum less than 10, but [2,3,4,5] and [2,3,4,5,6] don't, so the result of filter (\xs -> sum xs <= 10) . Data.List.inits applied to [2,3,4,5,6] is [[],[2],[2,3],[2,3,4]], again a list of lists of integers.

The last step is the easiest: we just return the last element of the list of lists of integers. This is in principle unsafe, because what should the last element of an empty list be? In our case, we are good to go, since inits always returns the empty list [] first, which has sum 0, which is less than ten - so there's always at least one element in the list of lists we're taking the last element of. We apply last to a list which contains the initial segments of the original list which sum to less than 10, ordered by length. In other words: we return the longest initial segment which sums to less than 10 - which is what you wanted!

If there are negative numbers in your numbers list, this way of doing things can return something you don't expect: getUpTo [10,4,-5,20] returns [10,4,-5] because that is the longest initial segment of [10,4,-5,20] which sums to under 10; even though [10,4] is above 10. If this is not the behaviour you want, and expect [10], then you must replace filter by takeWhile - that essentially stops the filtering as soon as the first element for which the predicate returns False is encountered. E.g. takeWhile [2,4,1,3,6,8,5,7] evaluates to [2,4]. So in our case, using takeWhile stops the moment the sum goes over 10, not trying longer segments.

By writing getUpTo as a composition of functions, it becomes easy to change parts of your algorithm: if you want the longest initial segment that sums exactly to 10, you can use last . filter (\xs -> sum xs == 10) . Data.List.inits. Or if you want to look at the tail segments instead, use head . filter (\xs -> sum xs <= 10) . Data.List.tails; or to take all the possible sublists into account (i.e. an inefficient knapsack solution!): last . filter (\xs -> sum xs <= 10) . Data.List.sortBy (\xs ys -> length xscomparelength ys) . Control.Monad.filterM (const [False,True]) - but I'm not going to explain that here, I've been rambling long enough!

Answer 3

There is an answer with a fast version; however, I thought it might also be instructive to see the minimal change necessary to your code to make it work the way you expect.

numbers :: [Int]
numbers = [1,2,3,4,5,6,7,8,9,10, 11, 12]

getUpTo :: [Int] -> Int -> [Int]
getUpTo (x:xs) max =
    if max < 10 -- (<), not (<=)
    then
            -- return a list that still contains x;
            -- can't reassign to max, but can send a
            -- different value on to the next
            -- iteration of getUpTo
            x : getUpTo xs (max + x)
    else
            [] -- don't want to return any more values here

Answer 4

BEWARE: This is not a solution to the knapsack problem :)

A very fast solution I came up with is the following one. Of course solving the full knapsack problem would be harder, but if you only need a quick solution this should work:

import Data.List (sort)

getUpTo :: Int -> [Int] -> [Int]
getUpTo max xs = go (sort xs) 0 []
    where
        go [] sum acc         = acc
        go (x:xs) sum acc
            | x + sum <= max  = go xs (x + sum) (x:acc)
            | otherwise       = acc

By sorting out the array before everything else, I can take items from the top one after another, until the maximum is exceeded; the list built up to that point is then returned.

edit: as a side note, I swapped the order of the first two arguments because this way should be more useful for partial applications.