How can I use generic type annotations to describe a recursive data type?

Question

Here's the function:

comboGraph :: [a] -> Int -> [b]
comboGraph _ 0 = []
comboGraph [] _ = []
comboGraph (x:xs) n =
    (buildEdges x xs) : comboGraph xs n
    where   buildEdges h t = (h, comboGraph t (n-1))

Ths function takes in a list of type a, a number, and returns a list of type b. As you can see, though, type b is actually a recursive type -- it will be something along the lines of [(a, [(a, b1)])]. When I try to compile, I get this error:

• Couldn't match type ‘b’ with ‘(a, [b0])’
  ‘b’ is a rigid type variable bound by
    the type signature for:
      comboGraph :: forall a b. [a] -> Int -> [(a, [b])]
    at xxx.hs:15:15
  Expected type: [(a, [b])]
    Actual type: [(a, [(a, [b0])])]
• In the expression: (buildEdges x xs) : comboGraph xs n
  In an equation for ‘comboGraph’:
      comboGraph (x : xs) n
        = (buildEdges x xs) : comboGraph xs n
        where
            buildEdges h t = (h, comboGraph t (n - 1))

How do I properly annotate this function?

You can not capture that in a list, since it would mean that a ~ [(b,a)]. You need a tree-like datastructure for that. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Feb 25, 2018 at 19:01
how actually do you want your data to look at? you will need to define a data to begin with. — Jason Hu
– Jason Hu, Commented Feb 27, 2018 at 19:49
@HuStmpHrrr ideally id like to use generic types a and b. — dopatraman
– dopatraman, Commented Feb 27, 2018 at 21:55
From what your code does, b has no chance to be generic. What problem are you solving? — Jason Hu
– Jason Hu, Commented Feb 27, 2018 at 21:56

duplode · Accepted Answer · 2018-03-01 02:09:01Z

To make the issue a bit more evident, let's substitute the definition of buildEdges in the final case of your definition:

comboGraph (x:xs) n =
    (x, comboGraph xs (n-1)) : comboGraph xs n

The result of comboGraph is supposed to be a list, but one whose elements are pairs that also have a comboGraph result (i.e. a list of the same type) within. As the type error you got says, that doesn't work -- it's as if you wanted a list with two tails. The fix is switching to a different data structure that reflects what you are trying to do:

-- Feel free to substitute better names.
data Combo a = Empty | Node a (Combo a) (Combo a)
    deriving (Eq, Ord, Show)

Empty covers the base cases which used to result in an empty list, while Node has one appropriately-typed field for each of the things you want to combine in the recursive case. comboGraph then becomes:

comboGraph :: [a] -> Int -> Combo a
comboGraph _ 0 = Empty
comboGraph [] _ = Empty
comboGraph (x:xs) n = Node x (comboGraph xs (n-1)) (comboGraph xs n)

(Note that Combo is actually a binary tree with values on the nodes.)

Daniel Wagner · Accepted Answer · 2018-03-01 02:18:28Z

I like the other answer, and I think you should use it. But it makes some reasoning leaps that require some intuition, and it can be hard to get this intuition without doing things the mechanical way a few times. So in this answer, I will show how to start with a failing definition like the one you have, "turn a crank", and mechanically get a solution that does work. The technique below can be applied to any infinite type error.

You have the following clause (paraphrased slightly):

comboGraph (x:xs) n =
    (x, comboGraph xs (n-1)) : {- ... -}

Just doing some straightforward type inference reasoning, we can see that comboGraph takes a list of some type (from the fact that it pattern matches on x:xs) and a number (from the fact that it subtracts one). Let's pick a concrete (monomorphic! but not yet known) type a for the list elements and see what we can infer about what it returns.

Well, it clearly returns a list with tuples inside. And the first part of the tuple is just an a. What about the second part? The second part of the tuple is... whatever type comboGraph returns. So comboGraph returns a type t satisfying the equation:

t = [(a, t)]

The only solution to this equation is [(a, [(a, [(a, [(a, ...)])])])]. Such infinite types don't exist raw in Haskell. But there is a standard trick to get quite close: use (type-level) recursion by introducing a newtype. We're solving for t, but Haskell types have to start with an upper-case letter, so we'll name our solution to this equation T.

newtype T a = T [(a, T a)] deriving Show

Now we don't quite have T a ~ [(a, T a)], but we do have an isomorphism: namely, \(T xs) -> xs :: T a -> [(a, T a)] and T :: [(a, T a)] -> T a are inverses. So now we can write your comboGraph definition by exploiting this isomorphism. Let's name the other half of the isomorphism:

unT :: T a -> [(a, T a)]
unT (T xs) = xs

So:

comboGraph (x:xs) n =
    T ((x, comboGraph xs (n-1)) : unT (comboGraph xs n))

The base cases have to get wrapped in T, as well, of course:

comboGraph _ 0 = T []
comboGraph [] _ = T []

Try it in ghci:

> comboGraph "abc" 3
T [('a',T [('b',T [('c',T [])]),('c',T [])]),('b',T [('c',T [])]),('c',T [])]

Collectives™ on Stack Overflow

How can I use generic type annotations to describe a recursive data type?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related