# Many functions can be generalised

20 messages
Open this post in threaded view
|

## Many functions can be generalised

 A year ago Edwardk Kmett pointed out some possible generalizations of functions [1], I made a ticket about them that led me here [2]. In addition to the functions mentioned> maybeToList :: Foldable f => f a -> [a]> maybeToList = toList> catMaybes :: (Foldable f)             => f (Maybe a) -> [a]> catMaybes :: (Foldable f, Foldable g) => f (g     a) -> [a]> catMaybes = foldMap toList> mapMaybes ::               (a -> Maybe b) -> (forall f. Foldable f => f a -> [b])> mapMaybes :: Foldable m => (a -> m     b) -> (forall f. Foldable f => f a -> [b])> mapMaybes f = foldMap (toList . f)we also have *many* other functions (I do not propose generalising all these function ((especially when the name stops making sense)), but I will include them) that I will define in the vocabulary of ‘lens’. Some generalise to ‘Foldable’> take :: Int -> (forall f a. Foldable f => f a -> [a])> take n = toListOf (taking n folded)> drop :: Int -> (forall f a. Foldable f => f a -> [a])> drop n = toListOf (dropping n folded)> takeWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> takeWhile p = toListOf (takingWhile p folded)> dropWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> dropWhile p = toListOf (droppingWhile p folded)> -- Same as ‘Control.Lens.Indexed.None’> filter :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> filter p = toListOf (folded.filtered p)> cycle :: Foldable f => f a -> [a]> cycle = toListOf (cycled folded)> lookup :: Eq k => k -> (forall f. Foldable f => f (k, v) -> Maybe v)> lookup = lookupOf folded> listToMaybe :: Foldable f => f a -> Maybe a> listToMaybe = firstOf foldedwhile others — to ‘Traversable’> transpose :: Traversable f => f [b] -> [f b]> transpose = transposeOf traverse> scanl1 :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanl1 = scanl1Of traverse> scanr1_ :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanr1_ = scanr1Of traverseMore radical suggestions (pay no heed to the hacky ‘partsOf’, assume better implementation [3]) would allow us to sort a ‘data V2 a = V2 a a deriving (…, Traversable)’ if it contains ordered values:> sort :: (Traversable t, Ord a) => t a -> t a> sort = over (partsOf traverse) Data.List.sort> sortBy :: (a -> a -> Ordering) -> ([a] -> [a])> sortBy = over (partsOf traverse) . Data.List.sortBy> sortOn :: Ord b => (a -> b) -> ([a] -> [a])> sortOn = over (partsOf traverse) . Data.List.sortOn> reverse :: Traversable t => t a -> t a> reverse = over (partsOf traverse) Data.List.reverse> -- Based on ‘Control.Lens.??’> flip :: Functor f => f (a -> b) -> a -> f b > flip f x = fmap (\$ x) for > flip :: (Functor f, Distributive g) => f (g a) -> g (f a)> flip = Data.Distributive.distributeAMP happened some years ago, does this go too far or not far enough? ;) share your thoughtsP.s. I understand those skeptical of the ‘partsOf’ solutions but they do feel magical and uses crop up in odd places, especially in compound structures (I don't have better examples):> ghci> peopleList = Pair ["Bob", "Eve"] (Just "Alice")> ghci> data Product f g a = Pair (f a) (g a) deriving (Show, Functor, Foldable, Traversable)> ghci> sort peopleList> Pair ["Alice","Bob"] (Just "Eve")> ghci> reverse peopleList> Pair ["Alice","Eve"] (Just "Bob")> ghci> peopleMap = fromList [(1,"Bob"),(2,"Eve"),(3,"Alice")] > ghci> sort peopleMap> fromList [(1,"Alice"),(2,"Bob"),(3,"Eve")]> ghci> reverse peopleMap> fromList [(1,"Alice"),(2,"Eve"),(3,"Bob")] _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 I disagree with many of these. For example, I think of takeWhile as having a type shaped like takeWhile :: (a -> Bool) -> f a -> f a Implementations are available for, e.g., sequences, sets, and maps. I don't really want some silly list producer. If I want takeWhile.toList, I know where to get it. Similarly, if I want distribute (which I haven't yet), I know where to get it. Some of these proposals also have substantial performance penalties, such as the sort generalization (which also can't be written in an "obviously total" manner, unfortunately). On Nov 27, 2016 2:10 AM, "Baldur Blöndal" <[hidden email]> wrote:A year ago Edwardk Kmett pointed out some possible generalizations of functions [1], I made a ticket about them that led me here [2]. In addition to the functions mentioned> maybeToList :: Foldable f => f a -> [a]> maybeToList = toList> catMaybes :: (Foldable f)             => f (Maybe a) -> [a]> catMaybes :: (Foldable f, Foldable g) => f (g     a) -> [a]> catMaybes = foldMap toList> mapMaybes ::               (a -> Maybe b) -> (forall f. Foldable f => f a -> [b])> mapMaybes :: Foldable m => (a -> m     b) -> (forall f. Foldable f => f a -> [b])> mapMaybes f = foldMap (toList . f)we also have *many* other functions (I do not propose generalising all these function ((especially when the name stops making sense)), but I will include them) that I will define in the vocabulary of ‘lens’. Some generalise to ‘Foldable’> take :: Int -> (forall f a. Foldable f => f a -> [a])> take n = toListOf (taking n folded)> drop :: Int -> (forall f a. Foldable f => f a -> [a])> drop n = toListOf (dropping n folded)> takeWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> takeWhile p = toListOf (takingWhile p folded)> dropWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> dropWhile p = toListOf (droppingWhile p folded)> -- Same as ‘Control.Lens.Indexed.None’> filter :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> filter p = toListOf (folded.filtered p)> cycle :: Foldable f => f a -> [a]> cycle = toListOf (cycled folded)> lookup :: Eq k => k -> (forall f. Foldable f => f (k, v) -> Maybe v)> lookup = lookupOf folded> listToMaybe :: Foldable f => f a -> Maybe a> listToMaybe = firstOf foldedwhile others — to ‘Traversable’> transpose :: Traversable f => f [b] -> [f b]> transpose = transposeOf traverse> scanl1 :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanl1 = scanl1Of traverse> scanr1_ :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanr1_ = scanr1Of traverseMore radical suggestions (pay no heed to the hacky ‘partsOf’, assume better implementation [3]) would allow us to sort a ‘data V2 a = V2 a a deriving (…, Traversable)’ if it contains ordered values:> sort :: (Traversable t, Ord a) => t a -> t a> sort = over (partsOf traverse) Data.List.sort> sortBy :: (a -> a -> Ordering) -> ([a] -> [a])> sortBy = over (partsOf traverse) . Data.List.sortBy> sortOn :: Ord b => (a -> b) -> ([a] -> [a])> sortOn = over (partsOf traverse) . Data.List.sortOn> reverse :: Traversable t => t a -> t a> reverse = over (partsOf traverse) Data.List.reverse> -- Based on ‘Control.Lens.??’> flip :: Functor f => f (a -> b) -> a -> f b > flip f x = fmap (\$ x) for > flip :: (Functor f, Distributive g) => f (g a) -> g (f a)> flip = Data.Distributive.distributeAMP happened some years ago, does this go too far or not far enough? ;) share your thoughtsP.s. I understand those skeptical of the ‘partsOf’ solutions but they do feel magical and uses crop up in odd places, especially in compound structures (I don't have better examples):> ghci> peopleList = Pair ["Bob", "Eve"] (Just "Alice")> ghci> data Product f g a = Pair (f a) (g a) deriving (Show, Functor, Foldable, Traversable)> ghci> sort peopleList> Pair ["Alice","Bob"] (Just "Eve")> ghci> reverse peopleList> Pair ["Alice","Eve"] (Just "Bob")> ghci> peopleMap = fromList [(1,"Bob"),(2,"Eve"),(3,"Alice")] > ghci> sort peopleMap> fromList [(1,"Alice"),(2,"Bob"),(3,"Eve")]> ghci> reverse peopleMap> fromList [(1,"Alice"),(2,"Eve"),(3,"Bob")] _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 I'd also be -1. Function generalization sometimes has a cost in comprehensability, and there aren't enough benefits to make it worth it to me.TomEl 27 nov 2016, a las 01:53, David Feuer <[hidden email]> escribió:I disagree with many of these. For example, I think of takeWhile as having a type shaped like takeWhile :: (a -> Bool) -> f a -> f a Implementations are available for, e.g., sequences, sets, and maps. I don't really want some silly list producer. If I want takeWhile.toList, I know where to get it. Similarly, if I want distribute (which I haven't yet), I know where to get it. Some of these proposals also have substantial performance penalties, such as the sort generalization (which also can't be written in an "obviously total" manner, unfortunately). On Nov 27, 2016 2:10 AM, "Baldur Blöndal" <[hidden email]> wrote:A year ago Edwardk Kmett pointed out some possible generalizations of functions [1], I made a ticket about them that led me here [2]. In addition to the functions mentioned> maybeToList :: Foldable f => f a -> [a]> maybeToList = toList> catMaybes :: (Foldable f)             => f (Maybe a) -> [a]> catMaybes :: (Foldable f, Foldable g) => f (g     a) -> [a]> catMaybes = foldMap toList> mapMaybes ::               (a -> Maybe b) -> (forall f. Foldable f => f a -> [b])> mapMaybes :: Foldable m => (a -> m     b) -> (forall f. Foldable f => f a -> [b])> mapMaybes f = foldMap (toList . f)we also have *many* other functions (I do not propose generalising all these function ((especially when the name stops making sense)), but I will include them) that I will define in the vocabulary of ‘lens’. Some generalise to ‘Foldable’> take :: Int -> (forall f a. Foldable f => f a -> [a])> take n = toListOf (taking n folded)> drop :: Int -> (forall f a. Foldable f => f a -> [a])> drop n = toListOf (dropping n folded)> takeWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> takeWhile p = toListOf (takingWhile p folded)> dropWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> dropWhile p = toListOf (droppingWhile p folded)> -- Same as ‘Control.Lens.Indexed.None’> filter :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> filter p = toListOf (folded.filtered p)> cycle :: Foldable f => f a -> [a]> cycle = toListOf (cycled folded)> lookup :: Eq k => k -> (forall f. Foldable f => f (k, v) -> Maybe v)> lookup = lookupOf folded> listToMaybe :: Foldable f => f a -> Maybe a> listToMaybe = firstOf foldedwhile others — to ‘Traversable’> transpose :: Traversable f => f [b] -> [f b]> transpose = transposeOf traverse> scanl1 :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanl1 = scanl1Of traverse> scanr1_ :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanr1_ = scanr1Of traverseMore radical suggestions (pay no heed to the hacky ‘partsOf’, assume better implementation [3]) would allow us to sort a ‘data V2 a = V2 a a deriving (…, Traversable)’ if it contains ordered values:> sort :: (Traversable t, Ord a) => t a -> t a> sort = over (partsOf traverse) Data.List.sort> sortBy :: (a -> a -> Ordering) -> ([a] -> [a])> sortBy = over (partsOf traverse) . Data.List.sortBy> sortOn :: Ord b => (a -> b) -> ([a] -> [a])> sortOn = over (partsOf traverse) . Data.List.sortOn> reverse :: Traversable t => t a -> t a> reverse = over (partsOf traverse) Data.List.reverse> -- Based on ‘Control.Lens.??’> flip :: Functor f => f (a -> b) -> a -> f b > flip f x = fmap (\$ x) for > flip :: (Functor f, Distributive g) => f (g a) -> g (f a)> flip = Data.Distributive.distributeAMP happened some years ago, does this go too far or not far enough? ;) share your thoughtsP.s. I understand those skeptical of the ‘partsOf’ solutions but they do feel magical and uses crop up in odd places, especially in compound structures (I don't have better examples):> ghci> peopleList = Pair ["Bob", "Eve"] (Just "Alice")> ghci> data Product f g a = Pair (f a) (g a) deriving (Show, Functor, Foldable, Traversable)> ghci> sort peopleList> Pair ["Alice","Bob"] (Just "Eve")> ghci> reverse peopleList> Pair ["Alice","Eve"] (Just "Bob")> ghci> peopleMap = fromList [(1,"Bob"),(2,"Eve"),(3,"Alice")] > ghci> sort peopleMap> fromList [(1,"Alice"),(2,"Bob"),(3,"Eve")]> ghci> reverse peopleMap> fromList [(1,"Alice"),(2,"Eve"),(3,"Bob")] _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________Libraries mailing list[hidden email]http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 In reply to this post by Baldur Blöndal On 07:10 Sun 27 Nov     , Baldur Blöndal wrote: > > catMaybes :: (Foldable f)             => f (Maybe a) -> [a] > > catMaybes :: (Foldable f, Foldable g) => f (g     a) -> [a] > > catMaybes = foldMap toList > > > mapMaybes ::               (a -> Maybe b) -> (forall f. Foldable f => f a > -> [b]) > > mapMaybes :: Foldable m => (a -> m     b) -> (forall f. Foldable f => f a > -> [b]) > > mapMaybes f = foldMap (toList . f) These two as well as 'filter' are generalized in witherable[1]. [1]: https://hackage.haskell.org/package/witherable/_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 On Sun, Nov 27, 2016 at 9:08 AM, Lana Black <[hidden email]> wrote: > On 07:10 Sun 27 Nov     , Baldur Blöndal wrote: >> > catMaybes :: (Foldable f)             => f (Maybe a) -> [a] >> > catMaybes :: (Foldable f, Foldable g) => f (g     a) -> [a] >> > catMaybes = foldMap toList >> >> > mapMaybes ::               (a -> Maybe b) -> (forall f. Foldable f => f a >> -> [b]) >> > mapMaybes :: Foldable m => (a -> m     b) -> (forall f. Foldable f => f a >> -> [b]) >> > mapMaybes f = foldMap (toList . f) > > These two as well as 'filter' are generalized in witherable[1]. > > [1]: https://hackage.haskell.org/package/witherable/I'm also -1 to the OP. If we want to do these sorts of generalizations, then we should use something like witherable and get that API to where everyone agrees it captures the right concept. Just because we *can* go polymorphic as above doesn't mean those are the proper generalizations. Anything sequential can be made into lists, but that doesn't mean lists are appropriate; lists lose a lot of information. I'd much rather see the above functions as:     mapMaybes :: Foo f => (a -> Maybe b) -> f a -> f b     catMaybes :: Foo f => f (Maybe a) -> f a Note how the f-structure is retained, rather than being needlessly converted to a list. The above signatures capture the idea that f is "sparse" and can absorb missing values, which is a coherent concept that should have some nice laws we can exploit to clean up our code. Indeed, the Witherable class takes this approach (though it has an unfortunate Traversable dependency I don't think is always appropriate). -- Live well, ~wren _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 In reply to this post by amindfv On Sun, 27 Nov 2016, [hidden email] wrote: > I'd also be -1. Function generalization sometimes has a cost in > comprehensability, and there aren't enough benefits to make it worth it > to me. And you lose type inference in more cases. > > maybeToList :: Foldable f => f a -> [a] > > maybeToList = toList Why should we have two names for Foldable.toList, where maybeToList even is no longer special to Maybe? > > take :: Int -> (forall f a. Foldable f => f a -> [a]) > > take n = toListOf (taking n folded) > > > drop :: Int -> (forall f a. Foldable f => f a -> [a]) > > drop n = toListOf (dropping n folded) > > > cycle :: Foldable f => f a -> [a] > > cycle = toListOf (cycled folded) I'd prefer an extension to Monoid, i.e.    take :: (??? m) => Int -> m -> m    drop :: (??? m) => Int -> m -> m    cycle :: (Semigroup m) => m -> m Yet, I do not propose to replace Prelude functions by this generalisations. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 In reply to this post by David Feuer (I meant FTP, not AMP)Fine points, the proposal wasn't a smashing hit but the response has been jolly good.What about functions that aren't expected to preserve structure like ‘lookup’ and (new) suggestions> lookup :: Eq a => k -> Foldable f => f (k, v) -> Maybe v> lookup = lookupOf folded> elemIndex :: Eq a => a -> Foldable f => f a -> Maybe Int> elemIndex = elemIndexOf folded> elemIndices :: Eq a => a -> Foldable f => f a -> Maybe Int> elemIndices = elemIndicesOf folded> findIndex :: (a -> Bool) -> Foldable f => f a -> Maybe Int> findIndex = findIndexOf folded> findIndices :: (a -> Bool) -> Foldable f => f a -> [Int]> findIndices = findIndicesOf foldedand the few that do fit that pattern such as ‘scanl1’, ‘scanr1’, possibly ‘transpose’ as well.P.s. At least I did not propose ↓ yet :)> shuffleM :: (Foldable f, MonadRandom m) => f a -> m (f a)> class ... => Sort f where>   sort :: Ord a => f a -> f a>   sort = over (partsOf traverse) Data.List.sort>   default>     sort :: Ord a => Traversable f => f a -> f a2016-11-27 7:53 GMT+00:00 David Feuer :I disagree with many of these. For example, I think of takeWhile as having a type shaped like takeWhile :: (a -> Bool) -> f a -> f a Implementations are available for, e.g., sequences, sets, and maps. I don't really want some silly list producer. If I want takeWhile.toList, I know where to get it. Similarly, if I want distribute (which I haven't yet), I know where to get it. Some of these proposals also have substantial performance penalties, such as the sort generalization (which also can't be written in an "obviously total" manner, unfortunately). On Nov 27, 2016 2:10 AM, "Baldur Blöndal" <[hidden email]> wrote:A year ago Edwardk Kmett pointed out some possible generalizations of functions [1], I made a ticket about them that led me here [2]. In addition to the functions mentioned> maybeToList :: Foldable f => f a -> [a]> maybeToList = toList> catMaybes :: (Foldable f)             => f (Maybe a) -> [a]> catMaybes :: (Foldable f, Foldable g) => f (g     a) -> [a]> catMaybes = foldMap toList> mapMaybes ::               (a -> Maybe b) -> (forall f. Foldable f => f a -> [b])> mapMaybes :: Foldable m => (a -> m     b) -> (forall f. Foldable f => f a -> [b])> mapMaybes f = foldMap (toList . f)we also have *many* other functions (I do not propose generalising all these function ((especially when the name stops making sense)), but I will include them) that I will define in the vocabulary of ‘lens’. Some generalise to ‘Foldable’> take :: Int -> (forall f a. Foldable f => f a -> [a])> take n = toListOf (taking n folded)> drop :: Int -> (forall f a. Foldable f => f a -> [a])> drop n = toListOf (dropping n folded)> takeWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> takeWhile p = toListOf (takingWhile p folded)> dropWhile :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> dropWhile p = toListOf (droppingWhile p folded)> -- Same as ‘Control.Lens.Indexed.None’> filter :: (a -> Bool) -> (forall f. Foldable f => f a -> [a])> filter p = toListOf (folded.filtered p)> cycle :: Foldable f => f a -> [a]> cycle = toListOf (cycled folded)> lookup :: Eq k => k -> (forall f. Foldable f => f (k, v) -> Maybe v)> lookup = lookupOf folded> listToMaybe :: Foldable f => f a -> Maybe a> listToMaybe = firstOf foldedwhile others — to ‘Traversable’> transpose :: Traversable f => f [b] -> [f b]> transpose = transposeOf traverse> scanl1 :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanl1 = scanl1Of traverse> scanr1_ :: (a -> a -> a) -> (forall f. Traversable f => f a -> f a)> scanr1_ = scanr1Of traverseMore radical suggestions (pay no heed to the hacky ‘partsOf’, assume better implementation [3]) would allow us to sort a ‘data V2 a = V2 a a deriving (…, Traversable)’ if it contains ordered values:> sort :: (Traversable t, Ord a) => t a -> t a> sort = over (partsOf traverse) Data.List.sort> sortBy :: (a -> a -> Ordering) -> ([a] -> [a])> sortBy = over (partsOf traverse) . Data.List.sortBy> sortOn :: Ord b => (a -> b) -> ([a] -> [a])> sortOn = over (partsOf traverse) . Data.List.sortOn> reverse :: Traversable t => t a -> t a> reverse = over (partsOf traverse) Data.List.reverse> -- Based on ‘Control.Lens.??’> flip :: Functor f => f (a -> b) -> a -> f b > flip f x = fmap (\$ x) for > flip :: (Functor f, Distributive g) => f (g a) -> g (f a)> flip = Data.Distributive.distributeAMP happened some years ago, does this go too far or not far enough? ;) share your thoughtsP.s. I understand those skeptical of the ‘partsOf’ solutions but they do feel magical and uses crop up in odd places, especially in compound structures (I don't have better examples):> ghci> peopleList = Pair ["Bob", "Eve"] (Just "Alice")> ghci> data Product f g a = Pair (f a) (g a) deriving (Show, Functor, Foldable, Traversable)> ghci> sort peopleList> Pair ["Alice","Bob"] (Just "Eve")> ghci> reverse peopleList> Pair ["Alice","Eve"] (Just "Bob")> ghci> peopleMap = fromList [(1,"Bob"),(2,"Eve"),(3,"Alice")] > ghci> sort peopleMap> fromList [(1,"Alice"),(2,"Bob"),(3,"Eve")]> ghci> reverse peopleMap> fromList [(1,"Alice"),(2,"Eve"),(3,"Bob")] _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 Meant > elemIndices :: Eq a => a -> Foldable f => f a -> [Int] _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

Open this post in threaded view
|

## Re: Many functions can be generalised

 In reply to this post by Baldur Blöndal On 09:08 Wed 30 Nov     , Baldur Blöndal wrote: > P.s. At least I did not propose ↓ yet :) > > > shuffleM :: (Foldable f, MonadRandom m) => f a -> m (f a) This would be an utter nonsense, given that many if not most foldables either don't have an order like Set or must have very specific order like different kinds of trees and therefore cannot be shuffled. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 This was probably supposed to be a Traversable constraint. I still suspect it would be unwise, because there may be data structures that can be shuffled more efficiently than this type would allow. On Nov 30, 2016 6:22 PM, "Lana Black" <[hidden email]> wrote:On 09:08 Wed 30 Nov     , Baldur Blöndal wrote: > P.s. At least I did not propose ↓ yet :) > > > shuffleM :: (Foldable f, MonadRandom m) => f a -> m (f a) This would be an utter nonsense, given that many if not most foldables either don't have an order like Set or must have very specific order like different kinds of trees and therefore cannot be shuffled. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 In reply to this post by Baldur Blöndal On 2016-11-30 04:08 AM, Baldur Blöndal wrote: > What about functions that aren't expected to preserve structure like > ‘lookup’ and (new) suggestions > >> lookup :: Eq a => k -> Foldable f => f (k, v) -> Maybe v >> lookup = lookupOf folded -1. It needs to die. >> elemIndex :: Eq a => a -> Foldable f => f a -> Maybe Int >> elemIndex = elemIndexOf folded > >> elemIndices :: Eq a => a -> Foldable f => f a -> Maybe Int >> elemIndices = elemIndicesOf folded > >> findIndex :: (a -> Bool) -> Foldable f => f a -> Maybe Int >> findIndex = findIndexOf folded > >> findIndices :: (a -> Bool) -> Foldable f => f a -> [Int] >> findIndices = findIndicesOf folded         I'm +0.5 on these but only if they come in together with the (!!) operator, which should then be added as a Foldable class method to allow for optimizations. Without (!!) there'd be no way to express the laws these operations need to satisfy. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 In reply to this post by wren romano-2 On Mon, Nov 28, 2016 at 4:41 PM, wren romano wrote:I'd much rather see the above functions as:     mapMaybes :: Foo f => (a -> Maybe b) -> f a -> f b     catMaybes :: Foo f => f (Maybe a) -> f a A while back, I found myself deriving this class:    class Functor f => Siftable f where        siftWith :: (a -> Maybe b) -> f a -> f b        sift :: (a -> Bool) -> f a -> f a        sift f = siftWith (\a -> if f a then Just a else Nothing)which is essentially Witherable minus Traversable. It has the nice property that it’s a functor from the Kleisli category for Maybe to Hask, so the laws are intuitive and easily expressed. You can even express wither using siftWith and traverse    wither :: (Siftable t, Traversable t, Applicative f) => (a -> f (Maybe b)) -> t a -> f (t b)    wither f = fmap (siftWith id) . traverse fBut it turns out that there aren’t many instances of Siftable that aren’t also Traversable. The most obvious would be infinite streams, but even they have a traversal if you restrict yourself to lazy applicatives.-- Dave Menendez <[hidden email]> _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 On Dec 2, 2016 6:14 PM, "David Menendez" <[hidden email]> wrote:A while back, I found myself deriving this class:    class Functor f => Siftable f where        siftWith :: (a -> Maybe b) -> f a -> f b        sift :: (a -> Bool) -> f a -> f a        sift f = siftWith (\a -> if f a then Just a else Nothing)I would expect several classes, corresponding to different methods of Witherable:class Siftable a m | m -> a where  sift :: (a -> Bool) -> m -> m  default sift :: SiftWithable f => (a -> Bool) -> f a -> f a  sift p = siftWith (\x -> x <\$ guard (p x))class Functor f => SiftWithable f where  siftWith :: (a -> Maybe b) -> f a -> f bclass Siftable a m => SiftableA a m where  siftA :: Applicative g => (a -> g Bool) -> m -> g m  default siftA :: (SiftWithAAble f, Applicative g) => (a -> g Bool) -> f a -> g (f a)  siftA p = siftWithA (\x -> (x <\$) . guard <\$> p x)class (Traversable f, SiftWithAble f) => SiftWithAAble f where  siftWithA :: Applicative g => (a -> g (Maybe b)) -> f a -> g (f a) _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 On Sat, Dec 3, 2016 at 12:50 AM, David Feuer wrote:On Dec 2, 2016 6:14 PM, "David Menendez" <[hidden email]> wrote:A while back, I found myself deriving this class:    class Functor f => Siftable f where        siftWith :: (a -> Maybe b) -> f a -> f b        sift :: (a -> Bool) -> f a -> f a        sift f = siftWith (\a -> if f a then Just a else Nothing)I would expect several classes, corresponding to different methods of Witherable:class Siftable a m | m -> a where  sift :: (a -> Bool) -> m -> m  default sift :: SiftWithable f => (a -> Bool) -> f a -> f a  sift p = siftWith (\x -> x <\$ guard (p x))class Functor f => SiftWithable f where  siftWith :: (a -> Maybe b) -> f a -> f bclass Siftable a m => SiftableA a m where  siftA :: Applicative g => (a -> g Bool) -> m -> g m  default siftA :: (SiftWithAAble f, Applicative g) => (a -> g Bool) -> f a -> g (f a)  siftA p = siftWithA (\x -> (x <\$) . guard <\$> p x)class (Traversable f, SiftWithAble f) => SiftWithAAble f where  siftWithA :: Applicative g => (a -> g (Maybe b)) -> f a -> g (f a) Yes, sift is more general than siftWith (which I should have called siftMap, in hindsight). But, so far as I know, the only things you can define sift for but not siftWith are sets and set-like things.At the time, I had also rejected sift by itself because I couldn’t think of any laws, but now that I look at it again, I guess they would be:    sift (const True) = id    sift (\x -> p x && q x) = sift q . sift pI think those would make sift a monoid homomorphism.These still allow some weird instances, like sift _ = id, or something like this:    newtype Weird a = Map a Bool    instance Ord a => Siftable a (Weird a) where        sift p (Weird m) = Weird (Map.union (Map.updateMin (const False) yes) no)            where            (yes, no) = Map.partitionWithKey (const . p) mI imagine it isn’t worth making the laws tighter to forbid this.-- Dave Menendez <[hidden email]> _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 You can also sift monomorphic containers using my class, which should probably be called MonoSiftable.data IntList = Cons !Int IntList | Nilinstance Siftable Int IntList where  sift _ Nil = Nil  sift p (Cons x xs)    | p x = Cons x (sift p xs)    | otherwise = sift p xsOn Dec 3, 2016 2:17 PM, "David Menendez" <[hidden email]> wrote:On Sat, Dec 3, 2016 at 12:50 AM, David Feuer wrote:On Dec 2, 2016 6:14 PM, "David Menendez" <[hidden email]> wrote:A while back, I found myself deriving this class:    class Functor f => Siftable f where        siftWith :: (a -> Maybe b) -> f a -> f b        sift :: (a -> Bool) -> f a -> f a        sift f = siftWith (\a -> if f a then Just a else Nothing)I would expect several classes, corresponding to different methods of Witherable:class Siftable a m | m -> a where  sift :: (a -> Bool) -> m -> m  default sift :: SiftWithable f => (a -> Bool) -> f a -> f a  sift p = siftWith (\x -> x <\$ guard (p x))class Functor f => SiftWithable f where  siftWith :: (a -> Maybe b) -> f a -> f bclass Siftable a m => SiftableA a m where  siftA :: Applicative g => (a -> g Bool) -> m -> g m  default siftA :: (SiftWithAAble f, Applicative g) => (a -> g Bool) -> f a -> g (f a)  siftA p = siftWithA (\x -> (x <\$) . guard <\$> p x)class (Traversable f, SiftWithAble f) => SiftWithAAble f where  siftWithA :: Applicative g => (a -> g (Maybe b)) -> f a -> g (f a) Yes, sift is more general than siftWith (which I should have called siftMap, in hindsight). But, so far as I know, the only things you can define sift for but not siftWith are sets and set-like things.At the time, I had also rejected sift by itself because I couldn’t think of any laws, but now that I look at it again, I guess they would be:    sift (const True) = id    sift (\x -> p x && q x) = sift q . sift pI think those would make sift a monoid homomorphism.These still allow some weird instances, like sift _ = id, or something like this:    newtype Weird a = Map a Bool    instance Ord a => Siftable a (Weird a) where        sift p (Weird m) = Weird (Map.union (Map.updateMin (const False) yes) no)            where            (yes, no) = Map.partitionWithKey (const . p) mI imagine it isn’t worth making the laws tighter to forbid this.-- Dave Menendez <[hidden email]> _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 On Sat, Dec 3, 2016 at 2:32 PM, David Feuer wrote:You can also sift monomorphic containers using my class, which should probably be called MonoSiftable.data IntList = Cons !Int IntList | Nilinstance Siftable Int IntList where  sift _ Nil = Nil  sift p (Cons x xs)    | p x = Cons x (sift p xs)    | otherwise = sift p xsYou can also use it with contra-variant or invariant type constructors, e.g.,instance Siftable a (a -> Bool) where    sift f g = \x -> f x && g x-- Dave Menendez <[hidden email]> _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Many functions can be generalised

 On Dec 4, 2016 12:22 AM, "David Menendez" <[hidden email]> wrote:You can also use it with contra-variant or invariant type constructors, e.g.,instance Siftable a (a -> Bool) where    sift f g = \x -> f x && g xThat looks backwards for your composition law, but I'm a bit tired so I wouldn't swear to it.Surely you can do the same with the constructor class.newtype Ab a = Ab (a -> Bool)instance Siftable Ab where  siftAway _ = Ab (const False)  sift p (Ab g) = Ab ...I'm not sure if my siftAway excludes anything it shouldn't.... _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries