search

ekmett / lens

Lenses, Folds, and Traversals - Join us on web.libera.chat #haskell-lens
http://lens.github.io/
Other
2.03k stars 271 forks source link

Add a shapely holesOf variant #787

Open treeowl opened 6 years ago

treeowl commented 6 years ago

The fancy type of holesOf is utterly mysterious to me, but going back in time there was

holesOf :: LensLike (Bazaar a a) s t a a -> s -> [Context a a t]

If we're dealing with a Traversable container, or the right sort of (polymorphic?) traversal function, we can do something like this instead:

holesOf' :: Traversable t => t a -> t (Context a a t)

This retains the correspondence between contexts and data structure positions that holesOf throws away. Of course, this could be implemented a bit shadily by traversing the container with the result of holesOf, but I'm rather curious whether it would be possible to come up with a version that works for structures that extend infinitely in both directions.

treeowl commented 6 years ago

Here's the beginning of an idea. I don't know if it can be made to work

data FM a t where
  Map :: (t -> u) -> FM a t -> FM a u
  Pure :: t -> FM a t
  Leaf :: (a -> t) -> a -> FM a t
  Branch :: (x -> y -> z) -> FM a x -> FM a y -> FM a z

instance Functor (FM a) where
  fmap = Map

instance Applicative (FM a) where
  pure = Pure
  liftA2 = Branch

runFM :: FM a t -> t
runFM (Map f t) = f (runFM t)
runFM (Pure t) = t
runFM (Leaf f a) = f a
runFM (Branch f xs ys) = f (runFM xs) (runFM ys)

bp :: a -> FM a a
bp a = Leaf id a

foo :: Traversable t => t a -> FM a (t a)
foo = traverse bp

Traversing a container with bp (as foo does) produces a tree precisely reflecting the structure of the traversal, which runFM will turn back precisely into the original tree. We can modify any as we like in the tree (somehow) and runFM it to get a new container. But making an FM a u that will produce the container of contexts seems a bit tricky with this type. Might be possible, or might not be.

treeowl commented 6 years ago

I guess this structure is pretty much the same as Magma. Both seem similarly complicated by a lack of polymorphism.

Separate thought: can we traverse a Magma using a zipper as a sort of index? I imagine so. Is that the right way to build the contexts?

treeowl commented 6 years ago

Aha! I got one! It's a little ugly, but I think bearable. See my answer to myself on SO.