David Feuer | 26 Jul 21:34 2014
Picon

Am I missing something about unfoldr?

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
David Feuer | 26 Jul 22:02 2014
Picon

Re: Am I missing something about unfoldr?

Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.

On Jul 26, 2014 3:34 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Carter Schonwald | 26 Jul 22:28 2014
Picon

Re: Am I missing something about unfoldr?

its worth point out that many uses of fusion in haskell libs punt on preserving bottoms, that is, fusion can make *more* programs terminate. I don't have a good example off  hand  mind you


On Sat, Jul 26, 2014 at 4:02 PM, David Feuer <david.feuer <at> gmail.com> wrote:

Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.

On Jul 26, 2014 3:34 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
David Feuer | 26 Jul 22:35 2014
Picon

Re: Am I missing something about unfoldr?

Foldr/build fusion can't remove bottoms; it *can* add them. That's why we have to be very careful. I *think* we're safe in this case, though.

On Jul 26, 2014 4:28 PM, "Carter Schonwald" <carter.schonwald <at> gmail.com> wrote:
its worth point out that many uses of fusion in haskell libs punt on preserving bottoms, that is, fusion can make *more* programs terminate. I don't have a good example off  hand  mind you


On Sat, Jul 26, 2014 at 4:02 PM, David Feuer <david.feuer <at> gmail.com> wrote:

Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.

On Jul 26, 2014 3:34 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
David Feuer | 26 Jul 23:10 2014
Picon

Re: Am I missing something about unfoldr?

I think this is probably what Hinze et al, "Theory and Practice of Fusion" describes as the fold/unfold law, "a fold after an unfold is a hylo" but I don't know enough to read that paper.

On Jul 26, 2014 4:35 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

Foldr/build fusion can't remove bottoms; it *can* add them. That's why we have to be very careful. I *think* we're safe in this case, though.

On Jul 26, 2014 4:28 PM, "Carter Schonwald" <carter.schonwald <at> gmail.com> wrote:
its worth point out that many uses of fusion in haskell libs punt on preserving bottoms, that is, fusion can make *more* programs terminate. I don't have a good example off  hand  mind you


On Sat, Jul 26, 2014 at 4:02 PM, David Feuer <david.feuer <at> gmail.com> wrote:

Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.

On Jul 26, 2014 3:34 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
wren romano | 15 Aug 04:23 2014
Picon

Re: Am I missing something about unfoldr?

On Sat, Jul 26, 2014 at 5:10 PM, David Feuer <david.feuer <at> gmail.com> wrote:
> I think this is probably what Hinze et al, "Theory and Practice of Fusion"
> describes as the fold/unfold law, "a fold after an unfold is a hylo" but I
> don't know enough to read that paper.

The two main styles of fusion are build/foldr and unfoldr/destroy. The
difference is in which side of the slash has the recursion. GHC's
choice to use build/foldr is because that worked more nicely with
various other facets of the language; this is discussed in some of the
early papers about list fusion in GHC.

The issue we run into is that you can't really have unfoldr/foldr
fusion because having recursion on both sides means they fight with
each other. But! we can fuse the operations together into a single
operation, and that single operation should behave nicely with both
build/foldr and unfoldr/destroy styles of fusion.

A catamorphism is the class of recursion schemes you get by
generalizing over the list data type in foldr (hence foldr is the list
instance of cata). Dually, an anamorphism is the class of corecursion
schemes you get by generalizing over the list data type in unfoldr
(hence unfoldr is the list instance of ana). If we use an anamorphism
to expand some "seed" value into a structure (e.g., a list), but then
we immediately use a catamorphism to destroy that structure to produce
a "summary" value, then we can eliminate the intermediate structure
and just go from seed to summary directly. That's what hylomorphisms
do. So we have:

    roll :: F (fix F) -> fix F
    unroll :: fix F -> F (fix F)

    cata :: (F b -> b) -> fix F -> b
    cata f = f . fmap (cata f) . unroll

    ana :: (a -> F a) -> a -> fix F
    ana g = roll . fmap (ana g) . g

    hylo :: (F b -> b) -> (a -> F a) -> a -> b
    hylo f g = f . fmap (hylo f g) . g

where

    cata f . ana g
    == {definition}
    f . fmap (cata f) . unroll . roll . fmap (ana g) . g
    == {unroll/roll fusion}
    f . fmap (cata f) . fmap (ana g) . g
    == {functor law}
    f . fmap (cata f . ana g) . g
    == {inductive hypothesis}
    f . fmap (hylo f g) . g
    == {definition}
    hylo f g

More specifically for lists:

    hyloList :: b -> (x -> b -> b) -> (a -> Maybe (x,a)) -> a -> b
    hyloList fnil fcons g a =
        case g a of
        Nothing -> fnil
        Just (x,a') -> fcons x (hyloList fnil fcons g a')

If we inline hyloList whenever g is known concretely, then the
intermediate Maybe(_,_) structure will be fused away by the
case-of-constructor transform.

Hopefully that should be enough to get you started?

