Hi, Am Sonntag, den 14.09.2014, 14:47 -0400 schrieb David Feuer:
Your scanl wrapper might be right for scanl, but it does not satisfy the condition Joachim proposed. In particular, if we define
(!!) :: [a] -> Int -> a xs !! n | n < 0 = error "Negative index." | otherwise = foldrW indexWrap indexCons (error "Large index.") xs n where indexCons x _ 0 = x indexCons _ r n = r (n-1) indexWrap = isoSimple
then the simple test
print $ (reverse $ eft 1 1000) !! 50
works just fine. If we replace isoSimple with scanlWrap isoSimple, then the test fails. That is, this produces wrap and unwrap so that wrap . unwrap is not much like the identity; it needs to interact with scanlCons in some fashion to work properly. This does not seem to be at all unusual for worker/wrapper pairs, but i believe it means we need to find a more general local correctness criterion than Joachim proposed, if I understood him correctly.
it would be easier to follow your discussion if you include concrete pointers to code in your mail, or include the code in question; i’m having trouble finding scanlWrap and scanlCons... (and so has Google). Anyways, the correctness criterion, if any, would relate scanlWrap with scanlCons and scanlNil; breakage due to using scanlWrap in a different consumer does not mean that we cannot find a (scanl-specific) invariant that allows us to prove fusion correct for foldrW/buidW fusion of scanl (as a consumer). Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org