Use arbitrary-precision integers for positions, avoiding overflow on infinite sequences:
type Seq a = a -> [Integer]

rep :: Eq a => [a] -> Seq a
rep xs v = [i | (i,x) <- zip [0..] xs, x == v]
The type synonym Seq a needs no equality constraint; the equality test is required specifically by rep. The list comprehension visits input positions in increasing order, so the output is an increasing list of precisely the matching positions. For finite inputs this includes a terminating empty list when the value is absent. Infinite inputs require the additional productivity distinctions discussed below. This is an occurrence-position representation of a sequence.
With nonpositive counts treated as in the standard list operations:
takeSeq :: Integer -> Seq a -> Seq a
takeSeq n s
  | n <= 0 = const []
  | otherwise = \v -> takeWhile (< n) (s v)

dropSeq :: Integer -> Seq a -> Seq a
dropSeq n s
  | n <= 0 = s
  | otherwise = \v -> map (subtract n) (dropWhile (< n) (s v))
An occurrence survives takeSeq n exactly when its original index is less than , and its index stays unchanged. It survives dropSeq n exactly when its original index is at least , and its new index is the original one minus . Sorted occurrence lists justify takeWhile and dropWhile. No equality constraint on the element type is needed because the operations only transform positions. The first guard also lets takeSeq 0 s v return [] without inspecting s v.
The most informative occurrence-position representation of a sequence of natural numbers is
naturals :: Seq Integer
naturals v
  | v < 0 = []
  | otherwise = [v]
Each nonnegative integer occurs once at its own index, and negative integers never occur.
This is not equal to rep [0..] under lazy evaluation. For a nonnegative query v, rep eventually emits v, but then searches forever for another occurrence: its result has the shape v : undefined, rather than the terminating singleton [v]. For a negative query, even the outer constructor is never produced, whereas naturals immediately returns [].
No general, correct rep :: Eq a => [a] -> Seq a can always certify those absences from an arbitrary infinite input. A terminating certification has inspected only finitely many elements, and the same prefix could be followed by the supposedly absent value, or by a further occurrence of it. Extra knowledge changes the problem: for a promised strictly increasing integer input, a search can stop with [] when it first exceeds the query and return [i] immediately upon equality. That specialised representation can produce naturals; a generic search cannot. This is the absence-detection obstruction for infinite lists.
Even and odd original positions become consecutive new positions:
evens :: Seq a -> Seq a
evens s v = map (`div` 2) (filter even (s v))

odds :: Seq a -> Seq a
odds s v = map (`div` 2) (filter odd (s v))
An occurrence at belongs to evens at position ; one at belongs to odds at position . Thus the formulas preserve increasing position order and produce the specified finite examples. For infinite occurrence lists, filtering can search forever when no further position of the chosen parity exists. Consequently these otherwise direct formulas need not preserve productivity for every query.
Define the ordered merge algorithm explicitly:
mergePos :: [Integer] -> [Integer] -> [Integer]
mergePos [] ys = ys
mergePos xs [] = xs
mergePos xs@(x:xt) ys@(y:yt)
  | x <= y = x : mergePos xt ys
  | otherwise = y : mergePos xs yt

ilv :: Seq a -> Seq a -> Seq a
ilv s t v = mergePos (map (2*) (s v))
                    (map (\j -> 2*j+1) (t v))
The first sequence occupies even positions and the second occupies odd positions. Within each transformed list, order is preserved; merging puts all positions for a queried token into increasing order. The two transformed lists have disjoint parities, so equality cannot occur between their heads on valid inputs. The length assumption ensures that these positions describe the intended interleaved sequence without a gap at its finite end.
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 by
alternating :: Seq Bool
alternating False = [0,2..]
alternating True = [1,3..]
This is a total representation: both queries return productive infinite occurrence lists. But
odds alternating False
filters for odd indices in [0,2..], so it produces no outer constructor and denotes . The call
ilv (evens alternating) (odds alternating) False
uses 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.

Ancestors (10)

  1. Functional programming, design and analysis of algorithms
  2. 2023
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version