Using constructor memory in haskell

Question

Possible duplicate:
Memory for Haskell Data Types

When solving combinatorial problems, I often present the solution as a bit string, for example. 1010100010110111000110 ... You get an image.

I realized that when I use [Int] for a bit string, Int always spends as much memory as this number would actually be (because Int is limited, unlike Integer ), since the computer only remembers the bit representation , and String will take up even more space as far as I know.

My idea was to use a data type

 data Bits = Empty | Zero Bits | One Bits deriving (Eq,Ord,Show) 

But how much memory do the Empty , Zero and One constructors use compared to Int 's?

Answer 1

Int costs two words in memory ( #I constructor and #Int ), your Bits data may use different values, for example: Zero (One (Zero Empty)) will cost:

• One word for the constructor Empty
• Two words for Zero Constructor and Field
• Two Words for One Constructor and Field
• Two words for Zero Constructor and Field

and the total cost is 7 words. Thus, the amount of memory for your data may be greater than for Int .