beginner implementation of Catamorphism for non binary trees versus the Composite Design Pattern

Question

For the moment, the dream still goes on, at each haskell concept I learn I am more enticed. Yet I havent completely fulfilled working on this precious @luqui's answer to my previous question about catamorphism, and i'm gonna come back at it until it's ok. It was about this sample code on Wikipedia, dealing with catamorphism on BINARY trees.

Nonetheless, I have tried implementing catamorphism for NON BINARY trees but I face some troubles:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                                 , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

-- that latest line doesnt please ghc upon "map g [y]"

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) } 

-- and this lattest sumTree is wrong too for ghc

I see > and +, just like the C++ operators > and +. So I don't understand ghc is angry at me without my giving to it objets implementing opertor >/+ or not.

Secondly I must admit I'm completely hazy about the sense of => (different from -> ???) and @ which seems to be like a guide for pattern matching.

How would you correct this code ?

And a latest question, I am also trying doing this because the Composite Pattern happened to be the most important for me in C++. And obviously I see it can be almost described in only one/two line in Haskell (that is truely amazing for me).

But how would you haskell people express the fact that Leaf and Composite constructor of Composition may have some kind of the same Interface? (I know it's not the good word since data are not mutable, but I hope you can guess-understand my concern/goal)

this is the total compilation error;

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

EDIT So this is the final version for non binary catamorphism

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                             , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composant a →  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ⇒ a →  a →  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

addList :: Num a ⇒ [a] → a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList } 

And according to the valid answer below: what I was asking for haskell equivalent of C++ Interfaces contracts seems to be typeclasses constraints.

So the design pattern Composite would be achieved by applying typeclass constraints when constructing the Composition a. Maybe a new specialized data should be define. But I should learn typeclasses before doing that :-)

Answer 1

There are a few different errors here, so I'm not sure the best way to deal with it on SO, but what the heck.

In the future, try to include more of the errors that GHC provides.

In:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

The function foldCompose has two errors that I can see, only one of which will be caught by the type checker.

1. You're pattern matching on (Composite [y]), which will only match for lists of one element. You likely want (Composite ys), which binds ys to the entire list.

2. map g [y] won't pass the type checker, because you've already defined g as taking a list of r, but you're giving it a list of a.

   In order to convert an a to an r you need to apply your CompositionAlgebra to it: g (map (foldComposition a) ys)

So I would write this as:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

For your next error:

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

In Haskell, a type variable (like a here) all by its lonesome may be filled in with any type at all by the caller, at the caller's choosing.

This means in your type signature you're claiming that the function maxPair will work for every input type. GHC complains (in its own way) that the operator > doesn't work for every type, and therefor refuses to compile your program.

You'll need to use typeclasses to solve this problem. In Haskell, typeclasses let the caller pick the types to use, but with some constraints. I recommend reading a Haskell tutorial on typeclasses.

The correct type signature would be:

maxOfPair :: Ord a => a →  a →  a

Which applies the Ord constraint to the type a.

Also, you should be using the standard function max.

Answer 2

Secondly I must admit I'm completely hazy about the sense of => (different from -> ???) and @ which seems to be like a guide for pattern matching.

Consinder the elem function, which tests if a list contains a certain value. You could define it as

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

Which signature has this function? Looks like elem :: a -> [a] -> Bool. But the compiler will complain because you wrote x == y, and not for every a the == function is defined, only for those a which are in the Eq type class. So you need to specify something like "For all a which are in Eq...". And exactly for this you need =>. So the correct signature for elem is elem :: Eq a => a -> [a] -> Bool.

The @ gives you the possibility to give a whole structure a name and to pattern match on it at the same time. E.g. if you have the pattern a@(x:xs) and you call that function with [1,2,3,4], then a is [1,2,3,4], xis 1 and xs is [2,3,4].