[Haskell-cafe] What class for splittable data / balanced-fold?
Ryan Newton
rrnewton at gmail.com
Mon Sep 30 03:13:06 CEST 2013
Thanks, that's interesting to know (re: Fortress).
Interestingly, in my Fortress days we looked at both using a split-like
> interface and at a more foldMap / reduce - like interface, and it seemed
> like the latter worked better – it requires a lot less boilerplate for
> controlling recursion, and better matches the fanout of whatever structure
> you're actually using underneath.
>
Ok, we'll have to try that. I may be underestimating the power of a
newtype and a monoid instance to expose the structure.. I was wrong about
this before [1]. Here's the foldMap instance for Data.Map:
foldMap _ Tip = mempty foldMap f (Bin _ _ v l r) = Foldable.foldMap
f l `mappend` f v `mappend` Foldable.foldMap f r
Simon Marlow in his recent Haxl talk also had a domain where they
wanted a symmetric (non-monadic) parallel spawn operation...
But it remains pretty hard for me to reason about the operational
behavior of these things... especially since foldMap instances may
vary.
Thanks,
-Ryan
[1] For example, here is a non-allocating traverseWithKey_ that I
failed to come up with:
-- Version of traverseWithKey_ from Shachaf Ben-Kiki
-- (See thread on Haskell-cafe.)
-- Avoids O(N) allocation when traversing for side-effect.
newtype Traverse_ f = Traverse_ { runTraverse_ :: f () }
instance Applicative f => Monoid (Traverse_ f) where
mempty = Traverse_ (pure ())
Traverse_ a `mappend` Traverse_ b = Traverse_ (a *> b)
-- Since the Applicative used is Const (newtype Const m a = Const m), the
-- structure is never built up.
--(b) You can derive traverseWithKey_ from foldMapWithKey, e.g. as follows:
traverseWithKey_ :: Applicative f => (k -> a -> f ()) -> M.Map k a -> f ()
traverseWithKey_ f = runTraverse_ .
foldMapWithKey (\k x -> Traverse_ (void (f k x)))
foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r
foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k x))
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130929/892e2b3d/attachment.htm>
More information about the Haskell-Cafe
mailing list