Having trouble creating a function that can be multiple types

Question

I am trying to create a singular function in class Traceable that lets me take both binary and variable trees and output a list of lists of all possible paths to leaves. I can't seem to compile and have been racking my brain trying to figure it out for hours. If someone could give me a hand that would be amazing.

This is my code

data Tree a = Null | Node a [Tree a] deriving Show
data BinTree a = Nil | Vertex a (BinTree a) (BinTree a) deriving Show

class Traceable a where
trace :: (BinTree a, Tree z) => z a -> [a]

instance Traceable (BinTree a) where{
trace Nil = []
trace (Vertex x l r) = trace l ++ [x] ++ trace 

instance Traceable (Tree a) where{
trace Null = []
trace (Node a x) = [a] ++ (trace (head x))}

I am getting this error

* Expected a constraint, but `BinTree a' has kind `*'
* In the type signature:
    trace :: (BinTree a, Tree z) => z a -> [a]
  In the class declaration for `Traceable'

* Expected a constraint, but `Tree z' has kind `*'
* In the type signature:
    trace :: (BinTree a, Tree z) => z a -> [a]
  In the class declaration for `Traceable'

* Expecting one fewer argument to `z'
  Expected kind `* -> *', but `z' has kind `*'
* In the type signature:
    trace :: (BinTree a, Tree z) => z a -> [a]
  In the class declaration for `Traceable'

Edit: This is a school project for me and I can't use any Haskell extensions

Doing what you suggested it got a ton further but I still have a couple of errors.

* Expecting one fewer argument to `BinTree a'
  Expected kind `* -> *', but `BinTree a' has kind `*'
* In the first argument of `Traceable', namely `BinTree a'
  In the instance declaration for `Traceable (BinTree a)'

* Expecting one fewer argument to `Tree a'
  Expected kind `* -> *', but `Tree a' has kind `*'
* In the first argument of `Traceable', namely `Tree a'
  In the instance declaration for `Traceable (Tree a)'

Edit #2 Thanks for your help, taking out the a from BinTree instantiation seems to have created another problem

* Couldn't match expected type `[a]'
              with actual type `t0 a0 -> [a0]'
* In the second argument of `(++)', namely `trace'
  In the second argument of `(++)', namely `[x] ++ trace'
  In the expression: trace l ++ [x] ++ trace
* Relevant bindings include
    r :: BinTree a (bound at tree.hs:11:20)
    l :: BinTree a (bound at tree.hs:11:18)
    x :: a (bound at tree.hs:11:16)
    trace :: BinTree a -> [a] (bound at tree.hs:10:2)

user_745903 · Answer

The cause of the error is simply the signature of the trace method. It doesn't make sense to talk about BinTree or Tree there – those are instances of the class and will be mentioned in time (when you declare the instance), not inside the class declaration. What you want is

class Traceable t where
  trace :: t a -> [a]

and then the instances should be written

instance Traceable BinTree where
  trace Nil = []
  ...
instance Traceable Tree where
  ...

There's another problem in the Tree instance: trace (head x) just creates the trace for the first subtree in the node. For one thing, that's not even guaranteed to exist (there could be zero branches), for another, there will typically be multiple other branches that are ignored this way. What you want to do is recurse into all the branches, i.e. for all the elements in the x list. “Doing something for all things in a list” generally suggests that you could use map. So, map trace x. However, that has type [[a]] (because each trace generates [a], and you end up with a list of those lists.

What you want to do is concatenate all of those lists together. That can be done with, wait for it: concat.

  trace (Node a x) = [a] ++ concat (map trace x)

...or more elegantly

  trace (Node a x) = a : concat (trace <$> x)

In fact the combination of mapping and concatenating is so common that there exist a standard function for that: concatMap. Moreover, it's the characteristic method of the notorious Monad typeclass, of which lists are an instance. Knowing that, you can write

  trace (Node a x) = a : (trace =<< x)

Which is quite nice.

Really though, you need to do none of that because the idea of gathering together all fields of a polymorphic container is also super common, and can be dealt with automatically. Here's the recommended solution:

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}

import Data.Foldable

data Tree a = Null | Node a [Tree a]
 deriving (Show, Functor, Foldable)
data BinTree a = Nil | Vertex (BinTree a) a (BinTree a)
 deriving (Show, Functor, Foldable)

And then simply trace = toList.

Having trouble creating a function that can be multiple types

1 Answers