Ryan Ingram ryani.spam at gmail.com
Wed Jul 9 23:48:45 EDT 2008

```On 7/9/08, Ronald Guida <oddron at gmail.com> wrote:
> Question: If I can't change my function f (in this case, accumulator),
> then is it possible to get the effect I want without having to resort
> to "unsafeInterleaveIO"?

Yes, but you won't like it.

Since you know that (f xs !! n) only depends on the first (n-1)
elements of xs, you have this identity:

f xs !! n == f (take (n-1) xs) !! n

You can then call f with a new list each time, extracting the desired
elements as you build up the source list.  This is, of course,
terribly inefficient.

In order to see why you need an unsafe primitive to solve this
function, you may find it enlightening to try to write this function:

> data Stream a b = NilStream | Stream b (a -> Stream a b)
> liftStream :: ([a] -> [b]) -> Stream a b
> liftStream = ?

(the inverse of this function is trivial to write)

The problem is that there is no way to extract the continuation from f
(x:??); if you had some way, you'd be able to call the same
continuation multiple times with different arguments, effectively
"pausing" f partway through and giving it new input.

By using unsafeInterleaveIO, you are adding a side-effect to the
"pure" argument to f, which allows it to interact with the user.  Once
that side-effect executes, the value is 'fixed' into place and can't
be modified.

Another way to look at it is to suppose that f didn't meet your
invariant, and tried to access an element out of order.  How is the
thunk to be evaluated for that element built?  If it can't do IO, it
must be a pure computation.  But it needs to do IO because the element
hasn't been determined yet.

-- ryan
```