5

(Background: Trying to learn Haskell, very new to functional programming. Typically used to Python.)

Suppose I have a list of 2-tuples, a histogram:

let h = [(1,2),(3,5),(4,6),(5,3),(6,7),(7,4),(8,6),(9,1)]

In imperative terms, I want to change the second term of each pair to be the sum of all the previous second pairs. In Python, the following (admittedly complex) list comprehension could do it:

[(p[0], sum( [p[1] for p in histogram[:i+1]] )) for i, p in enumerate(histogram)]

assuming histogram refers to a list of 2-tuples like h above.

Here's what I have so far in Haskell:

zip [fst p | p <- h] (scanl1 (+) [snd k | k <- h])

This works, but I wonder:

  • Is this reading through the list once, or twice?
  • Can it be expressed better? (I expect so.)

In case it isn't clear, this is the expected output for the above:

[(1,2),(3,7),(4,13),(5,16),(6,23),(7,27),(8,33),(9,34)]
Improve this question
1
  • 1
    Your Haskell is pretty similar to what I'd write initially, and I think it is pretty clear; certainly easier to approach than the lens or bifunctor approach. However, yes, it does walk the list multiple times. Commented Apr 3, 2014 at 17:51

3 Answers 3

Reset to default
11

You could use this function

accumulate = scanl1 step where step (_,acc) (p1,p2) = (p1,acc+p2)

Here is the result on your sample data:

*Main> accumulate h [(1,2),(3,7),(4,13),(5,16),(6,23),(7,27),(8,33),(9,34)]
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

That is correct - if you don't discard the first values you don't need to put them back again. It is simpler to just write accumulate = scanl1 step though.
@duplode Did not know that function. Answer updated, thank you.
Excellent! Very readable, too. Don't know why I'm trying to make everything in Haskell harder than it really is. :)
@Two-BitAlchemist I guess it is a necessary phase :-D
5

If you're new to Haskell this might be a little too early, but lens offers a nice succinct way:

> scanl1Of (traverse . _2) (+) h [(1,2),(3,7),(4,13),(5,16),(6,23),(7,27),(8,33),(9,34)]

You can easily accumulate only the first one by switching to _1:

> scanl1Of (traverse . _1) (+) h [(1,2),(4,5),(8,6),(13,3),(19,7),(26,4),(34,6),(43,1)]

Or accumulate all values as a sort of nested list:

> scanl1Of (traverse . both) (+) h [(1,3),(6,11),(15,21),(26,29),(35,42),(49,53),(61,67),(76,77)]
Improve this answer

Comments

4

Well,... (,) is a Data.Bifunctor and Data.Biapplicative

scanl1 (biliftA2 (flip const) (+))

is what you want.

A Functor is such a type f that for any a can apply any function a->b to f a to get f b. For example, (a,) is a Functor: there is a way to apply any function b->c to translate (a,b) to (a,c).

fmap f (x,y) = (x,f y)

A Bifunctor is such a type f that for any a and b can apply two functions a->c and b->d to f a b to get f c d. For example, (,) is a Bifunctor: there is a way to apply any pair of functions a->c and b->d to translate (a,b) into (c,d).

bimap f g (x,y) = (f x, g y)

A Biapplicative is such a type f that for any a and b can apply f (a->c) (b->d) to f a b to get f c d. For example, (,) is a Biapplicative: there is a way to apply any functions in the pair to translate (a,b) into (c,d)

biap (f,g) (x,y) = (f x, g y)

Data.Biapplicative defines biliftA2 to "lift" a pair of functions a->c->e and b->d->f - constructs a function of two arguments of type (a,b) and (c,d)

biliftA2 f g = \(x,y) (z,t) -> (f x z, g y t)

So biliftA2 constructs a function that can be used in scanl1 to do the necessary folding. flip const will ignore the first projection of the previous pair, and (+) will add up the second projection of the previous and next pair.

Improve this answer

4 Comments

Can you explain this one a bit more? I know I've accepted an answer, but I'm still learning from the other answers here, and I'm not sure how to read yours.
@Two-BitAlchemist I added more, let me know if you need more detail.
Wow, that was like math class! :) Are functor, bifunctor, and biapplicative typeclasses? Or are they just useful distinctions? Also, I'm still not sure I know what flip const does. Thanks again for all the extra detail. Glad I finally got a chance to read it through and soak it all in!
@Two-BitAlchemist yes, they are typeclasses. flip flips over the arguments of the given function. const ignores the second argument. flip const flips the arguments of const, so now the first argument gets ignored, and the second is returned as-is. flip const is the same as const id.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.