CODEWITHSUNDEEP
listhaskell
J. Chung
J. Chung

Reputation: 1

Haskell list length alternative

Hi I've got a list on Haskell with close to 10^15 Int's in it and I'm trying print the length of the list.

let list1 = [1..1000000000000000]   --  this is just a dummy list I dont
print list1 length                  --  know the actual number of elements

printing this takes a very long time to do, is there another way to get the number of elements in the list and print that number?

Upvotes: 0

Views: 510

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152697

I've occasionally gotten some value out of lists that carry their length. The poor man's version goes like this:

import Data.Monoid

type ListLength a = (Sum Integer, [a])

singletonLL :: a -> ListLength a
singletonLL x = (1, [x])

lengthLL :: ListLength a -> Integer
lengthLL (Sum len, _) = len

The Monoid instance that comes for free gives you empty lists, concatenation, and a fromList-alike. Other standard Prelude functions that operate on lists like map, take, drop aren't too hard to mimic, though you'll need to skip the ones like cycle and repeat that produce infinite lists, and filter and the like are a bit expensive. For your question, you would also want analogs of the Enum methods; e.g. perhaps something like:

enumFromToLL :: Integral a => a -> a -> ListLength a
enumFromToLL lo hi = (fromIntegral hi-fromIntegral lo+1, [lo..hi])

Then, in ghci, your example is instant:

> lengthLL (enumFromToLL 1 1000000000000000)
1000000000000000

Upvotes: 2

Related Questions