title: Overlapping instance in haskell
body: <p>I'm reading code of the <code>HList</code> library. There is an <code>HBetween</code> class which is a type level function taking a <code>HNat</code> n and return a list of <code>HNat</code>s forming a range [HZero, n). I want to implement an other class <code>HRange</code>, it has an overload function <code>hRange :: l -&gt; u -&gt; r</code> which take a low bound <code>l</code> and a upper bound <code>u</code> and return a range [l, u). My code is below(to make the code more clear, the result of <code>hRange</code> is in reversed order, say (u, l] )</p>
  
  <pre><code>{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, 
      FlexibleInstances, FlexibleContexts, UndecidableInstances #-}
  module Data.HList.HNats where
  import Data.HList.CommonMain
  class (HNat l, HNat u) =&gt; HRange l u r | l u -&gt; r where
    hRange :: l -&gt; u -&gt; r
  instance HNat l =&gt; HRange l (HSucc l) (HCons l HNil) where
    hRange _ _ = undefined
  instance HRange l u r =&gt; HRange l (HSucc u) (HCons u r) where
    hRange _ _ = undefined
  </code></pre>
  
  <p>I tried this code in ghci, something unexpected happened:</p>
  
  <pre><code>*Data.HList.HNats Data.HList&gt; :load Data/HList/HNats
  [1 of 1] Compiling Data.HList.HNats ( Data/HList/HNats.hs, interpreted )
  Ok, modules loaded: Data.HList.HNats.
  *Data.HList.HNats Data.HList&gt; hRange hZero (hSucc hZero )
  
  &lt;interactive&gt;:24:1:
      Overlapping instances for HRange
                                  HZero (HSucc HZero) (HCons HZero HNil)
        arising from a use of `hRange'
      Matching instances:
        instance HNat l =&gt; HRange l (HSucc l) (HCons l HNil)
          -- Defined at Data/HList/HNats.hs:14:10
        instance HRange l u r =&gt; HRange l (HSucc u) (HCons u r)
          -- Defined at Data/HList/HNats.hs:20:10
      In the expression: hRange hZero (hSucc hZero)
      In an equation for `it': it = hRange hZero (hSucc hZero)
  *Data.HList.HNats Data.HList&gt; 
  </code></pre>
  
  <p>I don't know why <code>hRange hZero (hSucc hZero )</code> could match instance <code>instance HRange l u r =&gt; HRange l (HSucc u) (HCons u r)</code>. Any explanation is appreciated!</p>