Re: FoldrW/buildW issues

2014-09-12 Thread David Feuer
On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
wrote:
> Interesting. I assumed that some wrap.unwrap=id law would hold, or at
> least some moral approximation (e.g. disregarding bottoms in an
> acceptable manner). But if the wrappers have to do arbitrary stuff that
> can arbitrarily interact with how the producer calls them, this becomes
> a bit less appealing.

No, nothing pleasant like that, I'm afraid. isoSimple is like that of
course, but once it gets to foldl, the fusion rule is handing the builder a
wrap/unwrap pair that isn't even close to that.

> > 2. Somewhat related to the above, this framework has a huge amount of
> > "wiggle room". There is very little to guide the choice of Wrap type.
>
> I guess that would be resolved by time and experience, if we’d employ
> that scheme. But maybe we don’t.

The only way I would imagine would be if it turned out there were a few
types that could be composed somehow. But when I, experimentally, applied
Dan Doel's scanl wrapper type combined with Simple to (!!), I just got
wrong answers.

> > Do you have any ideas?
>
> Directly related to foldrW, no.
>
> About list fusion and foldl in general, some half-baked.
>
> I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)"
> function, semantically the identity, but tell the compiler not to share
> the result of the computation. Using that in the definition of
> foldl-as-foldr, one can get the same effect as Call Arity, but a bit
> more reliable. I need to investigate if that solves the sumConcatInits
> problem.

How does that work exactly? Where do you stick the oneShot/why is it valid?

> Another idea, probably with the same effect: What happens if we extend
> build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
> to
> buildI :: (forall b. (a -> b -> b) -> b -> (b -> b) -> b) -> [a]
> where the extra argument is the identity, but magically „improves values
> of type b“. So with
>
> enum = buildI $ \c n imp -> go 0
>   where go i = imp $ case i of 100 -> n ; _ -> i `c` go (i+1)
>
> and
>
>foldl f a0 = foldrI (\x k a -> k (f x a)) id (\k a -> k a) a0
>
> we might get good code (but this is half-baked and written as I go).

It sounds a lot like the foldrW/buildW thing again, but maybe you can do
better with it.

> Shouldn’t this be on ghc-dev where others can join an, and people will
> find it in the archives later? I prefer to reserve private mail to,
> well, private matters :-)

If you like.

David
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: FoldrW/buildW issues

2014-09-13 Thread Joachim Breitner
Hi,


Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer:
> On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
> wrote:
> > Interesting. I assumed that some wrap.unwrap=id law would hold, or
> at
> > least some moral approximation (e.g. disregarding bottoms in an
> > acceptable manner). But if the wrappers have to do arbitrary stuff
> that
> > can arbitrarily interact with how the producer calls them, this
> becomes
> > a bit less appealing.
> 
> No, nothing pleasant like that, I'm afraid. isoSimple is like that of
> course, but once it gets to foldl, the fusion rule is handing the
> builder a wrap/unwrap pair that isn't even close to that.

and parametricity doesn’t help here? Note that due to the forall in the
type of buildW, you can probably reason about what kind of values buildW
can produce, as it can only use whatever the consumer handed to it.
Maybe there is an invariant for that type, and the worker/wrapper pair
is the identity for values that fulfill that invariant.

> > > Do you have any ideas?
> >
> > Directly related to foldrW, no.
> >
> > About list fusion and foldl in general, some half-baked.
> >
> > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)"
> > function, semantically the identity, but tell the compiler not to share
> > the result of the computation. Using that in the definition of
> > foldl-as-foldr, one can get the same effect as Call Arity, but a bit
> > more reliable. I need to investigate if that solves the sumConcatInits
> > problem.
> 
> How does that work exactly? Where do you stick the oneShot/

Quite simple, see the attached patch. I think I lost the corresponding
patch to base due to the merge, but all it did was to write

foldl k z xs = foldr (\v fn -> oneShot (\ z -> fn ( k z v ))) id xs z

also see http://www.joachim-breitner.de/publications/CallArity-TFP.pdf
§6.2.

> why is it valid?

Because the type of build allows the builder to use each result of the
„constructor“ to be used once, and the whole result is called once, by
foldl, with z as the argument.

