Sunday, March 21, 2010

Geometric Series in Haskell Using [..] Notation

I was reading the docs earlier today for Haskell's Enum class. Any instance of Enum can be used in the [..] notation, which has four forms: [a..b], [a,b..c], [a..], and [a,b..]. The implementor of Enum a can make these forms do anything, so long as they produce a value of type [a].

It occurred to me that I could create a type, and a corresponding Enum instance, which would make the [..] notation produce a geometric series rather than the usual arithmetic series. I called this type Geo. I also made an instance Integral Geo so that the [Geo] could be turned into a list of more usable numeric type. But I didn't stop there, because using the type directly would be ugly: map toInteger ([1,2..16] :: [Geo]).

So, I made a function geo :: (Integral a) => [Geo] -> [a]. So now, to get a geometric series in a reasonable type, the user only had to say geo [1,2..16].

Then I realized that, unlike when generating an arithmetic series, integral inputs do not guarantee integral outputs. So, I changed the type Geo to be an instance of Fractional rather than Integral, so that you can do things like take 5 $ geo [2,1..] and get the right answer.

If you want more detail, ask me or take a look at the code. An example progam is included.

0 comments:

Post a Comment