Lack of understanding infinite lists and seq operator

Question

The code below retains, for a given integer n, the first n items from a list, drops the following n items, keeps the following n and so on. It works correctly for any finite list. In order to make it usable with infinite lists, I used the 'seq' operator to force the accumulator evaluation before the recursive step as in foldl' as example. I tested by tracing the accumulator's value and it seems that it is effectively computed as desired with finite lists. Nevertheless, it doesn't work when applied to an infinite list. The "take" in the main function is only executed once the inner calculation is terminated, what, of course, never happens with an infinite list. Please, can someone tell me where is my mistake? ``` main :: IO () main = print (take 2 (foo 2 [1..100])) foo :: Show a => Int -> [a] -> [a] foo l lst = inFoo keepOrNot 1 l lst [] inFoo :: Show a => (Bool -> Int -> [a] -> [a] -> [a]) -> Int -> Int -> [a] -> [a] -> [a] inFoo keepOrNot i l [] lstOut = lstOut inFoo keepOrNot i l ls…

Accepted Answer

Here's how list concatenation is implemented:

```
(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
```

Note that

- the right hand list structure is reused as is (even if it's not been evaluated yet, so lazily)

- the left hand list structure is rewritten (copied)

This means that if you're using `++` to build up a list, you want the accumulator to be on the right hand side. (For finite lists, merely for efficiency reasons --- if the accumulator is on the left hand side, it will be repeatedly copied and this is inefficient. For infinite lists, the caller can't look at the first element of the result until it's been copied for the last time, and there won't be a last time because there's always something else to concatenate onto the right of the accumulator.)

The `True` case of `keepOrNot` has the accumulator on the left of the `++`. You need to use a different data structure.

The usual idiom in this case is to use difference lists. Instead of using type `[a]` for your accumulator, use `[a] -> [a]`. Your accumulator is now a function that prepends a list to the list it's given as input. This avoids repeated copying, and the list can be built lazily.

```
keepOrNot :: Bool -> Int -> [a] -> ([a] -> [a]) -> ([a] -> [a])
keepOrNot b n lst1 acc = case b of
  True -> acc . (take n lst1 ++)
  False -> acc
```

The initial value of the accumulator should be `id`. When you want to convert it to a conventional list, call it with `[]` (i.e., `acc []`).

`seq` is a red herring here. `seq` does not force the entire list. `seq` only determines whether it is of the form `[]` or `x : xs`.

You're learning Haskell, yes? So it would be a good idea as an exercise to modify your code to use a difference list accumulator. Possibly the use of infinite lists will burn you in a different part of your code; I don't know.

But there is a better approach to writing `foo`.

```
foo c xs = map snd . filter fst . zipWith f [0..] $ xs
  where f i x = (even (i `div` c), x)
```

Lack of understanding infinite lists and seq operator

Solution

Problem