--

-- 
Live well,
~wren
David Feuer | 15 Aug 04:44 2014
Picon

Re: Am I missing something about unfoldr?

I think that "for lists" version is pretty much what I ended up with (I haven't worked through what all the others might be about yet). I don't understand the "fight" you refer to, unless you actually mean trying to implement both foldr/build and destroy/unfoldr at the same time. If you write hyloList in a more inliner-friendly fashion:

hyloList fnil fcons g = go
  where
     go a = case g a of
        Nothing -> fnil
        Just (x,a') -> fcons x (go a')

and then write

unfoldr g a = build $ \c n -> hyloList n c g a

Then foldr/build gets you

foldr c n (unfoldr g a) = hyloList n c g a

And then if g is statically known and sufficiently simple, the Maybes go away.

On Aug 14, 2014 10:23 PM, "wren romano" <winterkoninkje <at> gmail.com> wrote:
On Sat, Jul 26, 2014 at 5:10 PM, David Feuer <david.feuer <at> gmail.com> wrote:
> I think this is probably what Hinze et al, "Theory and Practice of Fusion"
> describes as the fold/unfold law, "a fold after an unfold is a hylo" but I
> don't know enough to read that paper.

The two main styles of fusion are build/foldr and unfoldr/destroy. The
difference is in which side of the slash has the recursion. GHC's
choice to use build/foldr is because that worked more nicely with
various other facets of the language; this is discussed in some of the
early papers about list fusion in GHC.

The issue we run into is that you can't really have unfoldr/foldr
fusion because having recursion on both sides means they fight with
each other. But! we can fuse the operations together into a single
operation, and that single operation should behave nicely with both
build/foldr and unfoldr/destroy styles of fusion.

A catamorphism is the class of recursion schemes you get by
generalizing over the list data type in foldr (hence foldr is the list
instance of cata). Dually, an anamorphism is the class of corecursion
schemes you get by generalizing over the list data type in unfoldr
(hence unfoldr is the list instance of ana). If we use an anamorphism
to expand some "seed" value into a structure (e.g., a list), but then
we immediately use a catamorphism to destroy that structure to produce
a "summary" value, then we can eliminate the intermediate structure
and just go from seed to summary directly. That's what hylomorphisms
do. So we have:

    roll :: F (fix F) -> fix F
    unroll :: fix F -> F (fix F)

    cata :: (F b -> b) -> fix F -> b
    cata f = f . fmap (cata f) . unroll

    ana :: (a -> F a) -> a -> fix F
    ana g = roll . fmap (ana g) . g

    hylo :: (F b -> b) -> (a -> F a) -> a -> b
    hylo f g = f . fmap (hylo f g) . g

where

    cata f . ana g
    == {definition}
    f . fmap (cata f) . unroll . roll . fmap (ana g) . g
    == {unroll/roll fusion}
    f . fmap (cata f) . fmap (ana g) . g
    == {functor law}
    f . fmap (cata f . ana g) . g
    == {inductive hypothesis}
    f . fmap (hylo f g) . g
    == {definition}
    hylo f g

More specifically for lists:

    hyloList :: b -> (x -> b -> b) -> (a -> Maybe (x,a)) -> a -> b
    hyloList fnil fcons g a =
        case g a of
        Nothing -> fnil
        Just (x,a') -> fcons x (hyloList fnil fcons g a')

If we inline hyloList whenever g is known concretely, then the
intermediate Maybe(_,_) structure will be fused away by the
case-of-constructor transform.

Hopefully that should be enough to get you started?

--
Live well,
~wren
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Michael Snoyman | 27 Jul 07:08 2014

Re: Am I missing something about unfoldr?

One I saw not too long ago was where someone created an infinite Vector and then consumed it immediately. With optimizations turned on, the intermediate Vector was fused away. With optimizations turned off, it wasn't fused away, and the program eventually crashed when it ran out of memory for holding the infinite Vector.


On Sat, Jul 26, 2014 at 11:28 PM, Carter Schonwald <carter.schonwald <at> gmail.com> wrote:
its worth point out that many uses of fusion in haskell libs punt on preserving bottoms, that is, fusion can make *more* programs terminate. I don't have a good example off  hand  mind you


On Sat, Jul 26, 2014 at 4:02 PM, David Feuer <david.feuer <at> gmail.com> wrote:

Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.

On Jul 26, 2014 3:34 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
David Feuer | 26 Jul 22:31 2014
Picon

Re: Am I missing something about unfoldr?

But that doesn't look like it's actually a problem. Expand the foldr and unfoldr one step each, apply case-of-case, and it looks like everything comes together nicely.

On Jul 26, 2014 4:02 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.

On Jul 26, 2014 3:34 PM, "David Feuer" <david.feuer <at> gmail.com> wrote:

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = case f b of
  Just (a,new_b) -> a : unfoldr f new_b
  Nothing -> []

I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:

unfoldrB f b c n = go b
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b)
= foldr c n (build (unfoldrB f b))
= unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Gmane