CODEWITHSUNDEEP
haskell
turtle
turtle

Reputation: 8073

How to traverse a list and drop a value incrementally

I have a list that looks like this:

lst = [1,2,6,3,9]

I want to write a function that sums all the numbers in the list and appends this value to a new list, then walk through the list and drop a value one by one and sum the values. The function would perform this computation:

result = [[1+2+6+3+9],
          [1+6+3+9],
          [1+2+3+9],
          [1+2+6+9],
          [1+2+6+3]]

The function I am trying to describe would produce this result given the list example above:

[21,19,15,18,12]

I am having a difficult time understanding how to implement this function in Haskell. Specifically, how to traverse a list, and drop one element but increment the dropped value by one each time. Can anyone help? Thanks. I've been trying to write a helper function that uses a fold, but I can't figure out how to drop a different element from the last upon each "iteration".

Upvotes: 2

Views: 730

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 152682

Mog has given an answer that exploits the fact that (+) is associative, commutative, and has an inverse. However, I think it's also constructive to give an answer that works for any operation; that is, to produce the actual lists you're summing, then sum them. So the plan will be like this:

  1. Write a function that splits a list at each possible position.
  2. Write a function that turns a split back into a list by dropping the element at the split.
  3. Write a function that sums a list (already done in Prelude: use the sum function).
  4. Write a function that combines them, and includes the special case of the entire list.

There's a couple ways to do part one. The first choice is explicit recursion:

splits :: [a] -> [([a], [a])]
splits []     = [([],[])]
splits (x:xs) = ([],x:xs) : map (\(b,e) -> (x:b,e)) (splits xs)

We can check it out in ghci to make sure we've got it right:

*Main> splits "abcde"
[("","abcde"),("a","bcde"),("ab","cde"),("abc","de"),("abcd","e"),("abcde","")]

However, there's a nicer way. The Data.List module includes a bunch of functions for munging lists in particular ways. Two of them are tails and inits:

*Main> tails "abcde"
["abcde","bcde","cde","de","e",""]
*Main> inits "abcde"
["","a","ab","abc","abcd","abcde"]

So this definition is much nicer looking:

splits xs = zip (inits xs) (tails xs)

Now, we want a function that produces the list of lists with one element dropped from each position.

dropEach xs = [beginning ++ end | (beginning, ignored:end) <- splits xs]

So the final step is to put everything together.

funnySums xs = map sum (xs : dropEach xs)

We can test:

*Main> funnySums [1, 10, 100, 1000, 10000]
[11111,11110,11101,11011,10111,1111]

Upvotes: 9

m09
m09

Reputation: 7493

You could write something along those lines:

f xss@(x:xs) = total : map (total -) xs
  where total = sum xss

Basically it says that first you have the sum of your list, then you have for each element this same sum minus this element (and we skip the head).

For more details:

  • (x:xs) is used to pattern match on the given list, so that we can easily skip the head later by only using xs
  • xss@... is used to name the whole pattern so that we can still use the whole list easily
  • the where clause introduces a variable that holds the sum of the list, this way it's not recalculated plenty of times (maybe it'd have been optimized anyway, this way we're sure).
  • (total -) is an operator section: when called with argument x, it'll return total - x

Note: you'd have to precise what happens when this function is given the empty list, for example, if you want it to return the empty list, add:

f [] = []

edit: explanations about map (total -) xs:

as I detailed in my list above, (total -) is an operator section that gives us the following function:

\x -> total - x

it returns the total minus the value it's given.

Now, we map that function on the tail of the list given to f. For example, if you give f the list

[1, 2, 6, 3, 9]

It'll me mapped over

[2, 6, 3, 9]

If total is 21, the result of the map call is

[19, 15, 18, 12] -- [21 - 2, 21 - 6, 21 - 3, 21 - 9]

Upvotes: 12

Related Questions