CODEWITHSUNDEEP
haskellrecursion
James Elkwood
James Elkwood

Reputation: 155

Haskell count of all elements in list of lists

In Haskell, given a list of lists, where each sublist contains any number of integers, how can I write a function that returns the total number of elements in all the lists?

For example if my list is:

[[1,2,3],[4,3],[2,1],[5]]

The function would return 8, since there are 8 total elements in the list of lists. I know you can use length [] to get the length of a normal list, but how do I do this with a list of lists? I would assume the solution to be recursive, but could use some help, since I am new to the language.

Upvotes: 1

Views: 7662

Answers (4)

fp_mora
fp_mora

Reputation: 714

So all you need is to treat each list in the list as separate. What tools can do that? As Adam Smith demonstrates foldr is probably the tool of choice however fmap looks good, too and may be shorter. What other tools are there? One of my favorites, the list comprehension. The basic list comprehension lets you process each element of a list in turn. For yours:

yourList = [[1,2,3],[4,3],[2,1],[5]]

[length l | l <- yourList] -- gets the length of each list and

sum [length l | l <- yourList] -- adds up all the lengths produced

Upvotes: 0

Adam Smith
Adam Smith

Reputation: 54163

One additional (pedantic) solution using folds:

foldr ((+) . foldr ((+) . const 1) 0) 0
-- or more simply:
foldr ((+) . length) 0

This incredibly ugly fold generalizes to:

sum [1 | xs <- xss, x <- xs]

which is certainly easier to read.

Upvotes: 4

duplode
duplode

Reputation: 34378

Three ways:

  1. Get the length of each inner list, and sum them all:

    GHCi> sum (fmap length [[1,2,3],[4,3],[2,1],[5]])
8

    (Note this is equivalent to Thomas English's answer: map is fmap specialised to lists.)

  2. Flatten the list of lists, and then get the length:

    GHCi> length (concat [[1,2,3],[4,3],[2,1],[5]])
8

  3. Use the Compose wrapper, which will make length drill through the two layers of lists.

    GHCi> import Data.Functor.Compose
GHCi> length (Compose [[1,2,3],[4,3],[2,1],[5]])
8

    (While explaining exactly what is going on here is a little bit tricky -- in a nutshell, we are exploiting that Compose has a Foldable instance -- behind the scenes it boils down to something very much like the first solution.)

I would assume the solution to be recursive

Indeed. It's just that the additional recursion is performed by the other functions we use (fmap for lists, sum, concat, etc.), and so we don't have to write the recursive algorithms explicitly.

Upvotes: 9

Thomas English
Thomas English

Reputation: 231

You should check out how to use the 'map' function. Learn You a Haskell is a good resource to learn more!

mylist = [[1,2,3],[4,3],[2,1],[5]]

-- Get the length of each sublist with map
sublist_lengths = map length mylist 
-- sublist_lengths = [3, 2, 2, 1]

result = sum sublist_lengths

Upvotes: 4

Related Questions