Applicative Uniplate

[mbrock]

Hello!

As it happens, I'm writing some code to do concurrent fetching of resources as a Traversal, and this involves an applicative promise-like thing. It would be very convenient to then be able to perform this applicative traversal at certain leafs in a big data structure. This is possible with lens, but (I think) not with the currently released Uniplate—but we avoid lens, and already use lots of Uniplate!

Coincidentally I saw that @ndmitchell was working on applicativizing Uniplate only recently, so actually this is less of an "issue" and more of a curious inquiry into the status, whether this will be released, etc. :)

The code is already mostly done anyway, but with some ugly manual descent/replace, and it would be be fun to get rid of this!

[ndmitchell]

Hi @mbrock. I did indeed start moving Uniplate towards being based on Applicative, using some of the techniques from the lens library (which itself used some of the techniques from Uniplate). The primary motivation was that the lens people said in their benchmarks that Applicative went faster than my Str data type that Uniplate used before that. However, I found:

• Lens is a fair bit slower than Uniplate, even in the worst case when they are doing the same operations, specifically queries using the Data variant of Uniplate.
• If I port Uniplate to Applicative, it goes slower than currently.

So I think the lens people discovered Lens-Applicative is faster than Lens-Str, but the whole performance list is: Lens-Str < Lens-Applicative < Uniplate-Applicative < Uniplate-Str. That said, being based on Applicative is certainly cleaner, from a theoretical perspective. As a result I'm in a bit of a quandary - push ahead with something cleaner but slower, or leave it as it is.

Any chance of you pasting a fragment of your descent/replace stuff, and I'll see if that wasn't possible before, but is possible now? If so, the additional power might convince me towards Applicative.

[mbrock]

Thanks @ndmitchell, interesting stuff!

Here's what I want to do. Given

fetch :: URL -> Delayed Result

traverseDelayed :: Traversable t => (a -> Delayed b) -> t a -> Delayed (t b)

data Page = Page { title :: Text, links :: [Either URL Result] }

I want to transform, say, a Vector Page into a Delayed (Vector Page) with fetch applied to all links. This is slightly made up, and really the Page structure is a bit more deeply nested.

This would all be very easy if Delayed was a monad, but it's not, by design. These delayed values are made up of an initialize action and a read action, and when combined applicatively, the initializers are combined so that they can all be run at once. The effect in this case is that all URLs fetched during a traverseDelayed will be fetched concurrently.

I don't think there is a way to implement Monad for this type without losing the concurrency. The implementation of Delayed is an IO (IO a) (aka Compose IO IO a), and binding involves join, and to join these values means to conflate the initialization and the reading, which means introducing premature blocking. This is just the thing Simon Marlow's Haxl package is all about—you probably see the point!

Anyway, I guess the general story is simply that (<*>) can sometimes be much smarter than (>>=), and it would be sweet to be able to do biplate transforms that don't bind!

[ndmitchell]

You can already write the function you are after using the existing Uniplate library. You can define:

import Data.Generics.Str
import Data.Generics.Uniplate.Operations
import Control.Applicative

descendBiA :: Biplate from to => Applicative m => (to -> m to) -> from -> m from
descendBiA f x = case biplate x of
    (current, generate) -> generate <$> strMapA f current

strMapA :: Applicative m => (a -> m b) -> Str a -> m (Str b)
strMapA f Zero = pure Zero
strMapA f (One x) = One <$> f x
strMapA f (Two x y) = Two <$> strMapA f x <*> strMapA f y

Now descendBiA probably will do what you want. In the new Uniplate that would be just descendBiM.

However, I suspect there is a better option. You could try:

{-# LANGUAGE DeriveTraversable, DeriveFoldable, DeriveFunctor #-}

import Data.Traversable
import Data.Foldable
import Control.Applicative

data Page a  = Page {title :: String, links :: [a]}
    deriving (Traversable, Functor, Foldable)

download :: Page URL -> Delayed (Page Result)
download = traverse fetch

Now Page is statically typed to determine which type of thing it contains, either URL's or results. By defining Page as a Traversable data type (which new versions of GHC can derive automatically) your download function becomes simple.

[mbrock]

Oh, excellent, thanks a lot! I didn't realize it would be so easy to define the descendBiA function on top of the existing Uniplate.

Maybe descendBiA would be a good backwards-compatible addition to the Str-based Uniplate?

Yes, making Page polymorphic is also a nice solution, but in this case I'd like to avoid changing the type.

[ndmitchell]

Yes, I'll consider adding descendBiA - but I may wait a bit to dwell on what I do with basing it on Applicative or not first. I really want to unify under one code base before changing the API.

[neomaclin]

not sure I am hijacking the thread here. If possible, would love to see this lib could be ported into SCB's libs.

mostly because this I saw on SO.

descend (\x -> 2*x) (1,2,3,4,5) == (2,4,6,8,10)

it will be a life saver.

[ndmitchell]

What do you mean by "SCB's libs"? "Standard Chartered Bank"? If so, please reach out to me via internal OCS and I'll explain what you really want instead.

[neomaclin]

Cool! Thanks Neil!

[ndmitchell]

I made the change some time ago, but it seems to make things go slower, and I never got around to taking a proper look at it. Uploading the revised file (which may well not compile in isolation or when dropped over the existing code), more as a placeholder for when I get back to uniplate.

OperationsInc.zip

[googleson78]

I see that this change was made on master, but isn't published on Hackage. Is it still worse than the Str variant?

[ndmitchell]

Seemingly a bit slower, yes - at least at the time I made the change. It needs to either be finished off, or abandoned, and unfortunately I just left it in a half-done state...

[ndmitchell]

I rolled it back. Yes, it was slower, and whether to move forward or not was ambiguous, so rolled it back, shoved it on a branch, and cherry picked the interesting stuff over.

But as of now there is descendM using Applicative only, so hopefully that's helping and gives what this ticket was asking for.