[Haskell-beginners] Again on List Manipulation
Daniel Fischer
daniel.is.fischer at web.de
Sun Sep 12 08:52:48 EDT 2010
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)
More information about the Beginners
mailing list