First of all, good work! I can see the effort you put into grokking something so foreign, and I would like to commend you for it. I will be focusing on reviewing what I think you can improve, but don't let these critiques discourage you—all code can be improved, but not all code works.
I'll be doing a combination of making general comments and ...
Disclaimer: It has been a while since I've written Haskell in production. Also, while I usually like to review all the code, I have to admit that there is too much for me in this case. Instead, I'll try to focus on what I've seen from a short glance, raise concerns and show alternatives where applicable.
But first, let's give praise.
Types are everywhere
Ah, a fine Spec. Has been a while since I've used Hspec, but your tests seem reasonable. So, first of all: well done!
There is one bit we should fix though, and you have identified it yourself: the property tests.
Creating any kind of number and then checking whether it's positive is a hassle, as half the numbers will get discarded per ...
I think your code (sans bug) is fine. Your question is already a little nit-picky so my comments will mostly be nit-picks. I am not a Haskell expert either, so don't place too much authority in my comments. Evaluate them for yourself.
My comments are in a somewhat arbitrary order, but I've organized them with headers. The section pertaining ...
The code looks fine. At a high level, I don't think it really makes sense to say that this code follows a particularly object-oriented or functional style, maybe because the application is too simple. The difference in this case is really more a matter of perspective.
From an OOP point of view, maybe you see a type with a bunch of methods. That's okay. (It's ...
I won't be reviewing this code for efficiency, since I'm not quite so comfortable with analyzing some combination of State monad, immutable data structures, and laziness.
However, there are a few obvious changes you can make to your code.
Passing State Properly
This is what Franky was getting at with his comment, and it's a bit of a tricky bug. When you do
I might be a little bit late to the party, but better late than never, right?
Your central functions fromList and eval don't have type signatures. This forces the user to check Value and StepData's definition. Better add them:
eval :: Ord a => StepData a
eval = ...
fromList :: (Ord a, Monoid b) => [(a, a, b)]-> StepData a b