[Haskell-cafe] A list library without fixpoints and recursive types.

[flicky frans]

Hello. I read some Oleg Kiselyov's papers and tried to write more or
less efficient list library with lists represented as their right
fold, as mentioned here http://okmij.org/ftp/Haskell/zip-folds.lhs :
    It would be interesting to see, constructively, how to build
    the full-fledged (FR)-list library and avoid general recursion. Let
    the FR-list be the only driver of iterations.
Here is the code: http://ideone.com/NKNeWy
I don't post it to hackage, since I'm not sure, these lists are really
efficient.
There are two main ideas:
1) List is represented as an accumulating right fold, and an
accumulator passes from left to right.
2) For efficiency purposes elements skipping is incorporated into the
cons (($:) in the code) function. So there is only one isSkipped test
(d == 0 in the code) for every element, no matter, how many times drop
(or tail or dropWhile) was applied. So there are no redundant (<= 0)
checks, as described in the zip-folds paper:
    The function sdrop shows the major deficiency: we're stuck with the
    (<=0) test for the rest of the stream. In this case, some delimited
    continuation operators like `control' can help, in limited
    circumstances.
Here are the pluses:
1) No fixpoints and recursive types.
2) These lists are totally isomorphic to ordinary haskell's, even in a
strict monad.
3) No redundant (<= 0) checks.
There are some not very big problems with this encoding:
1) Code becomes more complicated than with the ordinary right fold.
2) In fscanl and fsndMapAccumL functions skipped elements are
traversed twice, because you need to traverse an accumulator through
skipped elements too. And the same holds for the fdropWhile function
with additional skipping overhead.
3) Since an accumulator passes from left to right, it's not possible
to efficiently fuse fscanr and fmapAccumR functions, so they are
defined in the terms of ($:) and ffoldr.
And one big problem:
zipWith and all other functions, that require parallel lists
processing, are quadratic. And the same holds for the ftails function
and all other functions, that deconstruct a list by repeatedly
applying (fhead . ftail) or collect lists, obtained by repeteadly
applied ftail function. However I have never seen any other
representation, expressible in pure System F with higher-rank types,
which allows such deconstruction in a linear time. If someone knows,
give me a link, please.

Any suggestions are welcome.