I have the following toy program which cyclic shifts a vector and adds it to itself (under a mod). It does that for different shifts and high number of iterations (compared to the size of the vector). Program works, but its dog slow. I am still learning Haskell, so my question is: am I doing something wrong?
import Data.List (foldl')
import qualified Data.Sequence as Seq
import Data.Sequence (index, zipWith, Seq, (><), (<|), (|>))
seqSize = 100
numShifts = 10000
cycleShift :: Integer -> Seq a -> Seq a
cycleShift s l = Seq.drop (fromInteger s) l >< Seq.take (fromInteger s) l
modAdd :: Seq Integer -> Seq Integer -> Seq Integer
modAdd s t = Seq.zipWith (\ a b -> (a + b) `mod` 10^16) s t
step :: Seq Integer -> Integer -> Seq Integer
step l shift = modAdd l (cycleShift shift l)
allshifts = [i `mod` seqSize |i <- [1..numShifts]]
start = Seq.fromList (1 : [0 | i <- [1..(seqSize - 1)]])
end = foldl' step start allshifts
main :: IO ()
main = print (Seq.index end 0)
The same program in Python
seq_size = 100
num_shifts = 10000
S = [i % seq_size for i in xrange(1, num_shifts + 1)]
ssums = [1] + [0 for i in range(seq_size - 1)]
for s in S:
shift = ssums[s:] + ssums[:s]
ssums = [(ssums[i] + shift[i]) % 10**16 for i in range(seq_size)]
print ssums[0]
Here are the timings. Haskell: real 0m5.596s Python: real 0m0.551s
Python is not known for it's speed and yet is x10 times faster ?!?