Nested List Appending in Haskell

Question

I'm trying to write a function that will append a given value to the innermost lists of a nested list structure, but I'm running into errors with type when I'm not even sure what the type signature of such a function would be.

digpend a xs = case xs of [_:_] -> map (digpend a) xs
                          [[]]  -> [[a]]
                          xs    -> a:xs

For example,

digpend 555 [ [ [ 5,1,-12,33 ] , [ 6,22 ] ] , [ [ -9,0,9,12,83 ] ] ]

should return

[ [ [ 555,5,1,-12,33 ] , [ 555,6,22 ] ] , [ [ 555,-9,0,9,12,83 ] ] ]

and ideally, it would work on any level of nesting by recursion. Is this allowed?

Answer 1

Here is a not-entirely-satisfactory implementation, using type classes:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class DigPend a b where
  digpend :: a -> [b] -> [b]

instance DigPend a a where
  digpend x xs = (x:xs)

instance (DigPend a b) => (DigPend a [b]) where
  digpend x xs = map (digpend x) xs

It works well, as long as the type of the arguments is fully specified:

*Main> digpend (5 :: Int) ([6,7,8] :: [Int])
[5,6,7,8]
*Main> digpend (555 :: Int) ([[[5,1,-12,33],[6,22]],[[-9,0,9,12,83]]] :: [[[Int]]])
[[[555,5,1,-12,33],[555,6,22]],[[555,-9,0,9,12,83]]]
*Main> digpend (5 :: Int) ([] :: [Int])
[5]
*Main> digpend (5 :: Int) ([] :: [[Int]])
[]

However, an invocation like digpend 5 [6,7,8] triggers lots of “ambiguous type variable” errors — a numeric literal like 5 is polymorphic (it can inhabit any instance of Num), and while ghci would usually happily default to Integer, it first tries to solve the type class constraints for DigPend, and at that stage, there is not enough type information for it to know which instance of digpend to apply.