CODEWITHSUNDEEP
haskell
dopatraman
dopatraman

Reputation: 13908

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

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?

Upvotes: 2

Views: 157

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 152682

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 [])]

Upvotes: 4

duplode
duplode

Reputation: 34378

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.)

Upvotes: 6

Related Questions