FoldrW/buildW issues

Joachim Breitner mail at joachim-breitner.de
Sun Sep 14 20:16:55 UTC 2014


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 at joachim-breitner.dehttp://www.joachim-breitner.de/
  Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140914/12f7d6cf/attachment-0001.sig>


More information about the ghc-devs mailing list