Generic Haskell: Determine whether a constructor is recursive or not

Question

I want to write some functions that work over all data types in Haskell (at least all instances of Data from Data.Data). A general problem I ran into is making a choice of what to do based on whether the constructor is recursive or not -- by recursive constructor I mean the data type is D and the there is a constructor C one of whose arguments is a D.

I can solve the above problem by solving a simpler problem: given a data, determine whether the outermost constructor is recursive.

Here is attempt number 1:

data B a = T | F
gIsLeafCons :: (Data a) => a -> B a
gIsLeafCons m = gfoldl (\x y -> F) (\x -> T) m

The idea is that if the constructor is recursive, then we return F else we return T. This works great at first glance:

gIsLeafCons 1 ==> T
gIsLeafCons ([] :: [Int]) ==> T

However, gfoldl is polymorphic, so given a tree data type such as

data Tree a = Leaf a | Node (Tree a) (Tree a)

We fail.

gIsLeafCons (Leaf 1) ==> F

The reason is that (Leaf 1) is not a truly empty constructor: it has the argument 1, and so the constructor function (\x y -> F) is applied.

Attempt number 2:

We could go with a "leaf constructor" is one where all children evaluate to F. This is a slight improvement:

gIsLeafByChild (Leaf 1) ==> T

However, if the leaves hold a different recursive structure; this will again fail.

gIsLeafByChild (Leaf (Leaf 1)) ==> F

I really want to stop at the first "leaf constructor" but gfoldl's polymorphic nature makes it seem hard to do this, as seen above.

So finally, is there a way to coax out whether a constructor is a "leaf constructor" or not. My current solution is to have a user pass in a list of leaf constructors ([Constr]), and I just check if the constructor is one of these. However, it would be nice to automatically infer if something would be in this list.

What will you do if there are two mutually-recursive constructors in different data types? data T = T Int F; data F = F Int T, for example. This could reasonably be considered recursive or "leaf". — amalloy
@amalloy: That's a fine question. I haven't thought too much about this, but I would say that a constructor is recursive if folding over that constructor requires invoking a fold. In the above foldT t f (T n a) = t n (foldF f t a); foldF f t (F n a) = f n (foldT t f a). So I would call them both recursive. Would that be reasonable? — Jonathan Gallagher
You might be interested in Constant from Data.Constant.Functor in the transformers package. hackage.haskell.org/package/transformers-0.4.1.0/docs/… It captures the idea of your B a type in general, for example, B a would be Constant Bool a. — Cirdec

Cirdec Cirdec · Accepted Answer · 2014-10-16T19:22:54

You've got a good start using gfoldl. We need to make two changes. First, as we traverse the structure, we need to keep track of each encountered type to see if they occur recursively. Secondly, we need to use gfoldl recursively to look inside the types we discover in the constructor.

Let's get some utility out of the way. bool will get the Bool result when we're done, and bId will convert Bs from one type to another.

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE RankNTypes #-}

import Data.Data

data Tree a = Leaf a | Node (Tree a) (Tree a)
    deriving (Data, Typeable)

data B a = T | F

bool :: B a -> Bool
bool T = True
bool F = False   

bId :: B a -> B b
bId T = T
bId F = F

We can get the type's representation, or TypeRep, from the Typeable class. Typeable is a superclass of Data, so whenever we have a Data a instance for some a, we will also have a Typeable a instance. We'll keep track of these by carrying around a list of the containing types' representations in a [TypeRep].

recursivelyConstructed :: Data a => a -> Bool
recursivelyConstructed = bool . rc []
    where
        cf :: forall d. d -> B d
        cf = const F        
        rc :: forall d. Data d => [TypeRep] -> d -> B d
        rc ts d = gfoldl (rc' (typeOf d:ts)) cf d
        rc' :: forall d b. Data d => [TypeRep] -> B (d -> b) -> d -> B b
        rc' _  T _ = T
        rc' ts F d =
            if elem (typeOf d) ts
            then T
            else bId . rc ts $ d

Let's try some examples

infiniteTree = Node infiniteTree infiniteTree

recursivelyConstructed (Leaf 1                        :: Tree Int) = False
recursivelyConstructed (Node (Leaf 1) (Leaf 2)        :: Tree Int) = True
recursivelyConstructed (infiniteTree                  :: Tree Int) = True
recursivelyConstructed (Leaf (Leaf 1)                 :: Tree (Tree (Int))) = False
recursivelyConstructed (Just (Leaf 1)                 :: Maybe (Tree Int))  = False
recursivelyConstructed (Just (Node (Leaf 1) (Leaf 2)) :: Maybe (Tree Int))  = True
recursivelyConstructed (Just infiniteTree             :: Maybe (Tree Int))  = True
recursivelyConstructed (Just (Leaf (Leaf 1))          :: Maybe (Tree (Tree Int))) = False

Generic Haskell: Determine whether a constructor is recursive or not

1 Answers