Type Deduction problem in Haskell (type class and instance declarations)

Sized.hs

{-# LANGUAGE GeneralizedNewtypeDeriving, FlexibleInstances #-}
module Sized where

import Data.Monoid

newtype Size = Size { getSize :: Int }
  deriving (Eq, Ord, Show, Num)

class Sized a where
  size :: a -> Size

instance Sized Size where
  size = id

instance Monoid Size where
  mempty  = Size 0
  mappend = (+)

data JoinList m a = Empty
                   | Single m a
                   | Append m (JoinList m a) (JoinList m a)
  deriving (Eq, Show)

testSomething :: (Sized b, Monoid b) => JoinList b a -> JoinList b a
testSomething (Single s value) = let numOfElem = getSize (size s)
                                     newSize = Size (numOfElem + 1)
                                 in Single newSize value
testSomething jl = jl


tree = Single (Size 5) "A"

main :: IO ()
main = putStrLn $ show $ testSomething tree

{-
Produces the following error:

Sized.hs:27:44:
    Could not deduce (b ~ Size)
    from the context (Sized b, Monoid b)
      bound by the type signature for
                 testSomething :: (Sized b, Monoid b) =>
                                  JoinList b a -> JoinList b a
      at Sized.hs:24:18-68
      ‘b’ is a rigid type variable bound by
          the type signature for
            testSomething :: (Sized b, Monoid b) =>
                             JoinList b a -> JoinList b a
          at Sized.hs:24:18
    Relevant bindings include
      s :: b (bound at Sized.hs:25:23)
      testSomething :: JoinList b a -> JoinList b a
        (bound at Sized.hs:25:1)
    In the first argument of ‘Single’, namely ‘newSize’
    In the expression: Single newSize value
-}

This is one possible solution: adding sFromInt to your class. This way you can do your calculation in Int and convert it back to any instance of Sized. This is probably not a very Haskelly solution, but it shows you that it's doable.

class Sized a where
  size :: a -> Size
  sFromInt :: Int -> a

instance Sized Size where
  size = id
  sFromInt s = Size s

testSomething :: (Sized b, Monoid b) => JoinList b a -> JoinList b a
testSomething (Single s value) = let numOfElem = getSize (size s)
                                     newSize = sFromInt (numOfElem + 1)
                                 in Single newSize value

However, for the way you are using it, I would think you'd want your Sized to be a subclass of Monoid. In that case, this would be more direct and convenient:

class Monoid a => Sized a where
  size :: a -> Size
  sFromInt :: Int -> a

instance Sized Size where
  size = id
  sFromInt s = Size s

instance Monoid Size where
  mempty  = Size 0
  mappend = (+)

testSomething :: (Sized b) => JoinList b a -> JoinList b a
testSomething (Single s value) = let newSize = s `mappend` (sFromInt 1)
                                 in Single newSize value

I think I understand your confusion. Let me play the role of an obnoxious compiler (GHC is very polite, and it always assumes that it's some kind of misunderstanding). So you are telling me that testSomething will work for any type b, as long it's Sized and Monoid. Well, you're wrong! Let me give you a counterexample.

data Money = Money Double Int

instance Sized Money where
    size (Money x n) = Size n

instance Monoid Money where
    mempty = Money 0.0 0
    (Money x n) `mappend` (Money x' n') = Money (x + x') (n + n')

moneyTree :: JoinList Money String
moneyTree = Single (Money 29.99 5) "A"

What happens when you call testSomething with moneyTree? You're trying to put Size instead of Money into the result. That won't work. What happened to the $29.99 that I gave you?!

Another way of looking at it is to remove the type signature from testSomething and ask GHCi what type it thinks it is. The answer is:

JoinList Size a -> JoinList Size a

It deduces the first type parameter to be Size, exactly because you're putting newSize of type Size into it.

Notice that this has nothing to do with Haskell. You'd have the same problem with any other language. You're trying to write a generic function that operates on containers of objects that are a subclass of some base B. You can't just replace an item in that container with an element of class B. What if you're called with a container of C, where C inherits from B. You'd return a container with all elements being C except for one that ends up as B. This won't even work in a dynamically typed language, except that you would get a runtime error much later, when you try to apply a method of C to a B, which doesn't support it.

That Money example was FANTASTIC, it cleared all the confusion I had about this situation. The problem I had was that I tried to map this to the hierarchy of interface -> concrete implementation like the following Java code for instance:

public interface MyInterface { ... }

public class MyClass implements MyInterface { ... }

public MyInterface testSomething() {
  return new MyClass();
}

But that is the comparison of Apples and Oranges in this situation. In case of the Haskell code, I'm not specifying the return type as something that is Sized and Monoid which makes it ok to return a concrete data type which is an instance of both Monoid and Sized! I'm reaching into the parameterized datatype (e.g JoinList) and replacing the contained item (as you mentioned) with something more specific that it needs to be and I can end up with a situation like the Money example that you drew above! I put Money in the JoinList and get back Size in the JoinList which is not permitted in ANY language of course! That Java interface example distracted me from the root cause of the problem and I could never get out of that rabbit hole 😄

Thank you SO MUCH, I highly appreciate it. It was a very interesting discussion and I learned a bunch of cool things actually 👍