[Haskell-beginners] Again on List Manipulation

[Daniel Fischer]

On Sunday 12 September 2010 13:57:50, Lorenzo Isella wrote:
> Dear All,
> First of all, thanks to the whole list for their help.
> I am still struggling with things I used to be able to do quite easily
> (though maybe not efficiently) with other languages. I still have to get
> used to the immutable nature of lists and the absence of for loops.
> Let us say you have two lists
>
> l = [1,1,1,1,2,2,2,2,2,2,2,3,3,5,6,7] (already sorted)
>
> and a list of corresponding values for every entry in l
>
> m=  [2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14].
> Also consider the list of the unique values in l
>
> l_un = nub l

If the list is sorted, much better than nub is

l_un = map head $ group l

nub has to check each list element against all (distinct) previous 
elements, hence its complexity is O(n^2) (where n = length l).
Even if the list is not sorted, if the type of its elements belongs to Ord, 
you can write a faster nubOrd (there's a proposal to get that function in 
the standard libraries, I don't know its status, for the time being, you 
have to write your own) of complexity O(n*log n).

>
> Now, what I would like to do is to get a third list, let us call it q,
> such that its length is equal to the length of l_un.
> On top of that, its i-th entry should be the sum of the entries of m
> corresponding to the i-th values of l_un.
> To fix the ideas, q should be
>
> q = [8,32, 8,10,12,14] .
> How would you do that?

map sum . group

if it's guaranteed that different elements of l correspond to different 
values in m. If that's not guaranteed,

import Data.Function (on)
import Data.List

q = map (sum . map snd) . groupBy ((==) `on` fst) $ zip l m


ghci> :t ((map (sum . map snd) . groupBy ((==) `on` fst)) .) . zip
((map (sum . map snd) . groupBy ((==) `on` fst)) .) . zip
  :: (Num b, Eq a) => [a] -> [b] -> [b]

>
> Cheers
>
> Lorenzo
>
> P.S.: I will need this function both with Integer and Double numbers (I
> may have situation in which the entries of one list or both are real
> numbers, though the goal stays the same)