[Haskell-cafe] gathering position information lazily using traverse

[Jan Christiansen]

On 10.09.2010, at 23:58, Felipe Lessa wrote:

> Hmmmm...
>
> On Fri, Sep 10, 2010 at 6:47 PM, Jan Christiansen
> <jac at informatik.uni-kiel.de> wrote:
>>  instance Applicative Proj where
>>    pure = Proj . const
>>    Proj f <*> Proj x = Proj (\p -> f (False:p) (x (True:p)))
>
>  (pure f) <*> Proj x
>   === Proj (const f) <*> Proj x
>   === Proj (\p -> (const f) (False:p) (x (True:p)))
>   === Proj (\p -> f (x (True:p)))
>
>  Proj f <*> (pure x)
>   === Proj f <*> Proj (const x)
>   === Proj (\p -> f (False:p) ((const x) (True:p)))
>   === Proj (\p -> f (False:p) x))
>
>>  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)))
>
>  (pure f) <*> Proj x
>   === Pure f <*> Proj x
>   === Proj (\p -> f (x p))
>
>  (Proj f) <*> (pure x)
>   === Proj f <*> Pure x
>   === Proj (\p -> f p x)
>
> Was this difference intended?

Yes, this is intended. This difference is the reason why the former  
instance does not satisfy the Applicative laws while the latter does.

The first instance provides every subterm of an idiomatic term with a  
position. Even a "pure" term is provided with a position although it  
does not use it. The latter instance does not provide a "pure" term  
with a position as it does not need one. Therefore, the second  
instance simply passes position p to a subterm if the other subterm is  
pure. In the example for the first instance we can observe that we  
unnecessarily extend the position with True and False respectively.