title: Understanding multiple types/typeclasses in Haskell declarations
body: <p>I'm trying to learn Haskell with <a href="http://learnyouahaskell.com/" rel="nofollow noreferrer">Learn You A Haskell...</a> but I got impatient and wanted to implement a favorite algorithm of mine to see if I could.</p>
  
  <p>I'm working on the tortoise/hare algorithm (<a href="http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare" rel="nofollow noreferrer">Floyd's algorithm</a>) for cycle detection.</p>
  
  <p>Here's the code I have so far:</p>
  
  <pre><code>idx :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; a
  idx f tortoise hare
      | (f tortoise) == (f (f hare)) = (f f hare)
      | otherwise = (idx f) (f tortoise) (f f hare)
  
  mu :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; Integer -&gt; (Integer, a)
  mu f tortoise hare cntr
      | (f tortoise) == (f hare) = (cntr+1, f tortoise)
      | otherwise = (mu f) (f tortoise) (f hare) (cntr+1)
  
  lam :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; Integer -&gt; Integer
  lam f tortoise hare cntr
      | tortoise == hare = cntr+1
      | otherwise = (lam f) tortoise (f hare) (cntr+1)
  
  floyd :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; (Integer, Integer)
  floyd f x0 = 
      let z = (idx f) x0 x0 
          (y1, t) = (mu f) x0 z 0
          y2 = (lam f) t (f t) 0
      in (y1, y2)
  
  tester :: (Integer a) =&gt; a -&gt; a
  tester a
      | a == 0 = 2
      | a == 2 = 6
      | a == 6 = 1
      | a == 1 = 3
      | a == 3 = 6
      | a == 4 = 0
      | a == 5 = 1
      | otherwise = error "Input must be between 0 and 6" 
  
  (floyd tester) 0
  </code></pre>
  
  <p>This tries to break the logic up into three steps. First get the index where f_idx == f_{2*idx}, then move from the start to get the parameter mu (distance from first element to start of the cycle), then move until you hit a repeat (length of the cycle).</p>
  
  <p>The function <code>floyd</code> is my hacky attempt to put these together.</p>
  
  <p>Aside from this being somewhat un-functional, I am also having issues loading the module and I'm not sure why:</p>
  
  <pre><code>Prelude&gt; :load M:\papers\programming\floyds.hs
  [1 of 1] Compiling Main             ( M:\papers\programming\floyds.hs, interpreted )
  
  M:\papers\programming\floyds.hs:23:12:
      `Integer' is applied to too many type arguments
      In the type signature for `tester': tester :: Integer a =&gt; a -&gt; a
  Failed, modules loaded: none.
  </code></pre>
  
  <p>Changing all occurrences of <code>Integer</code> to <code>Int</code> or <code>Num</code> don't make it any better.</p>
  
  <p>I'm not understanding the mis-application of <code>Int</code>. Following along in the tutorial, most type declarations for functions always have the form</p>
  
  <pre><code>function_name :: (Some_Type a) =&gt; &lt;stuff involving a and possibly other types&gt;
  </code></pre>
  
  <p>But when I replace the <code>(Eq a)</code> with <code>(Num a)</code> or <code>(Int a)</code> I get a similar error (type applied to too many arguments).</p>
  
  <p>I tried <a href="https://stackoverflow.com/questions/12018959/string-is-applied-to-too-many-type-arguments">reading this</a>, but it disagrees with the tutorial's notation (e.g. <a href="http://learnyouahaskell.com/higher-order-functions" rel="nofollow noreferrer">almost every function defined in these examples</a>). </p>
  
  <p>I must be badly misunderstanding Types vs. TypeClasses, but that's precisely what I thought I <em>did</em> understand to lead me to make the type declarations as in my code above.</p>
  
  <p>A follow up might be: what is the syntax for have multiple TypeClasses in the function type declaration? Something like:</p>
  
  <pre><code>mu :: (Eq a, Int b) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; b -&gt; (b, a)
  </code></pre>
  
  <p>(but this also gave compile errors saying <code>Int</code> was applied to too many arguments).</p>
  
  <p><strong>Added</strong></p>
  
  <p>Cleaned up and with changes based on the answer, the code below appears to be working:</p>
  
  <pre><code>idx :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; a
  idx f tortoise hare
      | (f tortoise) == (f (f hare)) = (f (f hare))
      | otherwise = (idx f) (f tortoise) (f (f hare))
  
  mu :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; Integer -&gt; (Integer, a)
  mu f tortoise hare cntr
      | (f tortoise) == (f hare) = (cntr+1, (f tortoise))
      | otherwise = (mu f) (f tortoise) (f hare) (cntr+1)
  
  lam :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; a -&gt; Integer -&gt; Integer
  lam f tortoise hare cntr
      | tortoise == hare = cntr+1
      | otherwise = (lam f) tortoise (f hare) (cntr+1)
  
  floyd :: (Eq a) =&gt; (a -&gt; a) -&gt; a -&gt; (Integer, Integer)
  floyd f x0 = 
      let z = (idx f) x0 x0 
          (y1, t) = (mu f) x0 z 0
          y2 = (lam f) t (f t) 0
      in (y1, y2)
  
  tester :: (Integral a) =&gt; a -&gt; a
  tester a
      | a == 0 = 2
      | a == 2 = 6
      | a == 6 = 1
      | a == 1 = 3
      | a == 3 = 6
      | a == 4 = 0
      | a == 5 = 1
      | otherwise = error "Input must be between 0 and 6" 
  </code></pre>
  
  <p>Then I see</p>
  
  <pre><code>*Main&gt; floyd tester 2
  (1,3)
  </code></pre>
  
  <p>and given this test function (essentially like the one from the Wikipedia example), this makes sense. If you start a <code>x0 = 2</code> then the sequence is <code>2 -&gt; 6 -&gt; 1 -&gt; 3 -&gt; 6...</code>, so <code>mu</code> is 1 (you have to move in one element to hit the start of the sequence) and <code>lam</code> is 3 (the sequence repeats every three entries).</p>
  
  <p>I suppose there's some question about whether to always consider the first point as burn-in before you can possibly "repeat".</p>
  
  <p>If anyone has advice on this, I'd be grateful. In particular, my <code>cntr</code> construct seems un-functional to me.. it's a way of counting how many repeated calls are made. I'm not sure if there's a better/different way that's less like saving the state of a variable.</p>