Dear Applicative experts,

I am seeking advice on Applicative instances and their use in traverse. Consider the following Applicative instance.

  newtype Proj a = Proj { unProj :: [Bool] -> a }

  instance Functor Proj where
    fmap g (Proj f) = Proj (g . f)

  instance Applicative Proj where
    pure = Proj . const
    Proj f <*> Proj x = Proj (\p -> f (False:p) (x (True:p)))

In fact, this is not an Applicative instance as it does not satisfy the laws. On basis of this "instance" I have defined the following function.

  gshape :: Traversable t => t a -> t [Bool]
  gshape x = unProj (traverse (const (Proj reverse)) x) []

The idea is simply to replace every polymorphic component by an identifier that identifies the position of the component in the data structure. That is, provided with the identifier I want to be able to project to the corresponding component. In this case this identifier is a path in the "idiomatic term" from the root to the component.

I can define a correct Applicative instance if I add an additional constructor, which represents pure. I did not prove that it satisfies all laws but I think it does.

  data Proj a = Pure a | Proj ([Bool] -> a)

  instance Functor Proj where
    fmap g (Pure x) = Pure (g x)
    fmap g (Proj f) = Proj (g . f)

  instance Applicative Proj where
    pure x = Pure x
    Pure f <*> Pure x = Pure (f x)
    Pure f <*> Proj x = Proj (\p -> f (x p))
    Proj f <*> Pure x = Proj (\p -> f p x)
    Proj f <*> Proj x = Proj (\p -> f (False:p) (x (True:p)))

My problem is that this correct instance is too strict for my purpose. It is important that gshape operates correctly on partial data, that is, even if its argument is partial all the components should be replaced correctly. For example, we have

  gshape (Node _|_ 0 (Leaf 1))) = Node _|_ [False,True] (Leaf [True])


If the applicative instance performs pattern matching, like the latter instance, then gshape is too strict. Therefore I suspect that there is no correct Applicative instance that satisfies my needs but I am not at all certain.

Thanks, Jan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to