... at least if the list is finite. If build re-uses a result, then
because it builds an infinite list (e.g. in
repeat x = build $ \c _ -> let r = x `c` r in r
) and I’m not quite sure if that is a problem. Probably not here,
because foldl applied to an infinite list is is ⊥ anyways. But with
others (e.g. scanl) I might be wrong and the oneShot trick might not
work there.


> > Another idea, probably with the same effect: What happens if we extend
> > build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
> > to
> > buildI :: (forall b. (a -> b -> b) -> b -> (b -> b) -> b) -> [a]
> > where the extra argument is the identity, but magically „improves values
> > of type b“. So with
> >
> > enum = buildI $ \c n imp -> go 0
> >   where go i = imp $ case i of 100 -> n ; _ -> i `c` go (i+1)
> >
> > and
> >
> >foldl f a0 = foldrI (\x k a -> k (f x a)) id (\k a -> k a) a0
> >
> > we might get good code (but this is half-baked and written as I go).
> 
> It sounds a lot like the foldrW/buildW thing again, but maybe you can
> do better with it.

Yes, it is very much inspired by it, but possibly simpler, and much
weaker: It doesn’t try to undo the continuation style of foldl, but only
helps the compiler a bit. I don’t like it a lot, though.

Gruß,
Joachim

-- 
Joachim Breitner
  e-Mail: m...@joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  Jabber-ID: nome...@joachim-breitner.de

commit f70ff9094bb89d2711ddccd92251dcfa74f86002
Author: Joachim Breitner 
Date:   Sun Jan 26 11:36:23 2014 +

Add GHC.Prim.oneShot

diff --git a/compiler/basicTypes/MkId.lhs b/compiler/basicTypes/MkId.lhs
index 604163f..c6fcbae 100644
--- a/compiler/basicTypes/MkId.lhs
+++ b/compiler/basicTypes/MkId.lhs
@@ -141,7 +141,8 @@ ghcPrimIds
 seqId,
 magicDictId,
 coerceId,
-proxyHashId
+proxyHashId,
+oneShotId
 ]
 \end{code}
 
@@ -1040,7 +1041,7 @@ another gun with which to shoot yourself in the foot.
 \begin{code}
 lazyIdName, unsafeCoerceName, nullAddrName, seqName,
realWorldName, voidPrimIdName, coercionTokenName,
-   magicDictName, coerceName, proxyName :: Name
+   magicDictName, coerceName, proxyName, oneShotName :: Name
 unsafeCoerceName  = mkWiredInIdName gHC_PRIM (fsLit "unsafeCoerce#") unsafeCoerceIdKey  unsafeCoerceId
 nullAddrName  = mkWiredInIdName gHC_PRIM (fsLit "nullAddr#") nullAddrIdKey  nullAddrId
 seqName   = mkWiredInIdName gHC_PRIM (fsLit "seq")   seqIdKey   seqId
@@ -1051,6 +1052,7 @@ coercionTokenName = mkWiredInIdName gHC_PRIM (fsLit "coercionToken#") coercionTo
 magicDictName = mkWiredInIdName gHC_PRIM (fsLit "magicDict") magicDictKey magicDictId
 coerceName= mkWiredInIdName gHC_PRIM (fsLit "coerce")coerceKey  coerceId
 proxyName = mkWiredInIdName gHC_PRIM (fsLit "proxy#")proxyHashKey   proxyHashId
+oneShotName   = mkWiredInId

Re: FoldrW/buildW issues

2014-09-14 Thread David Feuer
Joachim Breitner wrote:

> Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer:
> > On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
> > wrote:
> > > Interesting. I assumed that some wrap.unwrap=id law would hold, or
> > at
> > > least some moral approximation (e.g. disregarding bottoms in an
> > > acceptable manner). But if the wrappers have to do arbitrary stuff
> > that
> > > can arbitrarily interact with how the producer calls them, this
> > becomes
> > > a bit less appealing.
> >
> > No, nothing pleasant like that, I'm afraid. isoSimple is like that of
> > course, but once it gets to foldl, the fusion rule is handing the
> > builder a wrap/unwrap pair that isn't even close to that.
>
> and parametricity doesn't help here? Note that due to the forall in the
> type of buildW, you can probably reason about what kind of values buildW
> can produce, as it can only use whatever the consumer handed to it.
> Maybe there is an invariant for that type, and the worker/wrapper pair
> is the identity for values that fulfill that invariant.
>

