import Data.Traversable
append :: NestedList a -> NestedList a -> Either String (NestedList a)
append (Elem x) (Elem y) = Right $ List [Elem x, Elem y]
append (Elem _) _ = Left ""
append _ (Elem _) = Left ""
append (List xs) (List ys) = fmap List $ sequenceA $ zipWith append xs ys
The append you wrote in your questions seems to want to just flatten and concatenate the two lists, which is rather pointless, since you are throwing away all the structure. If this is desired behavior, then just use a regular list:
append' :: NestedList a -> NestedList a -> Either String [a]
append' (Elem x) (Elem y) = Right $ [x,y]
append' (Elem _) _ = Left ""
append' _ (Elem _) = Left ""
append' a b = Right $ flatten a ++ flatten b
You could also define your datatype in terms of the free monad:
import Control.Monad.Free
type NestedList = Free []
flatten :: NestedList a -> [a]
flatten = retract
append :: NestedList a -> NestedList a -> Either String (NestedList a)
append (Pure x) (Pure y) = Right $ Free [Pure x, Pure y]
append (Pure _) _ = Left ""
append _ (Pure _) = Left ""
append (Free xs) (Free ys) = fmap Free $ sequenceA $ zipWith append xs ys
This definition is isomorphic to the one you gave.