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 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? 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)
El dom, 12-09-2010 a las 13:57 +0200, Lorenzo Isella escribió:
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
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?
First, we build a list that has the wanted correspondence between m and l. The function 'zip' pairs the i-th element of l with the i-th element of m: Prelude Data.List Data.Function> zip l m [(1,2),(1,2),(1,2),(1,2),(2,4),(2,4),(2,4),(2,4),(2,6),(2,6),(2,4),(3,4),(3,4),(5,10),(6,12),(7,14)] then, we group by the value of the entry in l. The function 'groupBy' works just like group, but it allows to specify the predicate by which to group elements, instead of simply using equality (group === groupBy (==)). Here, we want to group pairs if their first component is equal, i.e., our grouping predicate is \(a,b) (c,d) -> a == c or \x y -> fst x == fst y or (==) `on` fst this gives: Prelude Data.List Data.Function> groupBy ((==) `on` fst) $ zip l m [[(1,2),(1,2),(1,2),(1,2)],[(2,4),(2,4),(2,4),(2,4),(2,6),(2,6),(2,4)],[(3,4),(3,4)],[(5,10)],[(6,12)],[(7,14)]] now, we can forget about the l-values. we are only interested in the values of the m list. To do this, we extract the second component of each pair, using the function snd. As these pairs are elements of list, and we want to extract the second component of all of them, we have to 'map' the function 'snd' over these lists. Now, these lists are themselves elements of our list, so we have to 'map' the function 'map snd' over it: Prelude Data.List Data.Function> map (map snd) . groupBy ((==) `on` fst) $ zip l m [[2,2,2,2],[4,4,4,4,6,6,4],[4,4],[10],[12],[14]] Finally, we only have to sum up the values in these lists. The function 'sum' sums up the values in a list, and as we want to do this for all the lists in our list, we simply map it: Prelude Data.List Data.Function> map sum . map (map snd) . groupBy ((==) `on` fst) $ zip l m [8,32,8,10,12,14] The last line can be slightly simplified, because map f . map g === map (f . g) to map (sum . map snd) . groupBy ((==) `on` fst) $ zip l m Jürgen
another solution might be to simply use nub on pairs, after zipping the two
lists. this of course assumes that the mapping between values is consistent.
q = map snd $ nub $ zip l m
On 12 September 2010 13:39, Jürgen Doser
El dom, 12-09-2010 a las 13:57 +0200, Lorenzo Isella escribió:
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
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?
First, we build a list that has the wanted correspondence between m and l. The function 'zip' pairs the i-th element of l with the i-th element of m:
Prelude Data.List Data.Function> zip l m
[(1,2),(1,2),(1,2),(1,2),(2,4),(2,4),(2,4),(2,4),(2,6),(2,6),(2,4),(3,4),(3,4),(5,10),(6,12),(7,14)]
then, we group by the value of the entry in l. The function 'groupBy' works just like group, but it allows to specify the predicate by which to group elements, instead of simply using equality (group === groupBy (==)). Here, we want to group pairs if their first component is equal, i.e., our grouping predicate is
\(a,b) (c,d) -> a == c
or
\x y -> fst x == fst y
or
(==) `on` fst
this gives:
Prelude Data.List Data.Function> groupBy ((==) `on` fst) $ zip l m
[[(1,2),(1,2),(1,2),(1,2)],[(2,4),(2,4),(2,4),(2,4),(2,6),(2,6),(2,4)],[(3,4),(3,4)],[(5,10)],[(6,12)],[(7,14)]]
now, we can forget about the l-values. we are only interested in the values of the m list. To do this, we extract the second component of each pair, using the function snd. As these pairs are elements of list, and we want to extract the second component of all of them, we have to 'map' the function 'snd' over these lists. Now, these lists are themselves elements of our list, so we have to 'map' the function 'map snd' over it:
Prelude Data.List Data.Function> map (map snd) . groupBy ((==) `on` fst) $ zip l m [[2,2,2,2],[4,4,4,4,6,6,4],[4,4],[10],[12],[14]]
Finally, we only have to sum up the values in these lists. The function 'sum' sums up the values in a list, and as we want to do this for all the lists in our list, we simply map it:
Prelude Data.List Data.Function> map sum . map (map snd) . groupBy ((==) `on` fst) $ zip l m [8,32,8,10,12,14]
The last line can be slightly simplified, because
map f . map g === map (f . g)
to
map (sum . map snd) . groupBy ((==) `on` fst) $ zip l m
Jürgen
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- Ozgur Akgun
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)
On 2010-09-12, at 7:57 , 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
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?
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)
Hi, Lorenzo! As you may have gathered, I'm a big fan of list comprehensions. First, I renamed your lists (better readability later on; also, I used bs instead of l, as l is easy to confuse with the vertical stroke character | required in list comprehensions): Prelude Data.List> let bs = [1,1,1,1,2,2,2,2,2,2,2,3,3,5,6,7] Prelude Data.List> let ms = [2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14] Prelude Data.List> let us = nub ls Next, use a list comprehension to give me the same number of elements as in us: Prelude Data.List> [u | u <- us] [1,2,3,5,6,7] Nest a list comprehension inside of that, so that each element now is list ms: Prelude Data.List> [[m | m <- ms] | u <- us] [[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14]] Introduce the elements of list bs, as we will need them for filtering: Prelude Data.List> [[m | (b,m) <- zip bs ms] | u <- us] [[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14],[2,2,2,2,4,4,4,4,6,6,4,4,4,10,12,14]] Filter by comparing the elements of bs and us, ie b == u: Prelude Data.List> [[m | (b,m) <- zip bs ms, b == u] | u <- us] [[2,2,2,2],[4,4,4,4,6,6,4],[4,4],[10],[12],[14]] Finally, sum each list: Prelude Data.List> [sum [m | (b,m) <- zip bs ms, b == u] | u <- us] [8,32,8,10,12,14] Henry
participants (5)
-
Daniel Fischer -
Henry Olders -
Jürgen Doser -
Lorenzo Isella -
Ozgur Akgun