That seems reasonable, and I suspect without any proof that Takano Akio's
wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it.
Scans seem to be more of a challenge. It appears to me that Dan's scanl
wrapper probably does *not* satisfy that requirement, and I don't know
enough to have much chance of finding one that does.

David
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: FoldrW/buildW issues

2014-09-14 Thread Dan Doel
Which scanl wrapper are you referring to?

The first one I figured out was quite wrong in certain ways. But I think
the new one is less controversial; it's a lot like the reverse one.

On Sun, Sep 14, 2014 at 1:03 PM, David Feuer  wrote:

> Joachim Breitner wrote:
>
>> Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer:
>> > On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
>> > wrote:
>> > > Interesting. I assumed that some wrap.unwrap=id law would hold, or
>> > at
>> > > least some moral approximation (e.g. disregarding bottoms in an
>> > > acceptable manner). But if the wrappers have to do arbitrary stuff
>> > that
>> > > can arbitrarily interact with how the producer calls them, this
>> > becomes
>> > > a bit less appealing.
>> >
>> > No, nothing pleasant like that, I'm afraid. isoSimple is like that of
>> > course, but once it gets to foldl, the fusion rule is handing the
>> > builder a wrap/unwrap pair that isn't even close to that.
>>
>> and parametricity doesn't help here? Note that due to the forall in the
>> type of buildW, you can probably reason about what kind of values buildW
>> can produce, as it can only use whatever the consumer handed to it.
>> Maybe there is an invariant for that type, and the worker/wrapper pair
>> is the identity for values that fulfill that invariant.
>>
>
> That seems reasonable, and I suspect without any proof that Takano Akio's
> wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it.
> Scans seem to be more of a challenge. It appears to me that Dan's scanl
> wrapper probably does *not* satisfy that requirement, and I don't know
> enough to have much chance of finding one that does.
>
> David
>
> ___
> ghc-devs mailing list
> ghc-devs@haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-devs
>
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: FoldrW/buildW issues

2014-09-14 Thread 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.

David


On Sun, Sep 14, 2014 at 2:08 PM, Dan Doel  wrote:

> Which scanl wrapper are you referring to?
>
> The first one I figured out was quite wrong in certain ways. But I think
> the new one is less controversial; it's a lot like the reverse one.
>
> On Sun, Sep 14, 2014 at 1:03 PM, David Feuer 
> wrote:
>
>> Joachim Breitner wrote:
>>
>>> Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer:
>>> > On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
>>> > wrote:
>>> > > Interesting. I assumed that some wrap.unwrap=id law would hold, or
>>> > at
>>> > > least some moral approximation (e.g. disregarding bottoms in an
>>> > > acceptable manner). But if the wrappers have to do arbitrary stuff
>>> > that
>>> > > can arbitrarily interact with how the producer calls them, this
>>> > becomes
>>> > > a bit less appealing.
>>> >
>>> > No, nothing pleasant like that, I'm afraid. isoSimple is like that of
>>> > course, but once it gets to foldl, the fusion rule is handing the
>>> > builder a wrap/unwrap pair that isn't even close to that.
>>>
>>> and parametricity doesn't help here? Note that due to the forall in the
>>> type of buildW, you can probably reason about what kind of values buildW
>>> can produce, as it can only use whatever the consumer handed to it.
>>> Maybe there is an invariant for that type, and the worker/wrapper pair
>>> is the identity for values that fulfill that invariant.
>>>
>>
>> That seems reasonable, and I suspect without any proof that Takano Akio's
>> wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it.
>> Scans seem to be more of a challenge. It appears to me that Dan's scanl
>> wrapper probably does *not* satisfy that requirement, and I don't know
>> enough to have much chance of finding one that does.
>>
>> David
>>
>> ___
>> ghc-devs mailing list
>> ghc-devs@haskell.org
>> http://www.haskell.org/mailman/listinfo/ghc-devs
>>
>>
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: FoldrW/buildW issues

2014-09-14 Thread Joachim Breitner
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
  m...@joachim-breitner.de • http://www.joachim-breitner.de/
  Jabber: nome...@joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nome...@debian.org



signature.asc
Description: This is a digitally signed message part
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: FoldrW/buildW issues

2014-09-24 Thread David Feuer
On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
wrote:
> I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)"
> function, semantically the identity, but tell the compiler not to share
> the result of the computation. Using that in the definition of
> foldl-as-foldr, one can get the same effect as Call Arity, but a bit
> more reliable. I need to investigate if that solves the sumConcatInits
> problem.

