haskell
Foldable Conversions
This is related to some of what I brought up in https://github.com/haskell/containers/issues/338. I was just working with Data.Set and wanted to call unions on some foldable collection of Sets. I can just write:
unions . toList
And that works fine. And for some data structures, the intermediate list may even get fused away. Maybe. But any time I have to call toList on a Foldable, I'm unsatisfied because whatever cosumes the list could have been written to just fold over the collection instead. It seems like generalizing unions should be possible (although it does use a special variant of foldl).
Additionally, having a fromFoldable would be nice. It would be misleading to generalize fromList since the name would then be misleading.
But for the most part, I would like the see the functions whose names don't explicitly mention the word "list" be generalized, with rewrite rules to use the tunes list variants when possible.
unions should be fine. However, some of the conversions from lists rely
pretty heavily on pattern matching the list. I don't know how to make a
fromFoldable for Data.Sequence that's any better than S.fromList .
F.toList. If you can find one, I'd be very happy to include it. I think the
same goes for sets and maps, to some extent, although there are some
substantial changes I want to make there that may or may not change the
situation in either direction.
On Oct 21, 2016 10:06 AM, "Andrew Martin" [email protected] wrote:
This is related to some of what I brought up in #338 https://github.com/haskell/containers/issues/338. I was just working with Data.Set and wanted to call unions on some foldable collection of Sets. I can just write:
unions . toList
And that works fine. And for some data structures, the intermediate list may even get fused away. Maybe. But any time I have to call toList on a Foldable, I'm unsatisfied because whatever cosumes the list could have been written to just fold over the collection instead. It seems like generalizing unions should be possible (although it does use a special variant of foldl).
Additionally, having a fromFoldable would be nice. It would be misleading to generalize fromList since the name would then be misleading.
But for the most part, I would like the see the functions whose names don't explicitly mention the word "list" be generalized, with rewrite rules to use the tunes list variants when possible.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/issues/351, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_Q-xm4sh2Rh5o5Y7TiLQABYztoi4ks5q2Mb8gaJpZM4KdQ2p .
Perhaps my reasoning is a bit naive, but if we were attempting to change the type signature of unions to no longer be list specific and instead be more generally defined in terms of a Foldable structure, couldn't we do the following:
Change:
unions :: Ord a => [Set a] -> Set a
unions = foldlStrict union empty
To:
unions :: (Foldable f, Ord a) => f (Set a) -> Set a
unions = foldl' union empty
Hi. While using Data.Map, I noticed that I can only construct one from List, and not from any Foldable. Looking at the code, I see that fromListWith and fromListWithKey don't use specificly List, only Foldable.foldl'. (for fromList, not so much ^)
While browsing the issue here, I see this has come up several times, but not sure whether there is a definitive answer.
So, would you consider a PR generalizing the two functions mentionned ? Should the other from*ListWith also generalized ?
P.S. : I'm quite new to Haskell, so please correct me if I've missed reasons why this is the way it is.
unions was generalized to use Foldable in #524.
Regarding fromFoldable, I think it would be good to add such definitions if they have a performance advantage over fromList by not having to create a list.
This will be true for Set and Map if #1042 makes it in. Not so much for other types at the moment.
It does seem redundant to add fromFoldable, fromFoldableWith, fromFoldableWithKey in addition to the list functions, but it can't be helped. I agree that generalizing the existing functions would make the names misleading.
Since #1042 made it in, fromList for all sets and maps are now defined as foldl' and I'm considering adding fromFoldable. But it's not perfect because it should be possible to fold over non-Foldable types (like unboxed vectors) to create a set/map.
What would be really nice is if we could offer a Fold as defined by the foldl library.
intoSet :: Fold a (Set a)
intoMap :: Fold (k, a) (Map k a)
Then a user can use the Fold as they please with any container, whether Foldable or not. But of course, we cannot depend on foldl.
An alternative is to expose the individual components of the Fold, including the internal type that accumulates elements. This seems low-level to me, and cumbersome to use compared to Fold.
emptyB :: SetBuilder a
insertB :: Ord a => a -> SetBuilder a -> SetBuilder a
finishB :: SetBuilder a -> Set a
Another option is to take the foldl' function as input.
fromFoldl' :: (forall b. (b -> a -> b) -> b -> f -> b) -> f -> Set a
This is a bit awkward to use and a little ugly IMO. It is also less powerful than the above alternatives. For instance, it can't be used to build monadically, unlike the Fold or SetBuilder options.