[Haskell-cafe] gathering position information lazily using traverse
Jan Christiansen
jac at informatik.uni-kiel.de
Fri Sep 10 17:47:29 EDT 2010
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
More information about the Haskell-Cafe
mailing list