How to find time complexity for functions in lazy functional languages?
I would consider an approach based on potential. Note that lazy evaluation changes the internal state of an object and therefore takes away an important advantage of functional programming.

As an example, imagine the following three functions


sort : List $\rightarrow$ List. Sorts the list using Selection Sort.
unique_special : List $\rightarrow$ List. For every odd position $i$ in the input list, the element at that position is removed from the list if it is equal to the element at $i+1$.
head : List $\rightarrow$ X. Finds the first element of the list.


Given a list $L$, I will use $\Phi(L)$ for its potential. $\Phi(L) : \{1, \dots, |L|\} \rightarrow \mathbb{N}$ is a function describing the cost of each element.

A "clear" list has a constant potential, i.e. $\Phi(L)(i) = 1$ for all indices $i$.

Let L be a list and sort(L) = L'. Then $\Phi(L')(i) = \sum\limits_{j=1}^{|L|} \Phi(L)(j)$, because Selection Sort will have to look at every element in $L$ to find a minimal one. After this, $L$ is completely evaluated, i.e. it is not "lazy" anymore. This means the potential of every element is reduced to $\Phi(L)(i) = 1$. Here you can see the importance of the fact, that lazy evaluation can change within an object. If you assume that is not possible, for example by disallowing variables (e.g. via "where" in Haskell), the analysis becomes easier.

For unique_special, consider again L' = unique_special(L). To evaluate the first element, the next one has to be evaluated as well (to compare them). $\Phi(L')(1) = \Phi(L)(1) + \Phi(L)(2)$. Of course, would $L'(1)$ be evaluated, the potential of $L(1)$ and $L(2)$ would become 1.

Later elements require additional knowledge of whether the previous elements were deleted. You have $L'(2) = L(1)$ if the first element was deleted and $L'(2) = L(2)$ otherwise. Hence, $\Phi(L')(2) = \Phi(L)(1) + \Phi(L)(2)$ and $\Phi(L')(3) = \Phi(L)(1) + \Phi(L)(2) + \Phi(L)(3) + \Phi(L)(4)$. 

Generalizing this formula results in $\Phi(L')(i) = \sum\limits_{j=1}^k \Phi(L)(j)$, where $k = \lfloor \frac{i}{2} \rfloor \cdot 2$.

Finally, consider head(L). This does not create a new list, it just requires you to pay the potential of $\Phi(L)(1)$.

As you can see, this clearly increases the complexity of function definitions, especially if you want to include changing potential of the same data structure in your analysis. It gives you the opportunity for a more abstract analysis though:

Let $L$ be a completely evaluated / non-lazy list and the call head(sort(L))). The cost of this call will be $\Phi(\text{sort}(L))(1) = \sum\limits_{j=1}^{|L|} \Phi(L)(j) = |L|$.

A second example: What is the cost of the call head(unique_special(L')), where $L' = \text{sort}(L)$? 

\begin{align*}
&amp; \Phi(\text{unique_special}(L'))(1) \\
=&amp; \Phi(L')(1) + \Phi(L')(2) \\
=&amp; \sum\limits_{j=1}^{|L|} 1 + \sum\limits_{j=1}^{|L|} 1 \\
=&amp; 2 |L|
\end{align*}

You can put more detail into the description of $\Phi$ to observe more accurate results.

Regarding generalization to other data structures, I didn't think about that too much so far. It should be clear that similar structures such as queues work in a similar way. However, for example for a Union-Find structure, I can't think of a way my approach would give you any advantage.

An addition regarding non-linear data structures, for example binary search trees. While it is the easiest option, there is no definite need to use a set $\{1, \dots, n\}$ as the domain of $\Phi$. A common way to index the nodes of a binary tree is to use strings in $\{0,1\}^*$. The root is labelled with the empty string $\varepsilon$ and for a node $v$, the left successor is $v0$ and the right successor is $v1$. For example, the following tree

   5
 4   8
1   6 9


would have the domain $\{\varepsilon, 0, 00, 1, 10, 11\}$.

Imagine a function delete : Tree $\times$ Node $\rightarrow$ Tree to remove a certain node from the tree. You need to check if either of the subtrees is empty. Let delete($T$, $v$) = $T'$, then the potential is $\Phi(T')(v) = \sum\limits_{\substack{w \in \{0,1\}^* \\ w \text{ is a descendant of } v}} \Phi(T)(w)$, where we assume $\Phi(T)(w) = 0$ if $w$ is not a node of $T$.