Haskell get filtered list of integers
Scenario: If there is an array of integers, and I want to get an array of integers, in turn, that their sum should not exceed 10.
I am new to Haskell and have tried below. If someone could fix me, we would be very grateful.
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
Expected Result
[1,2,3,4]
source to share
There is an answer with a quick version; however, I thought it would also be instructive to see the minimum changes required to your code to make it work as 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
source to share
BEWARE: This is not a solution to the backpack problem :)
The very quick solution I came up with is the following. Of course, solving the problem with a full backpack would be more difficult, but if you only want 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 matching the array in front of everything else, I can take the elements from the top one by one until the maximum is exceeded; the list generated for that point is then returned.
edit: as a side note, I changed the order of the first two arguments because it should be more useful for partial applications.
source to share
For educational purposes (and since I wanted to explain something :-), here's a different version that uses more standard functions. As written, it is slower because it calculates multiple sums and does not store the total. On the other hand, I think he talks pretty well about how to break the problem.
getUpTo :: [Int] -> [Int] getUpTo = last . filter (\xs -> sum xs <= 10) . Data.List.inits
I wrote the solution as a "pipeline" of functions; if you apply getUpTo
to a list of numbers, it will first be applied Data.List.inits
to the list, then it filter (\xs -> sum xs <= 10)
will be applied to the result, and finally it last
will be applied to the result of that.
So let's see what each of these three functions does. First, it Data.List.inits
returns the starting segments of the list in ascending order of length. For example, it 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, it filter (\xs -> sum xs <= 10)
goes through these lists of integers in order, storing them if their sum is less than 10 and discarding them otherwise. The first argument filter
is a predicate that specifies a list xs
, returns True
if the sum is xs
less than 10. This can be a bit confusing at first, so an example with a simpler predicate is fine I think. filter even [1,2,3,4,5,6,7]
returns [2,4,6]
because these are even values in the original list. In the earlier example, the lists []
, [2]
, [2,3]
and [2,3,4]
have a total of less than 10, but [2,3,4,5]
and [2,3,4,5,6]
not, therefore, the result filter (\xs -> sum xs <= 10) . Data.List.inits
is applied to [2,3,4,5,6]
[[],[2],[2,3],[2,3,4]]
, again, the list of lists of integers.
The last step is the simplest: we just return the last element of the list of lists of integers. Is this basically unsafe because there must be the last element of an empty list? In our case, we're good to go as it inits
first returns an empty list []
that has a sum of 0, which is less than ten, so there is always at least one element in the list of lists that we are taking the last element. We apply last
to a list that contains the starting segments of the original list that are less than 10 in sum, ordered by length. In other words: we are returning the longest starting segment that has a sum less than 10 - which is what you wanted!
If you numbers
have negative numbers in your list , this way of doing things might return something you don't expect: it getUpTo [10,4,-5,20]
returns [10,4,-5]
because this is the longest start segment [10,4,-5,20]
that adds up to 10 years; even if [10,4]
higher than 10. If this is not the behavior you want and expect [10]
, then you should replace filter
with takeWhile
- this, in fact, stops filtering as soon as the first element for which the predicate returns False
. For example. takeWhile [2,4,1,3,6,8,5,7]
evaluated before [2,4]
. Thus, in our case, the use takeWhile
stops the moment when the amount moves by 10, and not to longer segments.
Writing getUpTo
as a set of functions, it's easy to change parts of your algorithm: if you want the longest start segment to be exactly 10, you can use last . filter (\xs -> sum xs == 10) . Data.List.inits
. Or, if you want to look at tail segments, use head . filter (\xs -> sum xs <= 10) . Data.List.tails
; or take into account all possible sublists (i.e. ineffective backpack solution!): last . filter (\xs -> sum xs <= 10) . Data.List.sortBy (\xs ys -> length xs
compare length ys) . Control.Monad.filterM (const [False,True])
- but I'm not going to explain that I've been hanging around here for too long!
source to share
I am new to Haskell. I just started with it a few hours ago, and therefore I see a problem in every question that helps me get out of the imperative way of thinking and the opportunity to practice my recursive thinking :)
I thought about this 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 fun.
I was under the impression that I changed the signature of the original call because I considered it pointless to provide a leading zero to the outer function call, since I can only assume that it can only be zero at the beginning. So, in my implementation, I hid the seed from the caller and provided a maximum bound instead, which is more likely to change.
upToBound [1,2,3,4,5,6,7,8,9,0] 10
What are the outputs: [1,2,3,4]
source to share