Enigma machine simulator - improving recursive algorithm performance

I'm new to Haskell and am confused by why my code seems to preform so poorly, and wonder if there's something I've not grasped about the coding philosophy behind the language, or the best way to take advantage of its features.

For example, I have started, as an exercise (yet another) simple Enigma machine simulator (for which I've attached the state changing code below) that I have implemented in other languages (e.g., Mathematica) using exactly the same recursive approach to computing the state of the machine from previous states.

But in Haskell, this code performs too slowly to be of any use. I can for example

ghci> let cfg = EnigmaConfig "B-III-II-I" "KDO" "" "01.01.01"
ghci> map (windows . step cfg) [0..10]

to view the state changes of the machine as expressed by the rotor letters visible in the machine windows. But for larger ranges of steps, things start to take forever. I have to give up after a few minutes waiting for

ghci> map (windows . step cfg) [0..20]

to complete.

I've tried caching results of the overall machine state (step) and the rotor positions (componentPos), as indicated in the alternate versions of the relevant functions in the comment to the code fragment, but this has little effect.

Is there a better approach to improving the performance of recursive code like this in Haskell? Have my attempts to "cache" results failed to store the relevant values, or missed the source of my performance issues?

```
import Data.Char
import Data.List
import Data.List.Split
import Data.Maybe
import Data.Ix (inRange)

letters = ['A'..'Z']

letterIndex :: Char -> Int
letterIndex l = fromJust $ elemIndex l letters

type Wiring = String
type Turnovers = String
type Name = String

data Component = Component { wiring :: Wiring, turnovers :: Turnovers }

component :: Name -> Component
component n = case n of
"I" -> Component "EKMFLGDQVZNTOWYHXUSPAIBRCJ" "Q"
"II" -> Component "AJDKSIRUXBLHWTMCQGZNPYFVOE" "E"
"III"

First, the automatic stuff people will reply when somebody asks a question like this:

-
You are compiling the code with optimisations on, right?

-
You may (or may not) find that changing String to something else gives a speedup. (In this case, it's probably not the main bottleneck.)

I see several things which say "slow" to me. For a start,

letters = ['A'..'Z']

letterIndex :: Char ->  Int
letterIndex l = fromJust $ elemIndex l letters

That's a linear-time scan just to convert a character to a number. OK, it's a very small list to search. OTOH, I'm not sure how often this gets called, so... How about this:

letterIndex :: Char -> Int
letterIndex l = fromIntegral l - fromIntegral 'A'

That's now a constant-time calculation. And you don't need the fromJust nonsense.

windowNum :: EnigmaConfig -> Stage -> Int
windowNum ec i = letterIndex (("A" ++ (reverse $ windows ec) ++ "A") !! i)

OK, that doesn't sound good. Calling reverse is likely to be slow. Calling ++ is likely to be slow. Calling !! is likely to be slow. It sounds like you probably want to be using a different data structure here. Maybe Data.Map or something?

I'm not precisely sure what component is doing, but it may be worth changing Name from a String to an enumeration:

data Name = I | II | III | ...

This will probably make the case-block in component go a bit faster.

Without studying your actual algorithm in detail, these are the things that jump out at me.

EDIT: OK, so studying the code a bit closer, it seems that EnigmaConfig stores a bunch of strings, and every single time you want to do something, you parse and re-parse the strings into the actual codes you want. Don't do that. Store the actual code numbers you want (as Int or [Int] or Map Int Int or whatever). Reparsing again and again will be slow as hell — especially with all the calls to reverse and !! involved.

StackExchange Code Review Q#101851, answer score: 26