One nice thing about this idea (which sounds like it must be related to the
"state hack", but is more explicit) is that it presumably applies also to
similar situations in the State and ST monads, when a state transformer is
only used once. Could you explain, perhaps, what compiler transformation
this enables, and how you implemented it? It would be nice if the compiler
could figure this out for itself, but I'm sure that's much too big a
project for 7.10, whereas making sure foldl, scanl, mapAccumL, foldM, sum,
etc., work really reliably seems important. And yes, I do think such a
thing would probably work for scanl and such, assuming GHC's analysis can
use the information properly—they're just state-transforming list producers.

David
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: FoldrW/buildW issues

2014-09-24 Thread Joachim Breitner
Hi,


Am Mittwoch, den 24.09.2014, 16:37 -0400 schrieb David Feuer:
> On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
> wrote:
> > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)"
> > function, semantically the identity, but tell the compiler not to
> share
> > the result of the computation. Using that in the definition of
> > foldl-as-foldr, one can get the same effect as Call Arity, but a bit
> > more reliable. I need to investigate if that solves the
> sumConcatInits
> > problem.
> 
> One nice thing about this idea (which sounds like it must be related
> to the "state hack", but is more explicit) is that it presumably
> applies also to similar situations in the State and ST monads, when a
> state transformer is only used once. Could you explain, perhaps, what
> compiler transformation this enables, and how you implemented it?

I guess it is used in various places, and I woudn’t know all of them.
The one that I was aiming for was is this one

  case x of
True -> z
False -> \s(one-shot). e

to

  \s(one-shot) . case x of
True -> z s
False -> e

explained in Note [Combining case branches] at
https://github.com/ghc/ghc/blob/master/compiler/coreSyn/CoreArity.lhs#L671

The implementation is attached to my previous mail.


>  It would be nice if the compiler could figure this out for itself,

Well, that’s what I thought, and CallArity is what I came up with :-)

Greetings,
Joachim

-- 
Joachim “nomeata” Breitner
  m...@joachim-breitner.de • http://www.joachim-breitner.de/
  Jabber: nome...@joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nome...@debian.org



signature.asc
Description: This is a digitally signed message part
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


oneShot (was Re: FoldrW/buildW issues)

2014-10-07 Thread David Feuer
Just for the heck of it, I tried out an implementation of scanl using
Joachim Breitner's magical oneShot primitive. Using the test

