current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 3 down vote favorite

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?

share|improve this question
    
@AndrewC: I can’t quite see how yet, but it might be manageable using multiparameter type classes, no? The fact that (digpend a) wants to be polymorphic isn’t necessarily a problem. –  PLL Jun 28 '13 at 16:15

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
up vote 4 down vote

Solving this will require a bit of type-level programming skills and some GHC extensions.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE OverlappingInstances #-}

class Digpend a d where
  digpend :: a -> d -> d

instance (Digpend a d) => Digpend a [d] where
  digpend a list = map (digpend a) list

instance Digpend a [a] where
  digpend a list = a : list

main = do
  -- We have to help the compiler disambiguate the numbers by putting explicit
  -- type signatures:
  print $ digpend 
    (555 :: Int) 
    ([ [ [ 5,1,-12,33 ] , [ 6,22 ] ] , [ [ -9,0,9,12,83 ] ] ] :: [[[Int]]])
  -- In case of specific literals, such as `Char`, it's not a problem though.
  print $ digpend '!' [['a', 'b', 'c'], "def"]

Results in:

[[[555,5,1,-12,33],[555,6,22]],[[555,-9,0,9,12,83]]]
["!abc","!def"]
share|improve this answer
    
Interesting that we came to almost exactly the same solution! I wonder if there’s any approach that doesn’t require the explicit disambiguation? –  PLL Jun 28 '13 at 16:45
    
@PLL The ambiguity problem is not the problem of our solutions, but of the fact that numeric literals are inferred as Num a => a. Since our classes are polymorphic, the compiler can't use them to disambiguate it. In real life usage it won't be a problem though, since chances are this function will be used in a specific context, from which the compiler will be able to infer a specific type. There is also a possibility to infer either of the parameters based on another one by utilizing functional dependencies. –  Nikita Volkov Jun 28 '13 at 21:24
    
the ambiguity isn’t just from the numeric literals, since normally ghc(i) will happily either keep them polymorphic or choose defaults for them; it’s an interaction of some kind between this polymorphism and our slightly tricky flexible instances. It also won’t necessarily go away in real life usage, since polymorphic functions certainly don’t. Functional dependency could be a nice way to try to improve things, yes (though the class we’ve currently defined isn’t functional in either direction, so it doesn’t directly apply to our current approach). –  PLL Jun 30 '13 at 18:56
up vote 2 down vote

If you can/are allowed to define your own data type, you can also use the following:

data Tree a = Leaves [a] | InnerNodes [Tree a] deriving (Show)

digpend :: a -> Tree a -> Tree a
digpend x (Leaves xs) = Leaves $ x:xs
digpend x (InnerNodes []) = InnerNodes [Leaves [x]]
digpend x (InnerNodes xs) = InnerNodes . map (digpend x) $ xs

Some output examples:

*Main> digpend 10 $ InnerNodes [ Leaves [], Leaves [], InnerNodes []]
InnerNodes [Leaves [10],Leaves [10],InnerNodes [Leaves [10]]]
*Main> digpend 555 $ InnerNodes [InnerNodes [Leaves [5, 1, -12, 33], Leaves [6, 22]], InnerNodes [Leaves [-9, 0, 9, 12, 83]]]
InnerNodes [InnerNodes [Leaves [555,5,1,-12,33],Leaves [555,6,22]],InnerNodes [Leaves [555,-9,0,9,12,83]]]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.