Uniplate.Data with nested datatype doesn't terminate

[ndmitchell]

From https://code.google.com/p/ndmitchell/issues/detail?id=490

What steps will reproduce the problem?

1. Load the attached file into ghci or compile it with ghc.
2. Evaluate (e.g. by printing) test1 or test2

What is the expected output? What do you see instead?

Immediate evaluation and:

test1: [1] test2: [2,3,5,7,11,13,17,19]

What version of the product are you using? On what operating system? (Saying "latest" is fine, especially for Hoogle web search)

Latest.

Please provide any additional information below.

If you abort the operation early, you see the value. If you don't, then your memory is consumed by an exploding computation.

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE StandaloneDeriving #-}

module PerfectDatatype where

import Data.Generics
import Data.Generics.Uniplate.Data

data Perfect a = Zero a | Succ (Perfect (Fork a)) deriving (Show, Data)
data Fork a = Fork a a deriving (Show, Data)

deriving instance Typeable1 Perfect
deriving instance Typeable1 Fork

selectIntPerfect :: Perfect Int -> [Int]
selectIntPerfect = universeBi

ex1 :: Perfect Int
ex1 = Zero 1

ex2 :: Perfect Int
ex2 = Succ (Succ (Succ (Zero (Fork (Fork (Fork 2 3)
                                         (Fork 5 7))
                                   (Fork (Fork 11 13)
                                         (Fork 17 19))))))

test1 :: [Int]
test1 = selectIntPerfect ex1

test2 :: [Int]
test2 = selectIntPerfect ex2

[flip111]

My program uses uniplate and specifically the transformBi function and doesn't terminate. I use uniplate to transformations on a syntax tree after getting the idea from http://stackoverflow.com/a/20171291/1833322 I'm a new user to haskell and so far i have only a suspicion that the bug is caused by this issue but no hard proof (yet). Tracking this down was already pretty hard to do, see https://ghc.haskell.org/trac/ghc/ticket/12696

Some questions:

1. How can i know for sure this issue causes the non-termination of my program? Or is this already obvious from the GHC ticket?
2. How difficult would it be to fix this ticket (#9) in uniplate? Is this ticket still getting attention?
3. Are there any alternatives to transformBi either in uniplate or perhaps an alternative library?

Every day i try to make some progression on my program but i've been stuck for 2 weeks now, so i'm pretty eager to get this solved.

[flip111]

As a workaround i've been using Uniplate.Direct. But the boilerplate i have to write is getting a bit out of hand. For example i have this transformation

aeis :: Biplate from Identifier => from -> from
aeis = transformBi x
  where x (IExtended a) = let updated_text :: Text
                              updated_text = T.concat ["\\", snd $ t_text a, "\\"]
                          in IExtended $ a {t_text = (fst $ t_text a, updated_text)}
        x a = a

Now from each type that can (eventually) contain Identifier i have to write an instance of Biplate. Here a few examples:

instance Biplate ContextClause Identifier where
  biplate (CC x) = plate CC ||+ x

instance Biplate ContextItem Identifier where
  biplate (CI_Library x) = plate CI_Library |+ x

instance Biplate LibraryClause Identifier where
  biplate (LC x y z) = plate LC |- x |+ y |- z

instance Biplate LogicalNameList Identifier where
  biplate (LNL x y) = plate LNL |+ x ||+ y

instance Biplate (Terminal, NonTerminal LogicalName) Identifier where
  biplate (x, y) = plate (,) |- x |+ y

instance Biplate (NonTerminal LogicalName) Identifier where
  biplate (NTer x y) = plate NTer |- x |+ y

instance Biplate [Version] Identifier where
  biplate xs = (Zero, \Zero -> xs)

So if i want to write a transformation on another type i have to redo everything for this type too. In total there are 238 types, so the worst-case would go near 238 * 238 = 56644 instances. Well not exactly this but something like it i guess. I've been trying to use the derive package but i got blocked there as well ( https://github.com/ndmitchell/derive/issues/21 ). Ideally i would like to automatically derive the instances with either Data or with the faster GHC.Generics ( https://github.com/ndmitchell/uniplate/issues/11 ). I've been trying to implement the transformBi function with GHC.Generics. But i get stuck at about every turn i take.