What's more idiomatic in Haskell?
I tend towards the former, and then use a lens or traversal to extract the location.

import Control.Lens

class HasLocation t where
  loc :: Lens' t Location

instance HasLocation RExpr where
  loc f (RLExpr l e)    = f l &lt;&amp;&gt; \l' -&gt; RLExpr l' e
  loc f (RConstant l c) = f l &lt;&amp;&gt; \l' -&gt; RConstant l' c
  loc f (RMathExpr l m) = f l &lt;&amp;&gt; \l' -&gt; RMathExpr l' m
  loc f (FCall l i xs) = f l &lt;&amp;&gt; \l' -&gt; FCall l' i xs


With the class you can overload the use of loc for other data types. Because it is a lens you can use it to get/set/modify the location with a large vocabulary without cluttering your namespace.