Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 2 / f

For finite, fully defined representations, yes; for arbitrary infinite ones in Haskell, no. At the level of mathematical occurrence sets, splitting by parity, dividing by two, and then applying the inverse index transformations recovers every original position exactly once. Thus the equality holds on finite total position lists.

For a proper infinite representation, take the alternating Boolean sequence, represented byThis is a total representation: both queries return productive infinite occurrence lists. Butfilters for odd indices in [0,2..], so it produces no outer constructor and denotes $\perp$. The calluses mergePos to inspect both transformed lists before emitting its first result; it therefore also diverges. In contrast, alternating False starts with 0. Applying head distinguishes the two. The productivity failure is real even though the mathematical position-set identity is correct; the hypothesis that the input properly represents an infinite sequence does not remove it.