Problem

I am trying to solve the RIVALS problem on SPOJ: Starting from (0, 0), how many paths are there to reach point (X, Y), only taking one-unit steps moving to the right or up? *Constraints: 0 ≤ X ≤ 10 ^{6}, 0 ≤ Y ≤ 10^{6}, answer is to be given modulo (10^{9} + 7).*

I am facing a performance issue with accessing elements of a list. I am also facing a runtime error if I am trying to access the list element.

In order to get the n^{th} element I am using `[1,1,1,2]!!n`

, but I have been told that this runs in O(n) which is very slow. Is there any other data structure in Haskell which gives O(1) access time for n^{th} element?

About my algorithm: the number of way to move form (0,0) to (x,y) in 2D plain and answer is:

```
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Data.List
import Data.Bits
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Char8 as C
seqI :: Integer -> Integer
seqI x = seq x x
seqB :: Bool -> Bool
seqB x = seq x x
modExp' :: Integer -> Integer -> Integer -> Integer -> Integer
modExp' r b p m = let nextR = seqI $ (seqI $ r*b)`rem` m
nextB = seqI $ (seqI $ b*b)`rem` m
nextP = seqI $ shiftR p 1
incl = seqB $ testBit p 0
cont = seqB $ nextP /= 0
in if incl
then if cont
then modExp' nextR nextB nextP m
else nextR
else if cont
then modExp' r nextB nextP m
else r
modExp :: Integer -> Integer -> Integer -> Integer
modExp b p m = modExp' 1 b p m
readInts :: IO [Int]
readInts = fmap (map read.words) getLine
read2Ints :: IO [Int]
read2Ints = do
ints <- readInts
if length ints == 2 then return ints else do
putStrLn ("sorry, could you give me exactly two integers, "
++ "separated by spaces?")
read2Ints
p = 1000000007::Integer
ip = 1000000005::Integer
mtimes a b = (a * b)`rem`p
facts = scanl mtimes 1 [1..2000001]
anstable ::[Integer]
anstable = facts
solve ::Int->Int-> Integer
solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007
main :: IO ()
main = do
n <- readLn
forM_ [1..n::Int] (i -> do
xs <- read2Ints
print $(solve (head xs) (last xs)))
```

Solution

## Code organization

The definitions of `readInts`

and `read2Ints`

disrupt the mathematical code. The I/O routines belong further down, just before `main`

.

`import Data.Maybe`

and `import qualified Data.ByteString.Char8 as C`

appear to be superfluous.

## Abstraction

It is not immediately obvious from reading

```
``````
solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007
```

that it is calculating

I would expect to see

```
solve x y = modCombination (x + y) y p
modCombination n r p =
(factorial n) * (modInvFactorial r) * (modFactorial (n - r)) `rem` p'
where …
```

In some ways, you come close, but `anstable`

obscures your intention. Why not `ansTable`

, with the customary capitalization so that it doesn’t look like `an stable`

? Why did you rename it from `fact`

in the first place, making it more confusing? Why is `1000000007`

hard-coded at the end, when you could have used `p`

?

What is `ip`

? `1000000005`

is a magic number that appears nowhere in the stated challenge. What about `2000001`

? Where did that limit come from?