Understanding multiple types/typeclasses in Haskell declarations

Question

I'm trying to learn Haskell with Learn You A Haskell... but I got impatient and wanted to implement a favorite algorithm of mine to see if I could.

I'm working on the tortoise/hare algorithm (Floyd's algorithm) for cycle detection.

Here's the code I have so far:

idx :: (Eq a) => (a -> a) -> a -> a -> a
idx f tortoise hare
    | (f tortoise) == (f (f hare)) = (f f hare)
    | otherwise = (idx f) (f tortoise) (f f hare)

mu :: (Eq a) => (a -> a) -> a -> a -> Integer -> (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) => (a -> a) -> a -> a -> Integer -> Integer
lam f tortoise hare cntr
    | tortoise == hare = cntr+1
    | otherwise = (lam f) tortoise (f hare) (cntr+1)

floyd :: (Eq a) => (a -> a) -> a -> (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) => a -> 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

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).

The function floyd is my hacky attempt to put these together.

Aside from this being somewhat un-functional, I am also having issues loading the module and I'm not sure why:

Prelude> :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 => a -> a
Failed, modules loaded: none.

Changing all occurrences of Integer to Int or Num don't make it any better.

I'm not understanding the mis-application of Int. Following along in the tutorial, most type declarations for functions always have the form

function_name :: (Some_Type a) => <stuff involving a and possibly other types>

But when I replace the (Eq a) with (Num a) or (Int a) I get a similar error (type applied to too many arguments).

I tried reading this, but it disagrees with the tutorial's notation (e.g. almost every function defined in these examples).

I must be badly misunderstanding Types vs. TypeClasses, but that's precisely what I thought I did understand to lead me to make the type declarations as in my code above.

A follow up might be: what is the syntax for have multiple TypeClasses in the function type declaration? Something like:

mu :: (Eq a, Int b) => (a -> a) -> a -> a -> b -> (b, a)

(but this also gave compile errors saying Int was applied to too many arguments).

Added

Cleaned up and with changes based on the answer, the code below appears to be working:

idx :: (Eq a) => (a -> a) -> a -> a -> a
idx f tortoise hare
    | (f tortoise) == (f (f hare)) = (f (f hare))
    | otherwise = (idx f) (f tortoise) (f (f hare))

mu :: (Eq a) => (a -> a) -> a -> a -> Integer -> (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) => (a -> a) -> a -> a -> Integer -> Integer
lam f tortoise hare cntr
    | tortoise == hare = cntr+1
    | otherwise = (lam f) tortoise (f hare) (cntr+1)

floyd :: (Eq a) => (a -> a) -> a -> (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) => a -> 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" 

Then I see

*Main> floyd tester 2
(1,3)

and given this test function (essentially like the one from the Wikipedia example), this makes sense. If you start a x0 = 2 then the sequence is 2 -> 6 -> 1 -> 3 -> 6..., so mu is 1 (you have to move in one element to hit the start of the sequence) and lam is 3 (the sequence repeats every three entries).

I suppose there's some question about whether to always consider the first point as burn-in before you can possibly "repeat".

If anyone has advice on this, I'd be grateful. In particular, my cntr 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.

Answer 1

The general form of a (Rank-1) type declaration is

x :: [forall a b … . ] Cᴏɴꜱᴛʀᴀɪɴᴛ(a, b, …) => Sɪɢɴᴀᴛᴜʀᴇ(a, b, …)

where

• The forall a b … brings type variables in scope. This is usually omitted because Haskell98 implicitly uses all lowercase symbols in type-level expressions as type variables. Type variables are kind of like implicit parameters to a function: the caller gets to choose what particular type will be used, though they'll have to obey the...
• Cᴏɴꜱᴛʀᴀɪɴᴛ(a, b, …). This is most often either
  • a type class identifier together with some of the type variables (e.g. Integral a) which means "the caller has to make sure we can use a as some kind of integral number – add other numbers to it etc.",
  • a tuple of such type class constraints, e.g. (Eq a, Show a), which basically means constraint-level and: all of the constraint need to be fulfilled, the caller needs to make sure the variables are members of all the required type classes.

• Sɪɢɴᴀᴛᴜʀᴇ(a, b, …) is often some sort of function expression where the type variables may turn up on either side of an arrow. There can also be fixed types: much like you can mix literals and variables in (value-level) Haskell code, you can mix built-in types with local type variables. For example,

  showInParens :: Show a => a -> String
  showInParens x = "(" ++ show x ++ ")"
  

These are by far not the most general forms, though. In terms of modern Haskell,

• Cᴏɴꜱᴛʀᴀɪɴᴛ(a, b, …) is any type-level expression of kind Constraint, wherein the type variables may turn up, but also any suitable type constructors.
• Sɪɢɴᴀᴛᴜʀᴇ(a, b, …) is, quite similarly, any type-level expression of kind * (the kind of actual types), wherein the type variables may turn up, but also any suitable type constructors.

Now what is a type constructor? It's a lot like what values and functions are on the value level, but obviously on the type level. For instance,

GHCi> :k Maybe
Maybe :: * -> *

which basically means: Maybe acts as a type-level function. It has the kind of a function which takes a type (*) and spits out another one (*), so, since Int is a type, Maybe Int is also a type.

This is a very general concept, and though it may take some time to fully grasp it I think the following explains quite well everything that might still need to be said:

GHCi> :k (->)
(->) :: * -> * -> *
GHCi> :k (,)
(,) :: * -> * -> *
GHCi> :k Eq
Eq :: * -> Constraint

Answer 2

You can't say Integer a or Int a. You probably mean Integral a. Integral encompasses all types that are integers of some kind, including Integer and Int.

The thing before => is not a type but a type class. SomeTypeClass a => a means "any type a that is a member of the type class SomeTypeClass".

You can do this:

function :: Int -> String

which is a function that takes an Int and returns a String. You can also do this:

function :: Integer -> String

which is a function that takes an Integer and returns a String. You can also do this:

function :: Integral i => i -> String

which is a function that takes either an Int, or an Integer, or any other integer-like type and returns a String.

---

About your second question, your guess is right. You coud do

mu :: (Eq a, Integral b) => (a -> a) -> a -> a -> b -> (b, a)

---

Your commented questions:

1. what do you do if you want to ensure something has a Type that is a member of multiple TypeClasses?

You could do something like

function :: (Show a, Integral a) => a -> String

That will restrict a to be any type that is both a member of Show and Integral.

2. Suppose you only want to restrict the Type to reside in a TypeClass for some of the arguments, and you want other arguments to be of specific Types?

Then you just write out the other arguments as specific types. You could do

function :: (Integral a) -> a -> Int -> String

which takes any integer-like type a, and then an Int and returns a String.