CODEWITHSUNDEEP
haskell
Two-Bit Alchemist
Two-Bit Alchemist

Reputation: 18457

Transforming a List of 2-Tuples in Haskell

(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:

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)]

Upvotes: 5

Views: 884

Answers (3)

Sassa NF
Sassa NF

Reputation: 5406

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.

Upvotes: 4

Markus1189
Markus1189

Reputation: 2869

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)]

Upvotes: 5

Lee Duhem
Lee Duhem

Reputation: 15121

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)]

Upvotes: 11

Related Questions