Implement step function in Haskell
I might be a little bit late to the party, but better late than never, right?
Type signatures
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 =&gt; StepData a
eval = ...

fromList :: (Ord a, Monoid b) =&gt; [(a, a, b)]-&gt; StepData a b
fromList  = ...

Remove dead code
merge isn't used in your code. It's dead code and not used in your instance at all. Better remove it.
Make sure the code compiles
That wasn't an issue back in 2013, but nowadays Semigroup is a superclass of Monoid, and you need to implement it too.
Don't encode Bool twice
eval's sol can be simplified a lot if we just use not around the condition:
eval (StepData xs) t = y
  where (_,_,y) = head $ dropWhile sol xs
        sol (a,b,_) = not (a &lt;= Value t &amp;&amp; Value t &lt; b)

The function also gets easier to understand if we use filter instead, as we don't need to deal with double negation (drop and not):
eval (StepData xs) t = y
  where (_,_,y) = head $ filter sol xs
        sol (a,b,_) = a &lt;= Value t &amp;&amp; Value t &lt; b

Document requirements of data
fromList needs a proper sorted list. That's not documented anywhere and neither enforced in its type nor its logic. We might end up with StepData [(Value 3, Value 1, Maybe 3)] or StepData [(Value 3, Value 4, Maybe 3),(Value 1, Value 2, Maybe 3)], as the list is only maped.
Instead, use foldMap and make sure that the values are ordered properly:
fromList = foldMap go
  where
    go (a, b, y)
      | a &lt; b     = StepData [(Value a, Value b, y)]
      | otherwise = StepData [(Value b, Value a, y)]