[Agda] Positive but not strictly positive types
effectfully
effectfully at gmail.com
Sat Apr 11 04:03:51 CEST 2015
> I thought Scott encoding was actually:
> newtype List a = Roll { case_ :: forall r. (a -> List a -> r) -> r -> r }
> I.E. the one-step eliminator. Yours looks like the primitive
recursive eliminator (instead of the structurally recursive one).
Yep, I forgot the terminology. Mine is kind of Church encoding + Scott
encoding. Just like P-numerals [1], only lists.
> Certainly it requires a recursive definition for map. And it seems that if you did anything taking
> advantage of the Scott-like part of it, the maps would not be fused for that. So if I zipped lists
> that had functions mapped over them, they wouldn't be fused. Perhaps I'm wrong, though.
Having
smap :: (a -> b) -> List a -> List b
smap h xs = List $ \f -> runList xs (\xs' -> f (smap h xs') . h)
the `szipWith`, that calls `split', that uses Scott-like part, will
not fuse `smap's. So looks like you're right. Anyway, you get O(1)
`tail' and readable code, which is in many cases a good price for
losing fusion after zipping.
> But with non-strict positive types you can eliminate the zip penalty.
I've been thinking for quite a long time, that it's not even possible.
Is your technique described somewhere?
[1] http://okmij.org/ftp/Haskell/LC_Pnum.lhs
More information about the Agda
mailing list