Geek Answers Handbook

Convert a list of 2 sets to Haskell

(Background: The attempt to learn Haskell is very new to functional programming. Commonly used for 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 mandatory terms, I want to change the second member of each pair as the sum of all the previous second pairs. In Python, this can do the following (admittedly, complex) list comprehension:

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

Assuming the histogram refers to a list of 2 tuples, such as h above.

Here is what I still have in Haskell:

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

This works, but I wonder:

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

If this is not clear, this is the expected result for the above:

 [(1,2),(3,7),(4,13),(5,16),(6,23),(7,27),(8,33),(9,34)]
+6
source share
3 answers

You can use this function

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

Here is the result according to your data:

 *Main> accumulate h [(1,2),(3,7),(4,13),(5,16),(6,23),(7,27),(8,33),(9,34)]
+11
source

If you are new to Haskell, this might be too early, but lens offers a nice concise way:

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

You can easily copy only the first 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 copy all the values ​​as a nested list:

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

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

 scanl1 (biliftA2 (flip const) (+))

- Is this what you want.

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

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

A Bifunctor is such a type f that for any a and b you can apply two functions a->c and b->d to fab to get fcd . 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 fg (x,y) = (fx, gy)

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

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

Data.Biapplicative defines biliftA2 for “lifting” a pair of functions a->c->e and b->d->f - it builds a function from two arguments of type (a,b) and (c,d)

 biliftA2 fg = \(x,y) (z,t) -> (fxz, gyt)

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

+4
source

More articles:


All Articles