types - recurse over same type?

[soupi]

Hi! First I'd like to thank you for this super cool package!

I was wondering why doesn't types recurse deeper when the Traversal focus has the same type as the "big" outer type.

Example:

{-# language LambdaCase, DeriveDataTypeable, DeriveGeneric, TypeApplications #-}

import GHC.Generics
import Data.Data

data Expr
  = Lit Int
  | Add Expr Expr
  | Sub Expr Expr
  | Mul Expr Expr
  deriving (Show, Data, Generic)

expr :: Expr
expr = Add (Sub (Lit 1) (Lit 2)) (Lit 3)

f :: Expr -> Expr
f = \case
    Add a b -> Mul a b
    Lit i -> Lit (i + 1)
    a -> a

When I run over types f expr i get: Mul (Sub (Lit 1) (Lit 2)) (Lit 3) - meaning only the outer Expr has been transformed (shallow).

When I run over (types @Int) (+1) expr I get: Add (Sub (Lit 2) (Lit 3)) (Lit 4) - meaning all of the Ints have been transformed (deep).

Coming from uniplate and Control.Lens.Plated I'd expect over types to work similarly to transformBi and toListOf types to work like universeBi, but it only doesn't when the focus type is the same:

λ> import Data.Generics.Uniplate.Data
λ> import Data.Generics.Product
λ> import Control.Lens

λ> over (types @Int) (+1) expr
Add (Sub (Lit 2) (Lit 3)) (Lit 4)
λ> transformBi ((+1) :: Int -> Int) expr
Add (Sub (Lit 2) (Lit 3)) (Lit 4)

λ> over types f expr
Mul (Sub (Lit 1) (Lit 2)) (Lit 3)
λ> transformBi f expr
Mul (Sub (Lit 2) (Lit 3)) (Lit 4)

λ> universeBi expr :: [Int]
[1,2,3]
λ> toListOf (types @Int) expr
[1,2,3]

λ> toListOf (types @Expr) expr
[Add (Sub (Lit 1) (Lit 2)) (Lit 3)]
λ> universeBi expr :: [Expr]
[Add (Sub (Lit 1) (Lit 2)) (Lit 3),Sub (Lit 1) (Lit 2),Lit 1,Lit 2,Lit 3]

Any reason for the behaviour differences?

Thanks in advance!

[Lysxia]

It's a bit unfortunate that when the types are the same it degenerates to the identity traversal. I think that if `types` **at least went one level deep**, then the recursive `transform` would be a one-liner: ``` transform :: (...) => (a -> a) -> (a -> a) transform f = f . over types f ``` A non-recursive traversal composes better and has nicer properties than a recursive (SYB-style) one. In particular, the above shows that a non-recursive traversal can be used to create recursive traversals quite concisely (and not conversely). In addition, recursive traversals probably break some traversal laws (`over h f . over h g = over h (f . g)`), because of the overlapping foci (the usual suspect). For those reasons they might not seem to be as fundamental as non-recursive traversals.

[soupi]

After further inspection following your tip regarding non-recursive traversals it seems like types has the same semantics as childrenBi and descendBi from uniplate:

λ> descendBi f expr
Mul (Sub (Lit 1) (Lit 2)) (Lit 3)
λ> descendBi ((+1) :: Int -> Int) expr
Add (Sub (Lit 2) (Lit 3)) (Lit 4)

λ> U.childrenBi expr :: [Expr]
[Add (Sub (Lit 1) (Lit 2)) (Lit 3)]
λ> U.childrenBi expr :: [Int]
[1,2,3]

[neongreen]

Is there a way to implement this using current types?

[soupi]

I might be mistaken, but I don't think you can.

[georgefst]

If this behaviour isn't changing any time soon (from the above discussion, it's not clear to me whether it even can be "fixed"), it would be great to at least have a comment in the documentation.

I've just spent a while debugging an issue where I was implicitly expecting types @a @a to recurse. I also for some reason assumed that the outermost expression wouldn't be traversed, but perhaps that part should have been more obvious. Either way, I think the behaviour could do with clarification.