Concatenating lists in ternary trees

Question

I'm making a function that concatenates ternary trees of lists, using an accumulator.

 19 data Ttree t = Nil | Node3 t (Ttree t) (Ttree t) (Ttree t)
 20 
 21 acc :: Ttree [a] -> [a]
 22 acc tree = acc' tree []
 23 
 24 acc' :: Ttree [a] -> [a] -> [a]
 25 acc' Nil rest = rest
 26 acc' (Node3 xs l m r) rest =
 27     xs $ acc' l $ acc' m $ acc' r rest

I get this error, using ghc. But I don't see how the expected type of xs is a -> b:

e6.hs:26:4:
    Couldn't match expected type `a -> b' against inferred type `[a1]'
    In the first argument of `($)', namely `xs'

Answer 1

The left-hand-side of ($) must be a function (i.e. of type a -> b), which xs clearly not. Remember the definition of ($) is

f $ x = f x

it is not a substitution of parenthesis in general. Probably you want

acc' (Node3 xs l m r) rest = xs ++ (acc' l . acc' m . acc' r) rest

instead.

(Note that this is not tail recursive.)

Answer 2

A small addition to Kenny's answer:

Prelude> :t ($)

($) :: (a -> b) -> a -> b