scanlA :: (b -> a -> b) -> b -> [a] -> [b]
scanlA f a bs = build $ \c n ->
a `c`
foldr (\b g x -> let b' = f x b in (b' `c` g b'))
  (const n)
  bs
  a

scanlB :: (b -> a -> b) -> b -> [a] -> [b]
scanlB f a bs = build $ \c n ->
a `c`
foldr (\b g -> oneShot (\x -> let b' = f x b in (b' `c` g b')))
  (const n)
  bs
  a

f :: Int -> Bool
f 0 = True
f 1 = False
{-# NOINLINE f #-}

barA = scanlA (+) 0 . filter f
barB = foldlB (+) 0 . filter f


with -O2 (NOT disabling Call Arity) the Core from barB is really,
really beautiful: it's small, there are no lets or local lambdas, and
everything is completely unboxed. This is much better than the result
of barA, which has a local let, and which doesn't seem to manage to
unbox anything. It looks to me like this could be a pretty good tool
to have around. It certainly has its limits—it doesn't do anything
nice with reverse . reverse  or  reverse . scanl f b . reverse, but it
doesn't need to be perfect to be useful. More evaluation, of course,
is necessary.to make sure it doesn't go wrong when used sanely.

David
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: oneShot (was Re: FoldrW/buildW issues)

2014-10-07 Thread Sophie Taylor
Wait, isn't call arity analysis meant to do this by itself now?

On 7 October 2014 17:05, David Feuer  wrote:

> Just for the heck of it, I tried out an implementation of scanl using
> Joachim Breitner's magical oneShot primitive. Using the test
>
> scanlA :: (b -> a -> b) -> b -> [a] -> [b]
> scanlA f a bs = build $ \c n ->
> a `c`
> foldr (\b g x -> let b' = f x b in (b' `c` g b'))
>   (const n)
>   bs
>   a
>
> scanlB :: (b -> a -> b) -> b -> [a] -> [b]
> scanlB f a bs = build $ \c n ->
> a `c`
> foldr (\b g -> oneShot (\x -> let b' = f x b in (b' `c` g b')))
>   (const n)
>   bs
>   a
>
> f :: Int -> Bool
> f 0 = True
> f 1 = False
> {-# NOINLINE f #-}
>
> barA = scanlA (+) 0 . filter f
> barB = foldlB (+) 0 . filter f
>
>
> with -O2 (NOT disabling Call Arity) the Core from barB is really,
> really beautiful: it's small, there are no lets or local lambdas, and
> everything is completely unboxed. This is much better than the result
> of barA, which has a local let, and which doesn't seem to manage to
> unbox anything. It looks to me like this could be a pretty good tool
> to have around. It certainly has its limits—it doesn't do anything
> nice with reverse . reverse  or  reverse . scanl f b . reverse, but it
> doesn't need to be perfect to be useful. More evaluation, of course,
> is necessary.to make sure it doesn't go wrong when used sanely.
>
> David
> ___
> ghc-devs mailing list
> ghc-devs@haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-devs
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: oneShot (was Re: FoldrW/buildW issues)

2014-10-07 Thread Joachim Breitner
Hi,


Am Dienstag, den 07.10.2014, 03:05 -0400 schrieb David Feuer:
> Just for the heck of it, I tried out an implementation of scanl using
> Joachim Breitner's magical oneShot primitive. Using the test
>
> [..]
>
> with -O2 (NOT disabling Call Arity) the Core from barB is really,
> really beautiful: it's small, there are no lets or local lambdas, and
> everything is completely unboxed. This is much better than the result
> of barA, which has a local let, and which doesn't seem to manage to
> unbox anything.


I cannot reproduce this here. In fact, I get identical core in both
cases. Only when I do pass -fno-call-arity, A gets bad code, while B is
still good.

Maybe your example is too small?

Greetings,
Joachim

-- 
Joachim “nomeata” Breitner
  m...@joachim-breitner.de • http://www.joachim-breitner.de/
  Jabber: nome...@joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nome...@debian.org



signature.asc
Description: This is a digitally signed message part
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs


Re: oneShot (was Re: FoldrW/buildW issues)

2014-10-07 Thread David Feuer
Yes, and it does a very good job in many cases. In other cases, it's
not as good.

On Tue, Oct 7, 2014 at 7:59 AM, Sophie Taylor  wrote:
> Wait, isn't call arity analysis meant to do this by itself now?
>
> On 7 October 2014 17:05, David Feuer  wrote:
>>
>> Just for the heck of it, I tried out an implementation of scanl using
>> Joachim Breitner's magical oneShot primitive. Using the test
>>
>> scanlA :: (b -> a -> b) -> b -> [a] -> [b]
>> scanlA f a bs = build $ \c n ->
>> a `c`
>> foldr (\b g x -> let b' = f x b in (b' `c` g b'))
>>   (const n)
>>   bs
>>   a
>>
>> scanlB :: (b -> a -> b) -> b -> [a] -> [b]
>> scanlB f a bs = build $ \c n ->
>> a `c`
>> foldr (\b g -> oneShot (\x -> let b' = f x b in (b' `c` g b')))
>>   (const n)
>>   bs
>>   a
>>
>> f :: Int -> Bool
>> f 0 = True
>> f 1 = False
>> {-# NOINLINE f #-}
>>
>> barA = scanlA (+) 0 . filter f
>> barB = foldlB (+) 0 . filter f
>>
>>
>> with -O2 (NOT disabling Call Arity) the Core from barB is really,
>> really beautiful: it's small, there are no lets or local lambdas, and
>> everything is completely unboxed. This is much better than the result
>> of barA, which has a local let, and which doesn't seem to manage to
>> unbox anything. It looks to me like this could be a pretty good tool
>> to have around. It certainly has its limits—it doesn't do anything
>> nice with reverse . reverse  or  reverse . scanl f b . reverse, but it
>> doesn't need to be perfect to be useful. More evaluation, of course,
>> is necessary.to make sure it doesn't go wrong when used sanely.
>>
>> David
>> ___
>> ghc-devs mailing list
>> ghc-devs@haskell.org
>> http://www.haskell.org/mailman/listinfo/ghc-devs
>
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://www.haskell.org/mailman/listinfo/ghc-devs